开发者社区> 问答> 正文

关于数据结构二叉树的内容

线索二叉树怎么充分利用了剩余结点呢?把剩余结点记录前驱后继,有什么效果呢? 课本上说,把树形逻辑变为线性逻辑,这一点如何体现的呢?

展开
收起
海边一只船 2020-05-28 13:30:44 700 0
1 条回答
写回答
取消 提交回答
  • image.png 看这个图,比如说先序遍历 传统的,每个节点存储左右孩子(蓝色线) 1->2->3没问题,3回不到2了。怎么办,需要在访问2的时候,把2放入堆栈。访问完3,左右都没有孩子了,此路走完,再到堆栈里面找2,才能到4。 类似的,4到1也不能直接连上。6到5也不能连上。 怎么办? 增加一个"线索",红色的箭头,在3的节点上指向2,4指向1,6指向5。 这样,不需要堆栈就可以遍历了。 image.png 没有线索,遍历需要4个序列。 现在用红色绳子把这4列串成一条线,这就是线索。 什么地方需要添加“线索”?没有左右孩子的节点,所以为了节约存储,可以把线索和孩子的节点放在同样的存储单元,用一个flag区分,是孩子还是线索。

    2020-05-29 18:16:31
    赞同 展开评论 打赏
问答标签:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
如何使用Tair增强数据结构构建丰富在线实时场景 立即下载
Apache Flink 流式应用中状态的数据结构定义升级 立即下载
低代码开发师(初级)实战教程 立即下载