算法与数据结构 --- 遍历二叉树和线索二叉树

第一部分 --- 遍历二叉树

 

1.空操作的意思就是操作结束

1.（先序遍历）如果遍历到的子树为空子树，则遍历结束，如果遍历的子树为非空子树，则先遍历这个子树的根结点，然后再去遍历这个子树的左子树和右子树（先左后右），遍历方式一样。

1.中根（序）遍历的操作和先根遍历差不多，唯一的区别就是中根遍历的顺序是先左子树然后根结点然后右子树

后序（根）遍历的顺序是：先左子树，然后是右子树，最后是根结点

 

1.如果只知道二叉树的前序序列和后序序列我们是无法确定唯一一颗二叉树的

  

 

必须具有中序序列和一个先序 / 后序序列的时候我们才能够还原出唯一确定的二叉树

（接下来讲讲遍历算法的实现）

先序遍历的算法如下

 

 

 

 

 

 

1.三种递归算法对于二叉树的访问路径都是一样的，只是访问结点的时机不同而已

1.这个辅助空间是我们每次调用遍历算法时开辟的，用来存储访问到的结点的数据的空间，在最坏的情况下，内存空间中会同时存在n个辅助空间（树每一层都只有一个结点的时，遍历树的话就会出现一直创建辅助空间而不释放，直到访问完最后一个结点，结束递归，才开始逐个释放内存空间），所以算法的空间复杂度取最坏情况O(n)

（接下来是遍历算法的非递归实现）

1.先把根结点入栈，然后将左子树的根结点入栈，然后将左子树的左子树的根结点入栈....，然后进行出栈操作，每有一颗子树的根结点出栈，我们就遍历这个子树的右子树，并对右子树的根结点采用同样的方式入栈和出栈，就这样不停的入栈和出栈，当树的所有的根结点都出栈的时候，我们的遍历就完成了。

BiTree p是一个指向二叉链表的中的根结点的指针（头指针）

InitStack（S）是在创建一个栈

 1.按照从上层到下层，从左到右的顺序依次访问每一个结点，且每一个结点只访问一次

1.上面这个出列的意思就是出队

二叉树的层次遍历使用的队列是顺序循环队列（定义如上）

 

1.如果单纯按照给定的先序序列来遍历创建二叉树的话，我们是不能够创建一个确定的二叉树的，那么解决办法是什么呢？

解决办法就是上面的第一步：从键盘输入二叉树的结点信息，通过这个结点信息 + 先序序列两个条件来唯一确定一个二叉树

（一般来说这个结点信息是赋值给我们要创建的二叉树中的每一个结点的空孩子）

1.最开始的先序序列是这样的：

但是根据这样的先序序列我们是无法创建一个确定的二叉树的，于是人们想到了用结点信息来修正这个先序序列

修正的步骤是：

1.人们创建一个结点信息（结点信息的数据类型和二叉树中的结点存储的数据的数据类型一致，且和每一个结点存储的每一个数据都不一样）

2.假设这个结点信息存储到我们要创建的二叉树中的每一个结点的空孩子中，存储好后得到一个修改后的二叉树:(结点信息就存储在图中的虚圆表示的空孩子中)

3.写出修改后的二叉树的先序遍历序列，并根据这个序列来创建我们想创建的二叉树：

4.创建步骤是：按照第三点中的先序序列来创建结点并输入结点中要存储的数据：根结点，然后左子树（左子树的根结点，然后左子树，右子树...），右子树 --- 创建结点时如果我们往结点中存储的是前面创建的结点信息的话则这个结点取消创建，如果不是就正常创建

 拷贝算法就是在遍历二叉树的同时创建新的结点复制遍历到的结点

 

 

 

如果结点本身就是叶子的话就直接返回1，不需要求叶子的左子树的叶子和右子树的叶子

---

第二部分 --- 线索二叉树

为了帮我们找到结点在特定遍历序列中的前驱和后继

 

 能不能把这 n + 1 个空指针域给利用起来呢？

1.将一个结点中的空指针域还未被利用起来的二叉树按照某种遍历次序使其变为线索二叉树的过程（即将结点的空指针域利用起来）的过程称为线索化。

2.左空指针域对应着前驱，右空指针域对应着后继

3.注意这里的结点的前驱和后继指的是特定的遍历序列中结点的前驱和后继，比如：

对上图的树进行中序遍历后我们得到上面那个中序遍历序列，其中B结点在这个中序遍历序列中的前驱是C结点后继是E结点

对原二叉树进行改造之后我们得到的有右边的这个二叉树就是原二叉树的线索二叉树，改造的过程称为线索化

1.为了区分线索二叉树中的指针域指向的是左右子树还是前驱后继，我们对二叉链表中的每个结点增设两个标志域 Itag 和 rtag，这两个标志域中数据的数据类型都是整型

 

当结点的左 / 右指针域为NULL空指针域的时候，则对应的标记 Itag和rtag 都标为1，如果结点在遍历序列中有对应的前驱 / 后继的话就将标记为1的空指针域指向对应的前驱结点和后继结点，如果没有的话则将左 / 右 指针域标为空指针域，

1.当线索二叉树中的一个结点的左 / 右指针域对应的标记域的值为1，但是这个左右指针域却没有指向任何结点的时候，我们称这个左 / 右指针域处于悬空态

2.在线索二叉树中必定会出现两个悬空态，一个悬空态是左指针域，另一个悬空态是右指针域

（从遍历序列来分析，必定会有一个结点缺少前驱（序列的第一个结点），一个结点缺少后继（序列的最后一个结点））

为了避免悬空态的出现导致指针域的狼粪，我们引入了线索二叉树的头结点：

头结点也和线索二叉树的结点一样有5个域，其中数据域为空，左标记域为0，左指针域指向线索二叉树的根结点；右标记域为1，右指针域指向遍历序列的最后一个结点

然后：遍历序列中的第一个结点的左指针域和最后一个序列的右指针域都不再是空指针域（处于悬空态），而是都指向我们引入的头结点