线索二叉树的画法

视频讲解线索二叉树的画法（通俗易懂）

1.线索二叉树的定义

在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。

2.线索二叉树的存储结构

线索二叉树中的线索能记录每个结点前驱和后继信息。为了区别线索指针和孩子指针，在每个结点中设置两个标志ltag和rtag。
当ltag和rtag为0时 ，leftChild和rightChild分别是指向左孩子和右孩子的指针；否则，leftChild是指向结点前驱的线索(pre)，rightChild是指向结点的后继线索(suc)。由于标志只占用一个二进位，每个结点所需要的存储空间节省很多。

3.画法

核心思想：将二叉树的腿给补全了。（每个二叉树可以有两条腿）

步骤：

1. 先写出对应遍历序列的顺序
2. 每个节点，先看它缺哪条腿（即哪个孩子为空），左孩子为空，表明要连左腿，右孩子为空，表明要连右腿，根据序列找其左边的节点和右边节点，找到即连接上对应节点，找不到即指向空。

例题1：

最终答案

例题2：

最终答案