数据结构——5.3 二叉树的遍历和线索二叉树
第五章 树与二叉树
5.3 二叉树的遍历和线索二叉树
- 概念
-
线索二叉树：为了快速得到遍历序列的前驱和后继
- 理解
-
线索二叉树是一种物理结构，二叉树一种逻辑结构
-
n个结点的线索二叉树具有2n个链域指针，除了根节点外，每个结点都被一个指针指向，因此用掉了n-1个指针，还剩下n+1个指针用作线索
-
指针指向的左右，若为0则是正常的子节点，若为1则为线索
- 技巧
-
中序遍历二叉树的终点一定是最右边的叶子
-
后序遍历的出入栈能够体现根节点到某一结点的路径
-
二叉树的先序、中序、后序遍历中，所有叶节点的先后顺序是不变的
-
若先序与后序结果相反：
-
叶结点只有一个
-
每层只有一个结点
-
结点数等于高度
-
不可能存在一个结点同时有左右孩子
-
中序序列中根节点在序列首或序列尾；
-
次根结点（移除根节点后变成根节点的结点，即原根节点的孩子结点）在不含根节点的序列中也在序列首或序列尾
-
-
若先序与后序结果相同，则该二叉树只有一个根节点
-
先序和后序序列组合
-
不能确定二叉树，必须要有中序参与
-
可以确定结点间的祖先关系，如先序XY，后序YX则X为Y的双亲，例如：先序aebdc、后序bcdea，则根节点a的孩子只有e
-
-
后序线索树的遍历需要栈的支持
-
前序序列与中序序列组合可以表述唯一的二叉树
-
前序序列作为入栈的次序，中序序列作为出栈的次序
-
若已知入栈次序和入栈元素个数n，则出栈的序列个数有： 1 n + 1 C 2 n n \frac{1}{n + 1}C_{2n}^{n} n+11C2nn个，即可能的二叉树个数
-
-
如果想要二叉树先序序列和中序序列相同，则所有非叶节点必须只有右子树