CHAPTER6--树和二叉树

安
徽 理
树的逻辑结构特点
工
大 学 1. 树中只有根结点没有前趋；
2. 除根外，其余结点都有且仅一个前趋；
3. 树的结点，可以有零个或多个后继；
4. 除根外的其它结点，都存在唯一条从
A
根到该结点的路径； 5. 树是一种分支结构。
B
C
D
E
FG H I J
KL
M
安
徽 理
树的应用
工
大 学
▪ 树可表示具有分支结构关系的对象
结论3知，x的右孩子应为2x+1，即2x+1=i，x=(i-1)/2。
故 i的双亲为└i/2┘ 证毕。
安
徽 理
6.2.3 二叉树的存储结构
工
大 学
❖ 顺序存储结构
所谓顺序存储结构，就是用一组连续的存储单元存储二
叉树的数据元素，结点在这个序列中的相互位置能反映出
结点之间的逻辑关系。 二叉树中结点之间的关系就是双亲
例1. 家族族谱
设某家庭有13个成员A、B、C、D、E、F、G、H、I、J
、K、L、M，他们之间的关系可如图所示的树表示。
例2. 单位行政机构的组织关系
A
B
C
D
E
FG H I J
KL
M
安
徽 理
树的应用
工
大 学
▪ 树是常用的数据组织形式
有些应用中数据元素之间并不存在分支结构关系，但是为
了便于管理和使用数据，将它们用树的形式来组织。
A
B
C
D
Ø
E
F
G H ØØØØI J
例如对于B结点而言： bt[2]的双亲为└1/2┘=1，即在bt[1]中 (为A)； 其左孩子在bt[2i]=bt[4]中(为D)； 其右孩子在bt[2i+1]=bt[5]中(为Ø )。

第六章 树和二叉树
￡6.1 树
￡6.1.1 树的定义 ￡6.1.2 基本术语
￡6.4 二叉树的遍历与线索化
￡6.4.1 二叉树的遍历 ￡6.4.2 二叉树的线索化 ￡6.5.2 森林与二叉树的转换 ￡6.5.3 树和森林的遍历
￡6.2 二叉树
￡6.2.1 二叉树的定义 ￡6.2.2 二叉树的性质
￡6. 3 二叉树的存储结构
Assign(T, cur_e, value); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：结点cur_e赋值为value。
Parent(T, cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。
InitBiTree (&T); 操作结果：构造空二叉树T。
DestroyBiTree (&T); 初始条件：二叉树T存在。 操作结果：销毁二叉树T。
CreateBiTree (&T, definition); 初始条件：definition给出二叉树T的定义。 操作结果：按definition构造二叉树T。
Value(T, e); 初始条件：二叉树T存在， e是T中某个结点。 操作结果：返回e的值。
Assign(T, &e, value); 初始条件：二叉树T存在， e是T中某个结点。 操作结果：结点e赋值为value。
Parent(T, e); 初始条件：二叉树T存在， e是T中某个结点。 操作结果：若e是T的非根结点，则返回它的双亲，否则函数值为“空”。
￡6.3.1 顺序存储结构 ￡6.3.2 链序存储结构
￡6.1 树
￡6.1.1 树的定义
（1）定义 树（Tree）：是n（n≥0）个结点的有限集。

2.孩子表示法 孩子表示法 在结点中设置指向每个孩子的指针域， 在结点中设置指向每个孩子的指针域，利用指针 指向该结点的所有孩子结点。 指向该结点的所有孩子结点。 大多采用按树的度设置结点的指针域的个数。 大多采用按树的度设置结点的指针域的个数。
9
6.1.4 树的存储结构
3.孩子兄弟表示法 孩子兄弟表示法 在结点中设置两个指针域， 在结点中设置两个指针域，一个指针域指向该结 点的第一个孩子，另一个指针域指向其右兄弟。 点的第一个孩子，另一个指针域指向其右兄弟。
2
6.1.1树的定义 树的定义
结点的度：结点所拥有子树的个数称为结点的度。 结点的度：结点所拥有子树的个数称为结点的度。 子树 称为结点的度 树的度：树中所有结点的度的最大值称为树的度。 最大值称为树的度 树的度：树中所有结点的度的最大值称为树的度。 叶结点：度为零的结点称为叶结点。也称终端结点 终端结点或 叶结点：度为零的结点称为叶结点。也称终端结点或叶 子 分支结点：度不为零的结点称为分支结点。也称非终端 分支结点：度不为零的结点称为分支结点。也称非终端 结点。除根结点以外，分支结点也称为内部结点。 结点。除根结点以外，分支结点也称为内部结点。 孩子结点和双亲结点： 孩子结点和双亲结点：树中一个结点的子树的根结点称 为孩子结点。该结点就称为孩子结点的双亲结点。 为孩子结点。该结点就称为孩子结点的双亲结点。 兄弟结点：具有同一双亲的孩子结点互为兄弟结点。 兄弟结点：具有同一双亲的孩子结点互为兄弟结点。 结点的祖先：从根到该结点所经分支上的所有结点， 结点的祖先：从根到该结点所经分支上的所有结点，称 为结点的祖先。 为结点的祖先。
17
6.2.2 二叉树的性质
性质4 具有n（ 性质 具有 （n>0）个结点的完全二叉树的深度 ）个结点的完全二叉树的深度h= log 2 n + 1 证明： 证明： 根据完全二叉树的定义可知深度为h-1层及以上的结点构成 根据完全二叉树的定义可知深度为 层及以上的结点构成 满二叉树，因此由性质2得深度为 得深度为h的完全二叉树满足 满二叉树，因此由性质 得深度为 的完全二叉树满足 n>2h-1-1和n≤2h-1 和 整理后得到 2h-1≤n<2h 不等式两边取对数， 不等式两边取对数，得 h-1≤log2n<h 由于h为正整数 为正整数， 由于 为正整数，因此 h= log 2 n + 1

或深度为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) 右子树为空