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

Question

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

Answer 1

看这个图，比如说先序遍历
传统的，每个节点存储左右孩子（蓝色线）
1->2->3没问题，3回不到2了。怎么办，需要在访问2的时候，把2放入堆栈。访问完3，左右都没有孩子了，此路走完，再到堆栈里面找2，才能到4。
类似的，4到1也不能直接连上。6到5也不能连上。
怎么办？
增加一个"线索"，红色的箭头，在3的节点上指向2，4指向1，6指向5。
这样，不需要堆栈就可以遍历了。

没有线索，遍历需要4个序列。
现在用红色绳子把这4列串成一条线，这就是线索。
什么地方需要添加“线索”？没有左右孩子的节点，所以为了节约存储，可以把线索和孩子的节点放在同样的存储单元，用一个flag区分，是孩子还是线索。