第五章 树与二叉树

5.3 二叉树的遍历和线索二叉树

• 概念

1. 线索二叉树：为了快速得到遍历序列的前驱和后继

• 理解

1. 线索二叉树是一种物理结构，二叉树一种逻辑结构

2. n个结点的线索二叉树具有2n个链域指针，除了根节点外，每个结点都被一个指针指向，因此用掉了n-1个指针，还剩下n+1个指针用作线索

3. 指针指向的左右，若为0则是正常的子节点，若为1则为线索

• 技巧

1. 中序遍历二叉树的终点一定是最右边的叶子

2. 后序遍历的出入栈能够体现根节点到某一结点的路径

3. 二叉树的先序、中序、后序遍历中，所有叶节点的先后顺序是不变的

4. 若先序与后序结果相反：

   1. 叶结点只有一个

   2. 每层只有一个结点

   3. 结点数等于高度

   4. 不可能存在一个结点同时有左右孩子

   5. 中序序列中根节点在序列首或序列尾；

   6. 次根结点（移除根节点后变成根节点的结点，即原根节点的孩子结点）在不含根节点的序列中也在序列首或序列尾

5. 若先序与后序结果相同，则该二叉树只有一个根节点

6. 先序和后序序列组合

   1. 不能确定二叉树，必须要有中序参与

   2. 可以确定结点间的祖先关系，如先序XY，后序YX则X为Y的双亲，例如：先序aebdc、后序bcdea，则根节点a的孩子只有e

7. 后序线索树的遍历需要栈的支持

8. 前序序列与中序序列组合可以表述唯一的二叉树

   1. 前序序列作为入栈的次序，中序序列作为出栈的次序

   2. 若已知入栈次序和入栈元素个数n，则出栈的序列个数有：$\frac{1}{n+1}{C}_{2n}^n$个，即可能的二叉树个数

9. 如果想要二叉树先序序列和中序序列相同，则所有非叶节点必须只有右子树