7
第5章 树
性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
k
2i1 2 k 1
i1
(5-1)
证明：性质1给出了二叉树每一层中含有的最大结点数， 深度为k的二叉树的结点总数至多为2k-1个。故命题成立。
8
第5章 树
性质3 对任何一棵二叉树，如果其终端结点数为n0，度 为2的结点数为n2，则n0=n2+1。
20
第5章 树
5.4 二叉树的遍历
5.4.1 二叉树的深度优先遍历 1. 先序遍历算法 先序遍历算法的遍历过程是，若二叉树非空，执行以下
操作： (1) 访问根结点； (2) 先序遍历左子树； (3) 先序遍历右子树。
21
第5章 树
图5-8 二叉树的遍历过程
22
第5章 树
图5-9 算法执行过程示意图
证明：设度为1的结点数为n1，则一棵二叉树的结点总 数为
n=n0+n1+n2
(5-2)
除根结点外，其余结点都有一个进入的分支(边)，设B
为分支总数，则n=B+1。又考虑到分支是由度为1和2的结点
发出的，故有B=2n2+n1，即
n=2n2+n1+1
比较式(5-1)与式(5-2)可得n0=n2+1。命题成立。
25
第5章 树
5.4.2 二叉树的广度优先遍历 二叉树的广度优先遍历又称为按层次遍历。这种遍历方
式是先遍历二叉树的第一层结点，然后遍历第二层结 点，……最后遍历最下层的结点。而对每一层的遍历是按从 左至右的方式进行的。
(5-3)

第5章 树
性质4 具有n个结点的完全二叉树的深度为 lbn + 1或
lb(n + 1)。
注：x表示不大于x的最大整数；x表示不小于x的最小
整数。
证明：由完全二叉树的定义可知，一个k层的完全二叉树
的前k-1层共有2k-1-1个结点，第k层上还有若干结点，所以结
点总数n满足关系：
2k-1-1＜n≤2k-1
17
第5章 树
图5-6 二叉树链式存储的结点结构
18
第5章 树
图5-7 链表存储结构
19
第5章 树
5.3.3 二叉树的建立 二叉树的建立是指如何在内存中建立二叉树存储结构。
二叉树顺序存储结构的建立比较简单，只须将二叉树各个结 点的(信息)值按原有的逻辑关系送入相应的向量单元中即可。
建立二叉树链式存储结构的算法有多种，它们依赖于按 照何种形式来输入二叉树的逻辑结构信息。一种常见的算法 是按照完全二叉树的层次顺序，依次输入结点信息来建立二 叉链表。对于一般二叉树，首先必须通过添加若干个虚结点 使其成为完全二叉树，然后建立二叉链表。
化方式，存储到一片连续的存储单元中。结点的顺序将反映 出结点之间逻辑关系。
11
第5章 树
图5-4 完全二叉树的结点编号
12
第5章 树
表 5-1 完全二叉树的顺序存储
编号 0 1 2 3 4 5 6 7 8 9 10
结点值
ABCDE FGH I J
H8
图5
13
第5章 树
图5-5和表5-2给出了一般二叉树构成完全二叉树并用顺 序存储结构存储的示例。其中方形结点为虚结点，并用符号 @表示结点值。
5
第5章 树
图5-3 满二叉树、完全二叉树和一般二叉树
6
第5章 树
性质1 在二叉树的第i层上至多有2i-1个结点(i≥1)。 证明：可用数学归纳法予以证明。 当i=1时，有2i-1=20=1，同时第一层上只有一个根结点， 故命题成立。 设当i=k时成立，即第k层上至多有2k-1个结点。 当i=k+1时，由于二叉树的每个结点至多有两个孩子， 因此第k+1层上至多有22k-1=2k个结点。故命题成立。
(2) 其余的结点可分成m个互不相交的有限集合T1，T2， …，Tm，其中每个集合又是一棵树，并称为根的子树。 将n=0时的空集合定义为空树(有的书上将n=1的集合定义为 空树)。
2
第5章 树
图5-1 学校的教学组织机构图
3
第5章 树
5.2 二 叉 树
定义2 二叉树是n(n≥0)个结点的有限集，它或为空树 (n=0)，或由一个根结点及两棵互不相交的、分别称做这个根 的左子树和右子树的二叉树构成。
23
第5章 树
2. 中序遍历算法 中序遍历算法的遍历过程是，若二叉树非空，执行以下 操作： (1) 中序遍历左子树； (2) 访问根结点； (3) 中序遍历右子树。
24
第5章 树
3. 后序遍历算法 后序遍历算法的遍历过程是，若二叉树非空，执行以下 操作： (1) 后序遍历左子树； (2) 后序遍历右子树； (3) 访问根结点。
14
第5章 树
图5-5 一般二叉树的结点编号
15
第5章 树
表 5-2 一般二叉树的顺序存储
编号 0 1 2 3 4 5 6 7
结点值
A B C @@@D
16
第5章 树
5.3.2 链式存储结构 链式存储是二叉树的一种自然链接方法。在一定的条件
下，链式存储可节省存储单元。因为二叉树的每个结点至多 有两个孩子，所以采用链式存储结构来存储二叉树时，每个 结点应至少包括三个域：结点数据域(data)、左孩子指针域 (lchild)和右孩子指针域(rchild)。二叉树链式存储结构的结点 逻辑结构如图5-6所示。
由二叉树的定义可以给出二叉树的五种基本形态，如图 5-2所示。当n=0时得到空二叉树；n=1时得到仅有一个根结 点的二叉树；当根结点的右子树为空时，得到一个仅有左子 树的二叉树；当根结点的左子树为空时，得到一个仅有右子 树的二叉树；当左、右子树均非空时，得到一般的二叉树。
4
第5章 树
图5-2 二叉树的基本形态
(5-4)
可推出2k-1≤n＜2k，取对数后可得k - 1≤lbn＜k。因为k为整数，
所以有k-1 = lbn，即k= lbn + 1。同样利用(5-3)式有2k-1＜
n+1≤2k，取对数得k-1＜lb(n+1)≤k，因而k= lb(n+1)。命题成
立。
10
第5章 树
5.3 二叉树的存储结构
5.3.1 顺序存储结构 顺序存储结构是将二叉树的所有结点，按照一定的顺序
第5章 树
第5章 树
5.1 树的基本概念 5.2 二叉树 5.3 二叉树的存储结构 5.4 二叉树的遍历 5.5 树和森林 5.6 线索二叉树 5.7 二叉树的应用
1
第5章 树
5.1 树的基本概念
定义1 树(Tree)是n(n≥0)个结点的有限集合T，它满足如 下两个条件：
(1) 有且仅有一个特定的称为根(Root)的结点，它没有前 趋；