中序线索二叉树

对二叉树进行遍历
可以理解为 从分支结构 导出 线性结构

遍历出来的序列 可以看成线性结构

序列中每个元素（节点）都有了前驱和后继，除了序列两端的元素

提到前驱和后继 这是线性结构的东西。

线索二叉树 ，一种更方便遍历操作的二叉树，这里的遍历操作是指 深度优先遍历，前序、中序、后序。

策略是： 在二叉树 用叶子节点 中的 空指针 直接指出 当前节点 的前驱或者后继。（前驱或者后继是 指在遍历序列中的前驱和后继）

对于同一棵二叉树，根据其遍历方式的不同，会得到不同的线索二叉树。

用空指针指向其节点的前驱或后继 的过程 就叫做 二叉树线索化

一个节点 有左空指针，则左空指针指向其前驱， 有右空指针，则右空指针指向其后继。

之前设计的二叉链表的存储结构 - 节点结构体设计

不能区分两类指针，不能满足设计
一类是黑色的，原来的，可以指向其左孩子和右孩子的指针
一类是黄色的，指向其在遍历序列中前驱或者后继节点的指针

lTag 和 rTag 就是两个表签
当 lTag 等于 0 时 指针 lChild 指的就是其左孩子
当 lTag 等于 1 时 指针 lChild 指的就是其前驱

对于rTag 也是一样规定。

每当访问一个节点的时候，如果当前节点左指针为空，就把它的左指针规定为线索，指向其前驱节点。
而如果其前驱节点的右指针为空，就把它规定为线索，指向当前访问的节点。

把中序递归遍历中 对节点的访问 改成 对节点线索的连接

用*&pre 参数 始终指向 当前所访问节点的前驱节点
也就是p指针所指向节点的前驱节点。
p是用来遍历节点的指针。

1.png 2.png 3.png 4.png 5.png 6.png 7.png 8.png 9.png 10.png 11.png 12.png 13.png 14.png 15.png 16.png 17.png 18.png 19.png
20.png 21.png 22.png
23.png
24.png
25.png

如何找遍历序列的第一个节点？

显然是从根节点一直往左走，一直走的不能走为止，即走到空指针为止，这个空指针所在的节点 就是遍历序列的第一个节点

如何找遍历序列的最后一个节点？

显然是从根节点一直往右走，一直走的不能走为止，即走到空指针为止
，这个空指针所在的节点 就是遍历序列的最后一个节点

如何找一个节点的后继节点？

对于一个节点来说，如果它有后继节点，并且其右指针为线索，那线索所指的节点 就直接是后继节点。如果它的右指针不是线索，那就从这个节点往右走一步，然后再一直往左走，直到走到头，最左端的节点就是其后继节点。
例如 图中的 A1 的后继节点 就是A6

如何找一个节点的前驱节点？

显然如果有前驱节点，并且其左指针为线索，那么线索所指的节点就直接是 前驱节点。如果左指针不是线索，那就往左走一步，然后一直往右走，所到达的节点就是其前驱节点。
例如 图中的A1 的前驱节点 就是 A5