关于数据结构二叉树的内容
线索二叉树怎么充分利用了剩余结点呢？把剩余结点记录前驱后继，有什么效果呢？ 课本上说，把树形逻辑变为线性逻辑，这一点如何体现的呢？
展开
收起
1
条回答
写回答
写回答
-
看这个图，比如说先序遍历 传统的，每个节点存储左右孩子（蓝色线） 1->2->3没问题，3回不到2了。怎么办，需要在访问2的时候，把2放入堆栈。访问完3，左右都没有孩子了，此路走完，再到堆栈里面找2，才能到4。 类似的，4到1也不能直接连上。6到5也不能连上。 怎么办？ 增加一个"线索"，红色的箭头，在3的节点上指向2，4指向1，6指向5。 这样，不需要堆栈就可以遍历了。 
没有线索，遍历需要4个序列。 现在用红色绳子把这4列串成一条线，这就是线索。 什么地方需要添加“线索”？没有左右孩子的节点，所以为了节约存储，可以把线索和孩子的节点放在同样的存储单元，用一个flag区分，是孩子还是线索。2020-05-29 18:16:31赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
