qq_43412960
qq_43412960
采纳率79.1%
2020-04-26 22:58

这是一个关于数据结构二叉树的内容

5
已采纳

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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • caozhy 从今以后生命中的每一秒都属于我爱的人 1年前

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

    点赞 1 评论 复制链接分享

相关推荐