引入

前面，我们说过，二叉树的遍历方法，以及如何使用代码创建二叉树并将三种遍历顺序都输出出来。如果你还对单链表有印象，我们会发现上节我们树的创建过程其实就是根结点指向左右子树，很像单链表指向唯一后继，对不对？还记得为什么我们要使用双向链表嘛？因为双向链表在找寻唯一前驱的时候方便。因此，二叉树也遇到了相同的问题，左右子树不知道自己的双亲是谁，我们该怎么解决呢？

问题

现在的二叉树

一个结点下，数据域和指针域
数据域，存放数据
指针域，指向该结点下的左右子树

问题一

如果我要找这个结点的双亲该怎么办呢？

麻烦了！我们要重新遍历这个棵二叉树
直到遇到这个结点，然后记录它得双亲

问题二

我们看上面这张图，发现

一个结点的指针域，如果没有左右子树！
例如 EFGHI ，它们的指针域会非常的浪费空间！
计算下来，一共9个结点，18个指针，10个都被浪费了。

好了，现在的问题是

左右子树找到不到双亲结点，孩子找不到爹妈。
如果没有左右子树，结点空间又被浪费掉！

思考

那么把剩余的空间利用起来，存放结点的双亲信息不就好了？

那我们就把结点的结构改造一下
让程序直到，我的左右子树指向的是我的左右子树，还是前驱后继

改造

我们将原有的结点结构体，改造如下

左孩子	左孩子状态	数据	右孩子状态	右孩子
Lchild	Ltag	Data	Rtag	Rchild

我们发现，增加了左右孩子的状态

左孩子状态为0，那么左孩子指向的是左孩子的结点地址。
左孩子状态为1，那么左孩子指向的是该结点的前驱地址。
右孩子状态为0，那么右孩子指向的是左孩子的结点地址。
右孩子状态为1，那么右孩子指向的是该结点的后继地址。

这么说可能有点晕，我们看看这张图，我们看到

现在 H 结点的左右子树地址为 NULL
那么我们让 H 结点的 Ltag 为 1
H 结点的左孩子指针域存储的就是H 结点的前驱
那么我们让 H 结点的 Rtag 为 1
H 结点的右孩子指针域存储的就是H 结点的后继
因为 H 结点的后继是没有的，所以存储为 NULL。

这样我们就最大限度上利用了存储空间，提高了搜索结点时的效率。即用空间换时间。下节我们主要讲讲线索二叉树的代码。

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。