线索式二叉树

二叉树的线索链表存储结构

二叉链表的空间利用情况：

在由n（n≥1）个节点构成的二叉树中，采用左右链表示法时，仅有n-1个指针用于指向子树，而空指针域的数量则达到了n+1个。

如何有效利用这些空指针域以解决上述问题？

• 当结点p存在左孩子时，p->lchild将指向该左孩子节点；若不存在，则令其指向该结点在（先序、中序、后序、层序）遍历中的前驱节点；
• 当结点p存在右孩子时，p->rchild将指向该右孩子节点；若不存在，则令其指向该结点在（先序、中序、后序、层序）遍历中的后继节点；

如何判断指针是用于指向左/右孩子，还是用于指示某种遍历方式下的前驱/后继？
可在每个结点中增设两个标志位，用以明确标识该节点的两个链域分别是指向其左/右孩子，还是指向特定遍历顺序下的前驱或后继。

节点构成：

![