1
第 7章 树和二叉树 （ Tree & Binary Tree）
7.1 树
7.2 二叉树
7.3 二叉树的设计与实现
7.4 遍历二叉树和线索二叉树
7.5 赫夫曼树及其应用
7.6 树与二叉树的转换
特点,非线性结构，一个直接前驱，但可能有多个
直接后继。 （一对多或 1:n）
2
7.1 树
7.1.1 树的定义
注 1,树的定义具有 递归性,即“树中还有树”。
树是由 n(n≥0 )个结点组成的有限集合 T。 n=0的树称为空
树；对 n>0的树，有,(1)仅有 一个特殊的结点称为 根结点,根
结点没有前驱结点； (2)当 n>1时，除根结点外其余的结点分
为 m(m>0)个 互不相交 的有限集合 T1,T2,…, Tm，其中每个集
合 Ti本身又是一棵结构和树类似的子树。
3
7.1.2 若干术语
—— 即上层的那个结点 (直接前驱 )
—— 即下层结点的子树的根 (直接后继 )
—— 同一双亲下的同层结点（孩子之间互称兄弟）
—— 即从根到该结点所经分支的所有结点
—— 即该结点下层子树中的任一结点
A
B C
GE I
D
HF J
FLK
根
叶子结点
森林
有序树
无序树
—— 即根结点 (没有前驱 )
—— 即终端结点 (没有后继 )
—— 指 m棵不相交的树的集
合 (例如删除 A后的子树个数 )
双亲结点
孩子结点
兄弟结点
祖先结点
子孙结点
—— 结点各子树从左至右有序，不能互换（左为第一）
—— 结点各子树可互换位置。
图 7.1
4
—— 即树的数据元素
—— 结点挂接的子树数
结点
结点的度
结点的层次
终端结点
分支结点
树的度
树的深度
(或高度 )
A
B C
GE I
D
HF J
FLK
—— 从根到该结点的层数（根结点算第一层）
—— 即度为 0的结点，即叶子
—— 即度不为 0的结点（也称为内部结点）
—— 所有结点度中的最大值（ Max{各结点的度 }）
—— 指所有结点中最大的层数（ Max{各结点的层次 }）
问,右上图中的结点数＝ ；树的度＝ ；树的深度＝13 3 4
（有几个直接后继就是几度，亦称“次数”）
5
7.1.3 树的抽象数据类型
数据集合, 树的结点集合，每个结点由数据元素和构造数
据元素之间关系的指针组成。
操作集合,
(1)创建树 MakeTree(T)
(2)撤消树 DestroyTree(T)
(3)查找树中当前结点的双亲结点 Parent(T,curr)
(4)查找树中当前结点的左孩子结点 LeftChild(T,curr)
(5)查找树中当前结点的右孩子结点 RightSibling(T,curr)
(6)遍历树 Traverse(T,Visit( ))
6
7.1.4 树的存储结构
树的结点之间的逻辑关系主要有双亲 -孩子关系，
兄弟关系。因此，从结点之间的逻辑关系分，树的存
储结构主要有,双亲表示法、孩子表示法、双亲孩子
表示法和孩子兄弟表示法 四种组合。
7
A -1
B 0
C 0
D 1
E 1
F 1
G 2
H 3
A
B C
GE
D
HF
1、双亲表示法
d p
0
1
2
3
4
5
6
(a)一棵树 （ b)仿真指针的双亲表示法存储结构
图 7.2 树的双亲表示法存储结构
8
0 0A
0 0C0 0B
1 1E 1 1F 1 1G0 0D
1 1I1 1H
2、孩子表示法
图 7.3 树的孩子法存储结构
9
最简单的树 ——— 二叉树
先研究最简单、最有规律的树，然
后设法把一般的树转化为简单树。
解决思路：
从上面看出，树的操作实现比较复杂。
补充：树的 5种表示法：
?图形表示法
?嵌套集合表示法
?广义表表示法
?凹入表示法
?左孩子－右兄弟表示法
11
图形表示法
教师 学生 其他人员
2001级 2002级 2003级 2004级
……
西安石油大学
计算机系电信系 自控系 ……
叶子
根
子树
12
嵌套集合表示法
13
( A ( B ( E ( K,L ),F ),C ( G ),D ( H ( M ),I,J ) )
约定：
根 作为由子树森林组成的 表的名字写在表的左边
广义表表示法
14
凹入表示法
又称目录表示法
15
data link 1 link 2,.,link n...
树结点的结构：
困惑, 构造树的结点时
应当开多少个链域?
16
A
B C D
E F G H I J
K L Mdata
左孩子 右兄弟
左孩子－右兄弟表示法
多叉树转为
了二叉树
17
7.2 二叉树
为何要重点研究每结点最多只有两个, 叉, 的树？
? 二叉树的结构最简单，规律性最强；
? 可以证明，所有树都能转为唯一对应的二叉树，
不失一般性。
7.2.1 二叉树的定义
7.2.2 二叉树的性质
7.2.3 二叉树的存储结构
18
7.2.1 二叉树的定义
一、二叉树,是 n（ n≥0）个结点的有限集合。 n=0的树称为
空二叉树； n>0的二叉树由一个根结点以及两棵互不相
交的、分别称为 左子树和右子树 的二叉树组成 。
逻辑结构,一对二（ 1:2）
基本特征,
① 每个结点最多只有两棵子树（不存在度大于 2的结点）；
② 左子树和右子树 次序不能颠倒 。
问：具有 3个结点的二叉树可能有几种不同形态？ 有 5种
基本形态：
一般
的树
有几
种？
19
二、满二叉树
在一棵二叉树中，如果所有分支结点都
存在左子树和右子树，并且所有叶子结点都
在同一层上，这样的二叉树称为满二叉树。
(一棵深度为 k((k≥ -1)且有 2k+1-1个结点的
二叉树称为满二叉树。 )
三、完全二叉树 图 7.4
如果一棵深度为 k，有 n个结点的二叉树
中各结点能够与深度为 k的顺序编号的满二叉
树从 1到 n标号的结点相对应的二叉树称为完
全二叉树。
特点,
(1)所有的叶结点都出现在第 k层或 k－ 1层。 图 7.5
(2)若任一结点，如果其右子树的最大层次为 i，则其左子树的
最大层次为 i或 i＋ 1。
a
b
d
c
e f g
1
2 3
5 64
20
三、满二叉树与完全二叉树的区别
满二叉树是叶子一个也不少的树，而完全二叉树虽然前
k-1层是满的，但最底层却允许在右边缺少连续若干个结点。
满二叉树是完全二叉树的一个特例。
四、为何要研究这两种特殊形式？
因为它们在顺序存储方式下可以复原。
21
7.2.2 二叉树的抽象数据类型
数据集合,二叉树的结点集合，每个结点由数据元素和构造数
据元素之间关系的指针组成。
操作集合：
(1)创建二叉树 MakeTree(T)
(2)撤消二叉树 DestroyTree(T)
(3)左插入结点 InsertLeftNode(curr,x)
(4)右插入结点 InsertRightNode(curr,x)
(5)左删除子树 DeleteLeftTree(curr)
(6)右删除子树 DeleteRightTree(curr)
(7)遍历二叉树 Traverse(T,Visit())
22
7.2.3 二叉树的性质
讨论 1：第 i层的结点数最多是多少？ (i≥0)
（利用二进制性质可轻松求出）
性质 1:在一棵非空二叉树的第 i层上至多有 2i个结点（ i≥ 0）。
性质 2:深度为 k的二叉树至多有 2k+1-1个结点 (k≥ -1)。
再提问：第 i层上至少有 个结点？0
讨论 2：深度为 k(k≥ -1)的二叉树，最多有多少个结点？
(利用二进制性质可轻松求出）
2i个
2k+1-1
个
23
性质 3,对于任何一棵非空的二叉树，若度为 2的结点
数有 n2个，则叶子数（ n0） 必定为 n2＋ 1 （即 n0=n2+1）
证明：
∵ 二叉树中全部结点数 n＝ n0+n1+n2(叶子数＋ 1度结点数＋ 2度结点数 )
又 ∵ 二叉树中全部结点数 n＝ B+1 ( 总分支数＋根结点 )
（ 除根结点外, 每个结点必有一个直接前趋, 即一个分支 ）
而 总分支数 B=n1+2n2 (1度结点必有 1个直接后继, 2度结点必有 2个 )
三式联立可得,n0+n1+n2= n1+2n2 +1,即 n0=n2+1
叶子数＝ 2度结点数＋ 1
讨论 3：二叉树的叶子数和度为 2的结点数之间有关系吗？
24
性质 4,具有 n个结点的完全二叉树的深度 k必为 ?log2(n+1)?-1
(假定 k为 0时表示此二叉树仅有根结点）
证明,根据性质 2,深度为 k的二叉树最多只有 2k+1-1个结点,
且完全二叉树的定义是与同深度的满二叉树前面编号相同, 即
它的总结点数 n位于 k层和 k-1层满二叉树容量之间,
即 2(k-1)+1-1<n≤ 2k+1-1,移项, 有 2k<n+1≤ 2k+1
对不等式求对数, 有 k<log2(n+1)≤k+ 1 因为 k是整数, 所以
k=?log2(n+1)?-1
对于两种特殊形式的二叉树（ 满二叉树和完全二叉树 ），还
特别具备以下 2个性质：
25
性质 5:对于一棵有 n个结点的完全二叉树的结点按照从上至下
和从左至右的顺序对所有结点从 0开始顺序编号,则对于序号
为 i的结点 (0≤i≤n),有：
(1)如果 i=0，则结点 i无双亲，是二叉树的根；如果 i>0，则
其双亲是结点 (i-1)/2(“/”表示整除）。
(2)如果 2i+1≥ n，则结点 i为叶子结点，无左孩子；否则，
其左孩子是结点 2i+1。
(3)如果 2i＋ 2≥ n，则结点 i无右孩子；否则，其右孩子是结
点 2i＋ 2。
可根据归纳法证明。
26
小结
7.1 树的基本概念
7.2 二叉树
二叉树的概念
两种特殊的二叉树
二叉树的性质
第 7章 树和二叉树 （ Tree & Binary Tree）
7.1 树
7.2 二叉树
7.3 二叉树的设计与实现
7.4 遍历二叉树和线索二叉树
7.5 赫夫曼树及其应用
7.6 树与二叉树的转换
特点,非线性结构，一个直接前驱，但可能有多个
直接后继。 （一对多或 1:n）
2
7.1 树
7.1.1 树的定义
注 1,树的定义具有 递归性,即“树中还有树”。
树是由 n(n≥0 )个结点组成的有限集合 T。 n=0的树称为空
树；对 n>0的树，有,(1)仅有 一个特殊的结点称为 根结点,根
结点没有前驱结点； (2)当 n>1时，除根结点外其余的结点分
为 m(m>0)个 互不相交 的有限集合 T1,T2,…, Tm，其中每个集
合 Ti本身又是一棵结构和树类似的子树。
3
7.1.2 若干术语
—— 即上层的那个结点 (直接前驱 )
—— 即下层结点的子树的根 (直接后继 )
—— 同一双亲下的同层结点（孩子之间互称兄弟）
—— 即从根到该结点所经分支的所有结点
—— 即该结点下层子树中的任一结点
A
B C
GE I
D
HF J
FLK
根
叶子结点
森林
有序树
无序树
—— 即根结点 (没有前驱 )
—— 即终端结点 (没有后继 )
—— 指 m棵不相交的树的集
合 (例如删除 A后的子树个数 )
双亲结点
孩子结点
兄弟结点
祖先结点
子孙结点
—— 结点各子树从左至右有序，不能互换（左为第一）
—— 结点各子树可互换位置。
图 7.1
4
—— 即树的数据元素
—— 结点挂接的子树数
结点
结点的度
结点的层次
终端结点
分支结点
树的度
树的深度
(或高度 )
A
B C
GE I
D
HF J
FLK
—— 从根到该结点的层数（根结点算第一层）
—— 即度为 0的结点，即叶子
—— 即度不为 0的结点（也称为内部结点）
—— 所有结点度中的最大值（ Max{各结点的度 }）
—— 指所有结点中最大的层数（ Max{各结点的层次 }）
问,右上图中的结点数＝ ；树的度＝ ；树的深度＝13 3 4
（有几个直接后继就是几度，亦称“次数”）
5
7.1.3 树的抽象数据类型
数据集合, 树的结点集合，每个结点由数据元素和构造数
据元素之间关系的指针组成。
操作集合,
(1)创建树 MakeTree(T)
(2)撤消树 DestroyTree(T)
(3)查找树中当前结点的双亲结点 Parent(T,curr)
(4)查找树中当前结点的左孩子结点 LeftChild(T,curr)
(5)查找树中当前结点的右孩子结点 RightSibling(T,curr)
(6)遍历树 Traverse(T,Visit( ))
6
7.1.4 树的存储结构
树的结点之间的逻辑关系主要有双亲 -孩子关系，
兄弟关系。因此，从结点之间的逻辑关系分，树的存
储结构主要有,双亲表示法、孩子表示法、双亲孩子
表示法和孩子兄弟表示法 四种组合。
7
A -1
B 0
C 0
D 1
E 1
F 1
G 2
H 3
A
B C
GE
D
HF
1、双亲表示法
d p
0
1
2
3
4
5
6
(a)一棵树 （ b)仿真指针的双亲表示法存储结构
图 7.2 树的双亲表示法存储结构
8
0 0A
0 0C0 0B
1 1E 1 1F 1 1G0 0D
1 1I1 1H
2、孩子表示法
图 7.3 树的孩子法存储结构
9
最简单的树 ——— 二叉树
先研究最简单、最有规律的树，然
后设法把一般的树转化为简单树。
解决思路：
从上面看出，树的操作实现比较复杂。
补充：树的 5种表示法：
?图形表示法
?嵌套集合表示法
?广义表表示法
?凹入表示法
?左孩子－右兄弟表示法
11
图形表示法
教师 学生 其他人员
2001级 2002级 2003级 2004级
……
西安石油大学
计算机系电信系 自控系 ……
叶子
根
子树
12
嵌套集合表示法
13
( A ( B ( E ( K,L ),F ),C ( G ),D ( H ( M ),I,J ) )
约定：
根 作为由子树森林组成的 表的名字写在表的左边
广义表表示法
14
凹入表示法
又称目录表示法
15
data link 1 link 2,.,link n...
树结点的结构：
困惑, 构造树的结点时
应当开多少个链域?
16
A
B C D
E F G H I J
K L Mdata
左孩子 右兄弟
左孩子－右兄弟表示法
多叉树转为
了二叉树
17
7.2 二叉树
为何要重点研究每结点最多只有两个, 叉, 的树？
? 二叉树的结构最简单，规律性最强；
? 可以证明，所有树都能转为唯一对应的二叉树，
不失一般性。
7.2.1 二叉树的定义
7.2.2 二叉树的性质
7.2.3 二叉树的存储结构
18
7.2.1 二叉树的定义
一、二叉树,是 n（ n≥0）个结点的有限集合。 n=0的树称为
空二叉树； n>0的二叉树由一个根结点以及两棵互不相
交的、分别称为 左子树和右子树 的二叉树组成 。
逻辑结构,一对二（ 1:2）
基本特征,
① 每个结点最多只有两棵子树（不存在度大于 2的结点）；
② 左子树和右子树 次序不能颠倒 。
问：具有 3个结点的二叉树可能有几种不同形态？ 有 5种
基本形态：
一般
的树
有几
种？
19
二、满二叉树
在一棵二叉树中，如果所有分支结点都
存在左子树和右子树，并且所有叶子结点都
在同一层上，这样的二叉树称为满二叉树。
(一棵深度为 k((k≥ -1)且有 2k+1-1个结点的
二叉树称为满二叉树。 )
三、完全二叉树 图 7.4
如果一棵深度为 k，有 n个结点的二叉树
中各结点能够与深度为 k的顺序编号的满二叉
树从 1到 n标号的结点相对应的二叉树称为完
全二叉树。
特点,
(1)所有的叶结点都出现在第 k层或 k－ 1层。 图 7.5
(2)若任一结点，如果其右子树的最大层次为 i，则其左子树的
最大层次为 i或 i＋ 1。
a
b
d
c
e f g
1
2 3
5 64
20
三、满二叉树与完全二叉树的区别
满二叉树是叶子一个也不少的树，而完全二叉树虽然前
k-1层是满的，但最底层却允许在右边缺少连续若干个结点。
满二叉树是完全二叉树的一个特例。
四、为何要研究这两种特殊形式？
因为它们在顺序存储方式下可以复原。
21
7.2.2 二叉树的抽象数据类型
数据集合,二叉树的结点集合，每个结点由数据元素和构造数
据元素之间关系的指针组成。
操作集合：
(1)创建二叉树 MakeTree(T)
(2)撤消二叉树 DestroyTree(T)
(3)左插入结点 InsertLeftNode(curr,x)
(4)右插入结点 InsertRightNode(curr,x)
(5)左删除子树 DeleteLeftTree(curr)
(6)右删除子树 DeleteRightTree(curr)
(7)遍历二叉树 Traverse(T,Visit())
22
7.2.3 二叉树的性质
讨论 1：第 i层的结点数最多是多少？ (i≥0)
（利用二进制性质可轻松求出）
性质 1:在一棵非空二叉树的第 i层上至多有 2i个结点（ i≥ 0）。
性质 2:深度为 k的二叉树至多有 2k+1-1个结点 (k≥ -1)。
再提问：第 i层上至少有 个结点？0
讨论 2：深度为 k(k≥ -1)的二叉树，最多有多少个结点？
(利用二进制性质可轻松求出）
2i个
2k+1-1
个
23
性质 3,对于任何一棵非空的二叉树，若度为 2的结点
数有 n2个，则叶子数（ n0） 必定为 n2＋ 1 （即 n0=n2+1）
证明：
∵ 二叉树中全部结点数 n＝ n0+n1+n2(叶子数＋ 1度结点数＋ 2度结点数 )
又 ∵ 二叉树中全部结点数 n＝ B+1 ( 总分支数＋根结点 )
（ 除根结点外, 每个结点必有一个直接前趋, 即一个分支 ）
而 总分支数 B=n1+2n2 (1度结点必有 1个直接后继, 2度结点必有 2个 )
三式联立可得,n0+n1+n2= n1+2n2 +1,即 n0=n2+1
叶子数＝ 2度结点数＋ 1
讨论 3：二叉树的叶子数和度为 2的结点数之间有关系吗？
24
性质 4,具有 n个结点的完全二叉树的深度 k必为 ?log2(n+1)?-1
(假定 k为 0时表示此二叉树仅有根结点）
证明,根据性质 2,深度为 k的二叉树最多只有 2k+1-1个结点,
且完全二叉树的定义是与同深度的满二叉树前面编号相同, 即
它的总结点数 n位于 k层和 k-1层满二叉树容量之间,
即 2(k-1)+1-1<n≤ 2k+1-1,移项, 有 2k<n+1≤ 2k+1
对不等式求对数, 有 k<log2(n+1)≤k+ 1 因为 k是整数, 所以
k=?log2(n+1)?-1
对于两种特殊形式的二叉树（ 满二叉树和完全二叉树 ），还
特别具备以下 2个性质：
25
性质 5:对于一棵有 n个结点的完全二叉树的结点按照从上至下
和从左至右的顺序对所有结点从 0开始顺序编号,则对于序号
为 i的结点 (0≤i≤n),有：
(1)如果 i=0，则结点 i无双亲，是二叉树的根；如果 i>0，则
其双亲是结点 (i-1)/2(“/”表示整除）。
(2)如果 2i+1≥ n，则结点 i为叶子结点，无左孩子；否则，
其左孩子是结点 2i+1。
(3)如果 2i＋ 2≥ n，则结点 i无右孩子；否则，其右孩子是结
点 2i＋ 2。
可根据归纳法证明。
26
小结
7.1 树的基本概念
7.2 二叉树
二叉树的概念
两种特殊的二叉树
二叉树的性质
