C
E
D
F
C
D
C

D
F
E F 二叉链表
E
二叉树
三叉链表
三叉链表的静态结构
root data parent lchild rchild 0 1 2 3 4 5 A B C D E F -1 0 1 1 3 3 1 2 -1 4 -1 -1 -1 3 -1 5 -1 -1
A
B C E D F
0
1 3 7 8 9 4 5
2 6
4. 二叉树的存储结构
顺序表示
1
2 4 5 6 3 7 7 4 8 2 5 9 1 3 6 10 9
8 9 10
1 2 3 4 5 6 7 8 910
完全二叉树 的顺序表示
1 2 3 4 0 5 6 7 8 0 0 0 0 910
一般二叉树 的顺序表示
链表表示
第六章 树和二叉树




1. 2. 3. 4. 5. 6.
树的定义和基本术语 二叉树 遍历二叉树与线索二叉树 树与森林 赫夫曼树 及其应用 二叉树的计数
6.1 树的定义和基本术语
树的定义
树是由 n (n 0) 个结点组成的有限集合。如果 n = 0， 称为空树；如果 n > 0，则 有且仅有一个特定的称之为根(Root)的结点，它只有直 接后继，但没有直接前驱； 当n > 1，除根以外的其它结点划分为 m (m >0) 个互不 相交的有限集 T1, T2 ,…, Tm，其中每个集合Ti本身又是一 棵树，并且称为根的子树(SubTree)。
特点
每个结点至多只有两棵非空子树（二叉树中 不存在度大于2的结点）
2.五种形态
L R L R
3. 性质
性质1 在二叉树的第 i 层上至多有 2i －1个结 点。(i 1) [证明用归纳法]
证明：当i=1时，只有根结点，2 i-1=2 0=1。 假设对所有j，i>j1，命题成立，即第j层上至多 有2 j-1 个结点。 由归纳假设第i-1 层上至多有 2i －2个结点。 由于二叉树的每个结点的度至多为2，故在第i层 上的最大结点数为第i-1层上的最大结点数的2倍， 即2* 2i －2= 2 i-1。
二叉链表的定义
typedef char TreeData; /*结点数据类型*/ typedef struct node /*结点定义*/ { TreeData data; struct node * lchild, * rchild; } BinTreeNode;
typedef BinTreeNode * BinTree; /*根指针*/
例如
A
A 只有根结点的树
B
C
D I J
E
K L
F
G H
M
有13个结点的树
其中：A是根；其余结点分成三个互不相交的子集， T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M}, T1,T2,T3都是根A的子树，且本身也是一棵树
树的基本术语
A
B E K 结点的度 树的度 叶结点 分支结点 L F C G H M D I J
若设二叉树的高度为h，则共有h层。除第 h 层外， 其它各层 (1 h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。
1 2 完全二叉树 4 5 6
3
7 1
8 9 10 11 12 1 2 4 5 6 7 3) 个结点的完全二叉树 的深度为log2 n ＋1
1层
2层 3层 4层
树的深度 有序树 无序树 森林 height =4
子女 双亲 兄弟
祖先 子孙 结点层次
6.2 二叉树 (Binary Tree)
1.定义
一棵二叉树是由 n (n 0) 个结点组成的有 限集合。如果 n = 0，称为空二叉树；如果 n > 0， 则由一个被称为根的结点和两棵互不相交的分 别称为根的左子树和右子树的二叉树组成。
若i = 1, 则 i 无双亲
若i > 1, 则 i 的双亲为i/2 若2*i< n, 则 i 的左子女为 2*i，若2*i+1 < n, 则 i 的右子 女为2*i+1 若结点编号i为奇数，且i!=1,则左兄弟结点i-1. 若结点编号i为偶数，且i!=n,则右兄弟结点为i+1. 结点i 所在层次为log 2 i +1
性质2 深度为 k 的二叉树至多有 2 k-1 个结点(k 1)。
证明：由性质1可见，深度为k的二叉树的 最大结点数为
(第i层上的最大结点数）
i 1
k
＝ 2 i 1 ＝20 + 21 + … + 2 k-1 = 2 k-1
i 1
k
性质3 对任何一棵二叉树T, 如果其叶结点数 为 n0, 度为2的结点数为 n2,则n0＝n2＋1. 证明：若度为1的结点有 n1 个，总结点个数为 n， 总边数为 e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 n – 1= e 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n0 = n2 + 1 n2 = n0 - 1
两种特殊形态的二叉树
定义1 满二叉树 (Full Binary Tree) 一棵深度为k且有2 k-1个结点的二叉树称为 满二叉树。(即每一层的结点数都达到最大值) 1 2 4 5 3
6
7
8 9 10 11 12 13 14 15
满二叉树
定义2 完全二叉树 (Complete Binary Tree)
lChild data rChild 含两个指针域的结点结构 lChild data parent rChild
含三个指针域的结点结构
data
lChild 二叉链表 rChild lChild
parent
data rChild 三叉链表
二叉树链表表示的示例
root A B B root A B root A
证明：设完全二叉树的深度为 h，则根据 性质2和完全二叉树的定义有 2h－1 - 1 < n 2h- 1或 2h－1 n < 2h 取对数 h－1 < log2n h，又h是整数， 因此有 h = log2 n ＋1
性质5 如将一棵有n个结点的完全二叉树自顶向
下，同一层自左向右连续给结点编号1, 2, …, n， 则有以下关系：