有序树（ordered tree）：
4KL
M
每个结点的子女由左到右是有次序的；否则是无序树；
A
无序
A
B C 有序 C B
10
计算机学院 软件工程系
结点A、B、C的度分别为： 3、2、1
结点A的孩子：
A
B，C，D
结点B的孩子： E，F
B
C
树的度： E
F GH
3
KL
M
结点F，G为堂兄弟 结点A是结点F，G的祖先
KL
M
6
计算机学院 软件工程系
例5.1: Tree=(D, R)
D={Book, C1, C2, C3, S1.1, S1.2, S2.1, S2.2, S2.3, S2.1.1, S2.1.2 } R={<Book,C1>, <Book,C2>, <Book,C3>, <C1,S1.1>, <C1,S1.2>,
大家好
计算机学院 软件工程系
第4章 树与二叉树
树的概念 二叉树 二叉树遍历 线索化二叉树 树与森林 Huffman树
2
计算机学院 软件工程系
树形结构是一种非线性结构，应用十分广泛。 如：行政机构、磁盘目录、家谱等
内蒙古大学
理工学院 计算机学院 生命科学学院 外国语学院 人文学院
数物电 学理子 系系系
叶子： K，L，F，G，M，I，J
结点I的双亲：
D
结点L的双亲：
D
E
结点B，C，D为兄弟 I J 结点K，L为兄弟
结点A的层次： 0 结点M的层次： 3
树的深度： 3
11
计算机学院 软件工程系
❖森林（Forest）: m(m≥ 0)棵互不相交的树的集合.
F
root
A
BC
D
E F GH I J
KL
M
证明：若设度为1的结点有 n1 个，总结点 个数为 n，总边数为 e，则根据二叉树的
定义，
n = n0 + n1 + n2 e = 2n2 + n1 = n - 1
因此，有 2n2 + n1 = n0 + n1 + n2 - 1
n2 = n0 - 1
n0 = n2 + 1
15
计算机学院 软件工程系
变形 2h < n+1 2h+1 取对数
h < log2(n+1) h+1 有 log2(n+1) = h+1
h = log2(n+1) -1
23-1 24-1
18
计算机学院 软件工程系
性质5 如将一棵有n个结点的完全二叉树自
<C2,S2.1>, <C2,S2.2>, <C2,S2.3>, <S2.1, S2.1.1>, <S2.1, S2.1.2>} Book
C1
C2
C3
S1.1
S1.2 S2.1 S2.2 S2.3
Chapter Section
S2.1.1 S2.1.2
Section
❖树是一种层次结构 （hierarchy structure） 7
计算机学院 软件工程系
❖基本术语：主要来源于家谱和树
双亲、子女（parent, child）：
若<a,b> R，则称a是b的双亲，b是a 的子女(孩子);
结点度（degree）： 结点所拥有的子女数； 叶（leaf）： 度为0的结点；
A
BC
D
分枝结点（branch node）： E 度大于0的结点；
[证明用数学归纳法] 性质2 深度为 k 的二叉树最多有 2k-1个结 点。(h ≥ 1)
[证明用求等比级数前k项和的公式] 20 + 21 + … + 2k-1 = 2k-1
14
计算机学院 软件工程系
性质3 对任何一棵二叉树, 如果其叶结点
有 n0 个, 度为2的非叶结点有 n2 个, 则有 n0＝n2＋1
计网计生环动生资英
算络算物境物物源语
机中中系系中工所系
系心心
心程
中
心
行政机构
日 汉历 哲 语 语史 学 系 系系 系
3
计算机学院 软件工程系
磁 盘 目 录
4
计算机学院 软件工程系
树和森林的概念
树的定义 ▪ 树是由 n (n ≥ 0) 个结点组成的有限集合。如果
n = 0，称为空树；如果 n > 0，则 ❖有一个特定的称之为根(root)的结点，它只有
• 叶结点仅在层次最大的两层出现 • 对任一结点，若其右子树的高度为l，则
其左子树的高度为l或l+1
17
计算机学院 软件工程系
性质4 具有 n (n 0) 个结点的完全二叉树 的高度为 log2(n+1) -1 证明：设完全二叉树的高度为 h，则有
2h - 1 < n 2h+1 - 1
上面h层结点数 包括第h层的最大结点数
4 KL
M
双亲在同层的非兄弟结点互称堂兄弟；
பைடு நூலகம்
9
计算机学院 软件工程系
祖先、子孙（ancestor）：
一个结点是它所有子树中的结点的祖先,这些结点是它的子孙;
路径（path）：
1
A
是一结点序列n1,n2,n3,…,nk，
并且前1个结点是后1个结
2B C D
点的双亲；它的长度是k-1; 3 E F G H I J
12
计算机学院 软件工程系
二叉树 (Binary Tree)
二叉树的定义
一棵二叉树是结点的一个有限集合， 该集合或者为空，或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不 相交的二叉树组成。
L
R
LR
二叉树的五种不同形态
13
计算机学院 软件工程系
二叉树的性质
性质1 若二叉树的层次从1开始, 则在二叉 树的第 i 层最多有 2i -1个结点。(i ≥ 1)
直接后继，但没有直接前驱； ❖除根以外的其他结点划分为 m (m ≥ 0) 个 互
不相交的有限集合T0, T1, …, Tm-1，每个集合 又是一棵树，并且称之为根的子树。
5
计算机学院 软件工程系
树的特点
每棵子树的根结点有且仅有一个直接前 驱，但可以有0个或多个直接后继。
A
BC
D
E F GH I J
定义1 满二叉树 (Full Binary Tree) 定义2 完全二叉树 (Complete Binary Tree)
若设二叉树的高度为h，则共有h+1层。 除第 h 层外，其它各层 (0 h-1) 的结点数 都达到最大个数，第 h 层从右向左连续缺 若干结点，这就是完全二叉树。(特点)
16
计算机学院 软件工程系
F GH I J
树的度：树中最大的结点度； K L
M
8
计算机学院 软件工程系
结点所在的层次（level）：
根在第1层，其它任一结点所在的层是其双亲的层加1；
深度或高（depth）：
1
A
结点所在的层次的最大层数；
2B
C
D
兄弟（sibling)：
具有同一双亲的结点互称兄弟；3 E F G H I J
堂兄弟（cousin）：
