第六章课件二叉树

这里，若T为根指针，则遍历左右子树时，是分别遍历以 T->lchild 和T->rchild 为根指针旳子树。
因为各子树旳遍历和整个二叉树旳遍历方式相同，所以， 各子树旳遍历可递归调用二叉树旳遍历算法。
先序遍历递归算法如下：
void PreOrder ( BiTree *T) { if ( T )
设B为分支总数，则n=B+1 又：分支由度为1和度为2旳结点射出， B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1
两种特殊形式旳二叉树
满二叉树 —— 一棵深度为k且有2 k-个1结点旳二叉树
特点：每一层上旳结点数都是最大结点数
完全二叉树 —— 深度为k，有n个结点旳二叉树当且仅当其每一种结点 都与深度为k旳满二叉树中编号从1至n旳结点一一相应 特点： 叶子结点只可能在层次最大旳两层上出现 对任一结点，若其右分支下子孙旳最大层次为l，则其 左分支下子孙旳最大层次必为l 或l+1
D HJ M
I
C G
A
B E K
L F C G D H
M I J
(A (B(E(K , L) , F) , C(G) , D(H(M) , I , J)))
树和二叉树
6.1 树旳定义和基本术语 ☞ 6.2 二叉树
6.3 遍历二叉树 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树
6.2 二叉树
b cd
a f
g
eh i
j
6.3 遍历二叉树
6.3.1 遍历二叉树
☞ 6.3.2 遍历二叉树旳递归算法
6.3.3 遍历二叉树旳非递归算法 6.3.4 递归算法旳应用（3个算法）

或深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度 为k的完全二叉树。
其中 2k-1 ≦ n≦2k-1 。
完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特 例。
•完全二叉树的特点：
若完全二叉树的深度为k ，则所有的叶子结点都出现在第k层
或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左 子树的最大层次为l或l+1。
结点的层次：从根开始定义为第1层，根的孩子
v
为第二层……。
树的深度（高度）：树中结点的最大层数。
森林（forest）：是m（m ≥ 0）棵互不相交的树
的集合。
6.2 二叉树
6.2.1 二叉树的定义 1 二叉树的定义
二叉树(Binary tree)是n(n≥0)个结点的有限集 合。若n=0时称为空树，否则： ⑴ 有且只有一个特殊的称为树的根(Root)结点； ⑵ 若n>1时，其余的结点被分成为二个互不相
(a) 二叉链表结点
(b) 三叉链表结点
图6-7 链表结点结构形式
(2) 二叉树的链式存储形式
例有一棵一般的二叉树，如图6-8(a)所示。以二叉链表和三叉链表 方式存储的结构图分别如图6-8(b) 、 6-8(c)所示。
a b cd
T a⋀
b ⋀c ⋀ d
T a ⋀⋀
b ⋀c ⋀ d
交的子集T1,T2，分别称之为左、右子树，并 且左、右子树又都是二叉树。 由此可知，二叉树的定义是递归的。
2 二叉树的基本形态 二叉树有5种基本形态，如图6-3所示。
AA
A
A
(a) (b)
(c) (d)
(e)
(a) 空二叉树 (b) 单结点二叉树 (c) 右子树为空

Y
D
N
Y a<60 E
E
N
A
Y
a<60 N D
C B D EA
Y a<80
a<70 N C
N a<90 Y
N
B
A
6.6 树的表示
6.6.1 树的存储结构
孩子链 表
孩子兄 弟链表
6.6.2 树的遍历
A
B
C
D
树的先根遍历算法描述如 下：
访问根结点。
EFG
H
按照从左到右的次序 先根遍历根的每一棵
之和

二叉树的带权外路径长度
n1
WPL (wi li )
i0
哈夫曼树定义为带权外路径长度最短的二叉树。 哈夫曼树不唯一
构造哈夫曼树
1、根据给定的n个权值{w1，w2，……，wn}构成n棵二叉树的集 合F={T1，T2，……，Tn}，其中每棵二叉树Ti中都有一个权值为 wi的根结点，其左右子树均空。
子树。
I
J K L M 树的后根遍历算法描述如
下：
先序遍历：A B E F I
NO
GCDHJ KL NOM
按照从左到右的次序 后根遍历根的每一棵
子树。
后序遍历：E I F G B C J K N O L M H D A

访问根结点。
0 14 1
0
6 1
33
T;
8 01
4 A
0 2
41 2
CS
T : 00 ; : 01 A : 10 C : 110 S : 111
例 电文是{CAS;CAT;SAT;AT} 其编码 “11010111011101000011111000011000” 电文为“1101000” 译文只能是“CAT”

日
6
第六章 树
三、 树的相关术语 结点：一个数据元素及若干个指向其子树的分支。 结点的度：结点所拥有的子树的个数称为该结点的度。 树的度：树中结点度的最大值。下图中结点B、C、 D的度为2；树的度为2。 叶子结点：度为0的结点称为叶子结点，或者称为终 端结点。分支结点：度不为0的结点称为分支结点或 非终端结点。图中的结点H、I、J、F、G为叶子结点； 结点A、B、C，D、E为分支结点。 A
有如下的式子：
n = n0 + n1 + n2 e = 2n2 + n1 = n - 1
将两个式子结合有
应用数学 中的知识 证明
2n2 + n1 = n0 + n1 + n2 - 1 既 n0 = n2 + 1
2020年11月10
日
14
第六章 树
若设二叉树的高度为h，如果该二叉树的每一层都达
到结点的最大数，称为满二叉树(如下图(a))；若除第
2020年11月10
日
4
第六章 树
下图是一棵具有10个结点的树，即T＝{A，B，C，…，I， J}，结点A为树T的根结点，除根结点A之外的其余结点分 为两个不相交的集合：T1＝{B，D，H，I，J}和T2={C，F， G}，T1和T2构成了结点A的两棵子树，子树T1的根结点为 B，其余结点又分为两个不相交的集合：T11＝{D，H，I}， T12 ＝ {E ， J} 。 子 树 T2 以 C 为 根 结 点 ， 又可 划 分 为集 合 T21={F，G}。如此可继续向下分为更小的子树，直到每 棵子树只有一个根结点为止。 A
B
C
D
E
F
G
2020年1H1月10I J