Question

线索二叉树是一种什么结构？

Answer 1

线索二叉树是一种物理结构。

用二叉表中空指针域，存放指向该结点在某种遍历次序下的前驱与后续节点的指针称为线索，这种加上了线索的二叉链表称为线索链表，相应的二叉树也称为线索二叉树，根据性质不同分别有前序、中序、后序等线索二叉树。

线索化具体实现

以中序二叉树的线索化为例，线索化的具体实现就是将中序二叉树的遍历进行修改，把原本打印函数的代码改为指针修改的代码就可以了。

我们设置一个pre指针，永远指向遍历当前结点的前一个结点。若遍历的当前结点左指针域为空，也就是无左孩子，则把左孩子的指针指向pre（相对当前结点的前驱结点）。

右孩子同样的，当pre的右孩子为空，则把pre右孩子的指针指向当前结点（相对pre结点为后继结点）。

最后把当前结点赋给pre，完成后续的递归遍历线索化。