数据结构重学日记（二十四）线索二叉树

线索二叉树是不借助栈而借助链表实现的非递归遍历方式。

在之前的操作中，n 个结点的二叉树就有 n + 1 个空指针，这就造成了很大浪费，所以可以将空指针利用起来，存放其他结点的地址，这样更便于索引。

还以这个树为例， 中序遍历的顺序为 D G B A E C F，G 没有左右子树，下一个结点为 B，所以把 G 的右指针存为 B，B 没有右子树，所以把 B 的右指针设置为 A 。A 的右子树不空，所以就不管它。

G 的左子树为空，所以 G 的左指针指向 D。

指向前驱后继的指针称为线索。
加入线索的二叉链表就称为 线索二叉树。

二叉树

线索二叉树是为了解决二叉树存储存在大量空指针的问题。也可以加快查询某个结点前驱后继的速度。