二叉树的遍历和性质

相关术语
①节点：包含一个数据元素及若干指向子树分支的信息。
②节点的度：一个节点拥有子树的数目称为节点的度。
③叶子节点：也称为终端节点，没有子树的节点或者度为零的节点。
④分支节点：也称为非终端节点，度不为零的节点称为非终端节点。
⑤树的度：树中所有节点的度的最大值。
⑥节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层。
⑦树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度。
⑧有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树。
⑨无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树。
⑩森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树由原来根节点的各棵子树构成。

特殊类型
1、满二叉树：一棵深度为k且有2^k-1个结点的二又树称为满二叉树。
2、完全二叉树：除了最下层，其他每层都饱满，最下层的结点都集中在该层最左边的若干位置上。
完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。

二叉树的性质
性质1：二叉树第i层上的结点数目最多为2^i-1。
性质2：深度为k的二叉树至多有2^k-1个结点(k≥1)。
性质3：二叉树中，叶子节点数为n0，度为2的结点数为n2，则no=n2+1。

二叉树的遍历运算（递归定义）
(1)先序遍历：根，左子树，右子树
(2)中序遍历：左子树，根，右子树
(3)后序遍历：左子树，右子树，根

图1：

先：2 7 1 6 5 3 8 9 4；
中：1 7 5 6 3 2 8 4 9；
后：1 5 3 6 7 4 9 8 2；

图2：

先：A B C K D E H F J G；
中：B K C A H E D J F G；
后：K C B H E J G F D A；

注：
已知先序和中序，二叉树是唯一的。
已知后序和中序，二叉树是唯一的。
已知先序和后序，二叉树不是唯一的。
因为先序后序只能判断出根，中序才能判断左右子树。

题型一：已知其中一些遍历结果，求其他遍历结果。
题型二：中缀表达式向前缀和后缀表达式的转化
题型三：统计ｎ个不同的点可以构造多少棵不同的二叉树? Catalan数=C(n,2*n)/(n+1)。
化简后：(2n)!/n!(n+1)!

练习
1、已知先序：1 2 4 3 5 7 6， 中序：2 4 1 7 5 3 6，请画出整棵二叉树。
2、已知后序：4 5 2 6 7 3 1， 中序：4 2 5 7 6 3 1，请画出整棵二叉树。
3、已知先序：1 2 3 4 5 6， 后序：3 2 5 6 4 1， 请画所有二叉树的情况。
4、如果只知道先序ａｂｃ，画出所有可能二叉树形状，并且计算多少种？
5、如果只知道中序ａｂｃ，画出所有可能二叉树形状，并且计算多少种？
6、如果只知道后序ａｂｃ，画出所有可能二叉树形状，并且计算多少种？

历年题目
2010提高（同2010普及）
5、一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（ ）。
A．0 B．2 C．4 D． 6
2009提高（同2009普及）
6、表达式a*(b+c)-d的后缀表达式是：
A) abcd*± B) abc+d- C) abc+d- D) -+*abcd
2008提高
16、二叉树T，已知其先序遍历是1 2 4 3 5 7 6（数字为节点编号，以下同），后序遍历是4 2 7 5 6 3 1，则该二叉树的中根遍历是（ ）
A．4 2 1 7 5 3 6 B．2 4 1 7 5 3 6 C．4 2 1 7 5 6 3 D．2 4 1 5 7 3 6
2008普及
13、二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点编号，以下同），中根遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是（ ）
A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3 1
2007提高
12、已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为结点的编号，以下同), 后根遍历是4 6 5 2 7 3 1, 则该二叉树的可能的中根遍历是( )
A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 6 7 D. 4 2 5 6 1 7 3
2007普及
20、已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是（ ）
A．4 6 5 2 7 3 1 B．4 6 5 2 1 3 7 C．4 2 3 1 5 4 7 D．4 6 5 3 1 7 2
2006提高（同2006普及）
14、已知6个结点的二叉树的先根遍历是1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ ）
A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 3 1 5 4 6 D. 2 3 1 4 6 5
答案：
2010提高：B
2009提高：6B
2008提高：16ABD
2008普及：13B
2007提高：14ABD
2007普及：20A
2006提高：14BC