第 6章 树与二叉树
6.1 树的概念和运算
6.2 二叉树
6.3 树和森林
6.4 树的典型应用
6.5 本章小结
6.1 树的概念和运算
树形结构是 线性结构的拓广 。
除了 首元 （ 唯一存在,在树形结构中称
为,根” 节点）没有前驱元素以外，树中其
他所有元素（ 节点 ）都有且只有一个直接前
驱元素（ 父 节点）；直接后继元素则没有限
制：没有直接后继元素的节点（ 叶 节点）可
以有多个；存在直接后继元素的节点，其直
接后继元素的个数也可以有多个。
6.1.1 树的定义与表示
? 树的定义,
树的 逻辑结构 可以这样描述：
树是包含 N(N>0)个节点的 有穷集合 D，
且在 D上定义了一个 关系 R，关系 R满足以
下条件：
(1) 有且仅有一个 节点 e0?D,它对于关系
R来说 没有前驱, 节点 e0称作树的 根 。
(2) 除节点 e0外, D中的每个节点对于关系
R来说都 有且仅有一个前驱 。
(3) 除节点 e0外的任何节点 e?S，都存在一
个节点序列 (e0,e1,…,em)，其中 e0就是树根，
且 em=e，有序对 <ei-1,ei>?R（ 1≤i≤m）。这
样的节点序列称为从 根到节点 e的一条路径 。
树的递归定义：
树是由一个或多个节点组成的有限集 T，
它满足下面两个条件：
(1)有一个特定的节点称之为 根 ;
(2)其余的节点分成 m(m≥ 0)个 互不相
交的有限集 T1,T2,…,Tm,其中每个集
合本身又是一棵 树, 称 T1,T2,…,Tm为
根的子树 。
递归是树的固有属性
树的表示：
体现树形结构中 分支 和 层次 的特性 。
A
B C D
E F G
H
B
G
F
H
D
E
C
A
A
B
C
D
E
F
H
G
( b ) 文式图表示方法( a ) 倒置的树形图表示方法 ( c ) 凹入表的表示方法
图6, 2 树形结构中分支与层次特性的表示
本书中描述 树形结构 的方式
6.1.2 树的基本术语
?节点
?节点的度
?叶子或终端节点
?非终端节点或分支节点
?内部节点
?树的度
?孩子
?双亲
?兄弟
?祖先
?子孙
?节点的层次
?树的深度或高度
?有序树
?无序树
?森林
6.1.3 树的 ADT
ADT Tree
{ 数据对象为 D:
D是具有相同特性的数据元素的集
合
数据间的关系 R:
(1) 若 D为空集,则称为空树 ;
(2) 若 D为非空集且仅含有一个数
据元素,则 R为空集,树只包含一个根节点 ;
允许空树（即树中
没有一个节点的树）
存在
(3) 若 D为非空集且含有不止一个数据元素,则
R={H},H是同时满足如下条目的二元关系,
(3.1) D中存在唯一的一个称为根的数据元素 r,
它在关系 H下无前驱 ;
(3.2) D-{r}?Ф,存在 D-{r} 的 一 个 划 分
D1,D2,…,Dm(m>0),对任意 j?k(1≤ j,k≤ m) 有
Dj∩ Dk=Ф,且对任意的 i(1≤ i≤ m),惟一存在数据元
素 xi∈ Di有 <r,xi>∈ H;
(3.3) 对应于 D-{r}的划分,H-
{<r,x1>,<r,x2>,…,<r,xm>}有惟一的一个划分
H1,H2,…,Hm(m>0),对任意 j?k(1≤ j,k≤ m)有
Hj∩ Hk=Ф,且对任意的 i(1≤ i≤ m),Hi是 Di上的二元
关系,(Di,{Hi})是一棵符合本定义的树,称为根 r的
子树。
几种基本操作,
treeCreate(&tree)
treeDestroy (&tree)
treeClear(&tree)
treeEmpty(tree)
treeWidth(tree)
创建一棵树 tree
销毁一棵已有的树
tree
创建一棵树 tree
判树是否为空
求树的度
treeDepth(tree)
treeRoot(tree)
treeInsert(&tree,elem)
treeDelete(&tree,elem)
求树的高度 (深度 )
求树的根
在树 tree中,按照某种规则
将元素 elem插入到树中合适
位置
在树 tree中,按照某种规则
将树中元素 elem删除
treeTraverse(tree,visit)
treeGetParent(tree,elem,&parent)
treeGetChild(tree,parent,order,&ch
ild)
遍历树 tree各元素，并用
visit代表的操作处理元素
数据
在树 tree中求节点 elem的
父节点，并将结果放入
parent中
说明,在树 tree中求节点 parent
的第 order个子节点，并将结果放
入 child中
treeSetChild(tree,parent,order,child)
}
在树 tree中设置节点
parent的第 order个子节点，
待设置的值已经放入 child
中
6.2 二叉树
6.2.1 二叉树的定义与基本运算
二叉树是一个集合 T；它可以是空集, 也可
以是一个由节点组成的有限集 。 同时, 集合 T具
有下列的性质：
(1) 如果 T是空集, 则称 T是空的二叉树 。
(2) 如果 T是有限集, 则 T由一个特定的, 称之为
根 的节点, 以及称为该根的两个互不相交的 左子
树 和 右子树 构成, 同时这两棵子树亦是 二叉树 。
递归定义
二叉树可以有 5种基本形态，
( a ) 空二叉树
( b ) 只含根结点二叉树 ( c ) 右子树为空的二叉树 ( d ) 左、右子树非空空的二叉树 ( e ) 左子树为空的二叉树
图6,3 二叉树的五种基本形态
root
root root root
?二叉树的基本运算
与树的基本运算相类似
详见二叉树的 ADT说明
6.2.2 二叉树的性质
? 性质 (1)：在二叉树的第 i层上至多有 2i-1
个节点（ i≥ 1）。
?性质 (2)：深度为 k的二叉树至多有 2k-1
个节点（ k ≥ 1）。
?性质 (3)：对任何一棵二叉树 T，如果其
叶节点数为 n0，度为 2的节点数为 n2，则
n0=n2+1。
特殊形态的二叉树：
完全二叉树和满二叉树。
满二叉树：
一棵深度为 k且有 2k-1个节点的二叉
树。
特点：每一层上的节点数都达到了最
大节点数。
完全二叉树：
（ 1）叶子节点只可能在层次最大的
两层上出现；
（ 2）对任一节点，若其右分支下的
子孙节点的最大层次为 k，则其左分支下
的子孙的最大层次不小于 k。
满二叉树是完全二叉树，但完全
二叉树不一定是满二叉树。
1
2
4 5
3
6 7
1
2
4 5
3
6
1
2
4 5
3
1
2
4
3
1
2
4
1
2
43
( b ) 完全二叉树( a ) 满二叉树 ( c ) 完全二叉树 ( d ) 完全二叉树 ( e ) 非完全二叉树 ( f ) 非完全二叉树
图6, 4 特殊形状的二叉树
3
5
完全二叉树的两个重要特性：
性质 (4)：具有 n个节点的完全
二叉树的深度为 ?log2n?+1。
性质 (5)：如果对一棵有 n个节点的完全二叉树 （ 其
深度为 ?log2n? +1） 的节点按层序编号 （ 从第 1
层到第 ?log2n? +1层, 每层从左到右 ）, 则对任
一节点 i（ 1≤ i≤ n）, 有：
① 如果 i = 1,则节点 i是二叉树的根, 无双
亲；如果 i >1,则其双亲 PARENT (i) 是节点
?i/2? 。
② 如果 2i > n,则节点 i无左孩子 （ 节点 i是
叶子节点 ） ；否则其左孩子 LCHILD(i)是节点 2i 。
③ 如果 2i+1>n，则节点 i无右孩子；否则其右
孩子 RCHILD(i) 是节点 2i+1。
6.2.3 二叉树的存储结构
? 顺序存储
以节点在向量中的相对位置来表示节点间
的关系。
不足：一般的二叉树也必须按完全二叉树
的形式来存储，势必会造成存储的浪费。
5
32
1
4
( a ) 二叉树T
∧22
∧1 1
4 ∧
∧5 ∧
3
4
5
∧3 ∧ ∧2
1
4 ∧
∧5 ∧
∧3 ∧
∧
( b ) 二叉树T 的单指针存储 ( c ) 二叉树T 的双指针存储 ( d ) 二叉树T 的三指针存储
图6.6 二叉树链式存储结构示例
root root root
? 链式存储
单叉链表 三叉链表
二叉链表
常用链式存储结构：二叉链表
6.2.4 二叉树操作的实现
? 遍历（周游）算法
深度优先遍历：
先序遍历：若二叉树为空, 则空操
作；否则
(1)访问根节点；
(2)先序遍历左子树；
(3)先序遍历右子树 。
中序遍历：若二叉树为空, 则空操作；
否则
(1)中序遍历左子树；
(2)访问根节点；
(3)中序遍历右子树 。
后序遍历：若二叉树为空, 则空操作；
否则
(1)后序遍历左子树；
(2)后序遍历右子树；
(3)访问根节点。
二叉树遍历的典型应用－－表达式树
cb
-a
*
cb
-a
*
cb
-a
*
cb
-a
*
(a)a*(b-c)的 表达式树T ( b ) 先序遍历表达式树T ( c ) 中序遍历表达式树T ( d ) 后序遍历表达式树T
图6,7 表达式树与三种遍历
先序遍历此二叉树, 得到的二叉树的
先序序列为,*a-bc；
中序遍历此二叉树, 得到该二叉树的
中序序列为,a*b-c；
后序遍历此二叉树，得到该二叉树的
后序序列为,abc-*；
前缀表示（波兰式）
后缀表示（逆波兰式）
中缀表示（中缀式）
非递归实现树的深度优先遍历
利用栈
非递归实现树的广度优先遍历
利用队列
?遍历算法 时间 复杂度,O(N)
?遍历算法 空间 复杂度：至多为 O(N)
6.3 树和森林
? 6.3.1 树的存储结构
三种典型的表示法：
第一种是 双亲表示法 。
第二种是孩子表示法 。
第三种是孩子兄弟表示法 。
R
L M N
P Q
W
R -1
L 0
M 0
N 0
P 1
Q 1
W 3
0
6
5
4
3
2
1
数组下标
数据域 父节点域
( a ) 树的逻辑结构 ( b ) 树的双亲表示法示例
data c 1 c Dc 2 ?
degree c 1 c dc 2 ?data
R
L
M ∧
N
P ∧
Q ∧
W ∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
3
2
0
1
0 0
0
R
L
M
N
P Q
W
root
root
节点的结构
节点的结构
( c ) 树的一种孩子表示法示例
( d ) 树的另一种孩子表示法示例
R
L
M ∧
N
P ∧
Q ∧
W ∧
0
6
5
4
3
2
1
数据域 子节点域
L M N ∧
P Q ∧
W ∧
R
L
M ∧
N
P ∧
Q ∧
W ∧
0
6
5
4
3
2
1
数据域 子节点域
L M N ∧
P Q ∧
W ∧
-1
0
0
0
1
1
3
父节点域
( e ) 树的孩子链表 ( e ) 树的带双亲的孩子链表
图6,8 树的双亲表示法与孩子表示法
R ∧
L
P∧ M∧
N ∧
Q ∧∧
W ∧∧
data nextSiblingfirstChild
节点的数据域
节点的下一个兄弟域节点的第一个孩子域
( a ) 树节点的存储结构 ( b ) 图6, 8 ( a ) 中的树对应的存储结构
图6,9 树的左孩子右兄弟存储结构
6.3.2 树、森林与二叉树的转换
?森林转换成二叉树
如果 F={T1,T2,…,Tm}是森林, 则按如下规
则转化成一棵二叉树 B=(root,lb,rb)。
① 若 F为空, 即 m=0,则 B为空二叉树；
② 若 F非空，即 m?0，则 B的根 root即为森
林中第一棵树的根 root(T1)； B的左子树 lb是从
T1中根节点的子树森林 F1={T11,T12,…,T1k}转化
而成的二叉树；其右子树 rb是从森林
F’={T2,T3,…,Tm}转化而成的二叉树。
A ∧
B∧ C E ∧∧
D ∧∧
A ∧
B∧
C
D ∧∧
E ∧∧
A ∧
B∧
C
E ∧∧D ∧∧
A
B C E
D
D E
B
A
C
树
二叉树
对应
存储 存储
解释解释
图6, 1 0 树与二叉树的对应关系示例
?二叉树转化成森林
如果 B=(root,lb,rb)是一棵二叉树,
则可按如下规则转化成森林
F={T1,T2,…,Tm}
① 若 B为空, 则 F为空；
② 若 B不空，则 F中第一棵树 T1的根
root(T1)即为二叉树 B的根 root； T1中根节
点的子树森林 F1是由 B的左子树 lb转换而成
的森林； F中除 T1之外其余树组成的森林
F’={T2,T3,…,Tm}是由 B的右子树 rb转换而
成的森林。
A
B E
E
A
B C D
F
G
D
B
A
C
E
G
F
D
C
G
F
树与二叉树对应
森林与二叉树对应
树根相连
图6.11 森林与二叉树的对应关系示例
6.3.3 树的遍历
? 树的遍历
先根（次序）遍历,先访问树的根
节点，然后按照从左至右的次序 先根遍
历 根的每棵子树
后根（次序） 遍历：先按照从左至右
的次序 后根遍历 每棵子树，然后访问根
节点。
?森林的两种遍历方法：
(1)先序遍历 森林
若森林非空, 则可按下述规则遍历之：
① 访问森林中第一棵树的根节点；
② 先序遍历第一棵树中根节点的子树森
林；
③ 先序遍历除去第一棵树之后的树构成
的森林。
(2)后序遍历森林
若森林非空, 则可按下述规则遍历之：
① 后序遍历森林中第一棵树的根节点的子
树森林；
② 访问第一棵树的根节点；
③ 按后根次序遍历除去第一棵树之后的其
余树构成的森林。
6.4 树的典型应用
? 6.4.1 回溯法中的解空间树与 0-1背
包问题
0-1背包问题,
给定 n种物品和一个背包 。 物品 i的重
量是 wi,其价值为 pi,背包的容量为 C。
问：应该如何选择装入背包的物品, 使
得装入背包中物品的总价值最大？
要求,对物品 i只有两种选择：要么全部
装入背包，要么全都不装入背包
借助树形结构组织问题的解空间，以便
能用回溯法搜索整个解空间。
A
B
D E
IH KJ
C
F G
ML ON
1
1
1 1 1 1
10
0
0
0 000
图6, 1 2 0 - 1 背包问题的解空间树( n = 3 )
从根结点
到叶节点
的一个路
径就对应
着解空间
的一个解
搜索最优解：回溯法
1,从开始节点（根节点）出发，以深
度优先方式搜索整个解空间。这个开始节点
成为活节点，同时也成为当前的扩展节点。
2,在当前扩展节点处，搜索向纵深方
向移至一个新节点。该新节点成为新的活节点，
并成为当前扩展节点。
3,如果在当前扩展节点处不能再向纵深
方向移动，则当前扩展节点就成为死节点。
往回移动（回溯）至最近的活节点处，
并使这个活节点成为当前扩展节点。
以这种工作方式递归地在解空间中搜索，
直至找到所要求的解或解空间中已无活节点时
为止。
注, 为了避免无效搜索，可使用剪枝
函数把不需要的子树剪去；使用限界函数剪去
得不到最优解的子树,从而提高回溯法的搜索
效率。
具体到 0-1背包问题：
预处理,按 各物品单位重量所包含的
价值从大到小进行排列物品。
设计预估函数，其返回值说明右子树中
是否存在一个比当前解更优的解决方案。以
此作为剪枝的依据。
预估函数的作用：
能够估计出最优解的上界。
0-1背包问题的回溯法效率分析：
预估函数需要 O(N)时间，其中 N为物
品种类的数量。在最坏情况下，有 O(2N)个
右子节点都需要进行预估，故求解 0-1背包
问题的回溯法时间复杂度为 O(N*2N)。
6.4.2 哈夫曼树与贪心算法
? 相关概念：
从树中一个节点到另一个节点之间
的分支构成这两个节点之间的路径；
路径上的分支数目称作路径长度。
考虑节点带权的树：
节点的带权路径长度为从该节点到树
根之间的路径长度与节点上权的乘积。
树的带权路径长度为树中所有叶子节点的
带权路径长度之和，记作：
)0,1(N
1
NklwW P L k
N
k
k ????? ?
?
11 4 23
11 4
2
3
2 3
11
4
(a)WPL=(11+4+3+2)*2=40 (b)WPL=(11+4)*3+3*2+2*1=53 (c)WPL=(2+3)*3+4*2+11*1=34
图6, 1 3 具有不同带权路径长度的二叉树
试构造一棵有 N个叶子结点的二叉树，
则其中带权路径长度 WPL最小的二叉树称作最
优二叉树或哈夫曼（ Huffman）树。
构造哈夫曼树思想：
(1)根据给定的 N个权值 {w1,w2,…,wN}
构成 N棵二叉树的集合 F ={T1,T2,…,TN}，
其中每棵二叉树 Ti中只有一个带权为 wi的根
节点，其左右子树均空；
(2)在 F中选取两棵根节点权值最小的
子树, 分别做为左右子树来构造一棵新的二
叉树, 且置新的二叉树的根节点的权值为其
左右子树上根节点的权值之和；
(3)在 F中删除这两棵树, 同时将新得到
的二叉树加入 F中；
(4)重复 (2),(3)，直到 F仅含一棵树
为止。
－－－－贪心算法
C D
A
B
A B DC
C D
A B
C D
B
A
11 4 3 2
3 2
11 4
11
4
3 2
4
3 2
11
5
9
5
9
5
20
C D
A
B
( a ) 初始集合含4 棵树 ( b ) 集合含3 棵树 ( c ) 集合含2 棵树 ( d ) 集合中只含1 棵树 ( e ) 哈夫曼树的前缀编码
1
1
1 0
0
0
A:0
B:10
C:110
D:111
图6, 1 4 哈夫曼树的构造过程及哈夫曼编码
贪心算法并不从整体最优的角度来考虑
问题。它所做出的选择只是在某种意义上的局
部最优选择。
?哈夫曼树应用：
哈夫曼编码 －－电文的 二进制前缀编码
6.5 本章小结
? 基本内容：
1,树的 基本概念
2,二叉树 的定义、性质和存储结构；
二叉树的遍历和线索化以及 遍历算法 的各
种描述形式；
3,树和森林 与二叉树的转换、树和
森林的遍历；
4.树的 典型应用 ； 回溯法 与 贪心算法 。
? 基本要求：
熟练掌握二叉树的 结构特性, 了解相
应的 证明方法 。
熟悉二叉树的各种 存储结构 的特点及
适用范围 。
熟练掌握各种 遍历策略 的递归算法,
了解遍历过程中, 栈, 的作用和状态, 而
且能灵活运用遍历算法实现二叉树的其他
操作 。 层次遍历 是按另一种搜索策略进行
的遍历 。
熟悉树的各种存储结构及其特点, 掌握树
和森林与二叉树的转换方法 。 掌握各种建立二
叉树和树的存储结构的方法 。
学会编写实现树的各种操作的算法 。
掌握建立哈夫曼编码的方法 。
学习并使用贪心算法与回溯法的思想 。
6.1 树的概念和运算
6.2 二叉树
6.3 树和森林
6.4 树的典型应用
6.5 本章小结
6.1 树的概念和运算
树形结构是 线性结构的拓广 。
除了 首元 （ 唯一存在,在树形结构中称
为,根” 节点）没有前驱元素以外，树中其
他所有元素（ 节点 ）都有且只有一个直接前
驱元素（ 父 节点）；直接后继元素则没有限
制：没有直接后继元素的节点（ 叶 节点）可
以有多个；存在直接后继元素的节点，其直
接后继元素的个数也可以有多个。
6.1.1 树的定义与表示
? 树的定义,
树的 逻辑结构 可以这样描述：
树是包含 N(N>0)个节点的 有穷集合 D，
且在 D上定义了一个 关系 R，关系 R满足以
下条件：
(1) 有且仅有一个 节点 e0?D,它对于关系
R来说 没有前驱, 节点 e0称作树的 根 。
(2) 除节点 e0外, D中的每个节点对于关系
R来说都 有且仅有一个前驱 。
(3) 除节点 e0外的任何节点 e?S，都存在一
个节点序列 (e0,e1,…,em)，其中 e0就是树根，
且 em=e，有序对 <ei-1,ei>?R（ 1≤i≤m）。这
样的节点序列称为从 根到节点 e的一条路径 。
树的递归定义：
树是由一个或多个节点组成的有限集 T，
它满足下面两个条件：
(1)有一个特定的节点称之为 根 ;
(2)其余的节点分成 m(m≥ 0)个 互不相
交的有限集 T1,T2,…,Tm,其中每个集
合本身又是一棵 树, 称 T1,T2,…,Tm为
根的子树 。
递归是树的固有属性
树的表示：
体现树形结构中 分支 和 层次 的特性 。
A
B C D
E F G
H
B
G
F
H
D
E
C
A
A
B
C
D
E
F
H
G
( b ) 文式图表示方法( a ) 倒置的树形图表示方法 ( c ) 凹入表的表示方法
图6, 2 树形结构中分支与层次特性的表示
本书中描述 树形结构 的方式
6.1.2 树的基本术语
?节点
?节点的度
?叶子或终端节点
?非终端节点或分支节点
?内部节点
?树的度
?孩子
?双亲
?兄弟
?祖先
?子孙
?节点的层次
?树的深度或高度
?有序树
?无序树
?森林
6.1.3 树的 ADT
ADT Tree
{ 数据对象为 D:
D是具有相同特性的数据元素的集
合
数据间的关系 R:
(1) 若 D为空集,则称为空树 ;
(2) 若 D为非空集且仅含有一个数
据元素,则 R为空集,树只包含一个根节点 ;
允许空树（即树中
没有一个节点的树）
存在
(3) 若 D为非空集且含有不止一个数据元素,则
R={H},H是同时满足如下条目的二元关系,
(3.1) D中存在唯一的一个称为根的数据元素 r,
它在关系 H下无前驱 ;
(3.2) D-{r}?Ф,存在 D-{r} 的 一 个 划 分
D1,D2,…,Dm(m>0),对任意 j?k(1≤ j,k≤ m) 有
Dj∩ Dk=Ф,且对任意的 i(1≤ i≤ m),惟一存在数据元
素 xi∈ Di有 <r,xi>∈ H;
(3.3) 对应于 D-{r}的划分,H-
{<r,x1>,<r,x2>,…,<r,xm>}有惟一的一个划分
H1,H2,…,Hm(m>0),对任意 j?k(1≤ j,k≤ m)有
Hj∩ Hk=Ф,且对任意的 i(1≤ i≤ m),Hi是 Di上的二元
关系,(Di,{Hi})是一棵符合本定义的树,称为根 r的
子树。
几种基本操作,
treeCreate(&tree)
treeDestroy (&tree)
treeClear(&tree)
treeEmpty(tree)
treeWidth(tree)
创建一棵树 tree
销毁一棵已有的树
tree
创建一棵树 tree
判树是否为空
求树的度
treeDepth(tree)
treeRoot(tree)
treeInsert(&tree,elem)
treeDelete(&tree,elem)
求树的高度 (深度 )
求树的根
在树 tree中,按照某种规则
将元素 elem插入到树中合适
位置
在树 tree中,按照某种规则
将树中元素 elem删除
treeTraverse(tree,visit)
treeGetParent(tree,elem,&parent)
treeGetChild(tree,parent,order,&ch
ild)
遍历树 tree各元素，并用
visit代表的操作处理元素
数据
在树 tree中求节点 elem的
父节点，并将结果放入
parent中
说明,在树 tree中求节点 parent
的第 order个子节点，并将结果放
入 child中
treeSetChild(tree,parent,order,child)
}
在树 tree中设置节点
parent的第 order个子节点，
待设置的值已经放入 child
中
6.2 二叉树
6.2.1 二叉树的定义与基本运算
二叉树是一个集合 T；它可以是空集, 也可
以是一个由节点组成的有限集 。 同时, 集合 T具
有下列的性质：
(1) 如果 T是空集, 则称 T是空的二叉树 。
(2) 如果 T是有限集, 则 T由一个特定的, 称之为
根 的节点, 以及称为该根的两个互不相交的 左子
树 和 右子树 构成, 同时这两棵子树亦是 二叉树 。
递归定义
二叉树可以有 5种基本形态，
( a ) 空二叉树
( b ) 只含根结点二叉树 ( c ) 右子树为空的二叉树 ( d ) 左、右子树非空空的二叉树 ( e ) 左子树为空的二叉树
图6,3 二叉树的五种基本形态
root
root root root
?二叉树的基本运算
与树的基本运算相类似
详见二叉树的 ADT说明
6.2.2 二叉树的性质
? 性质 (1)：在二叉树的第 i层上至多有 2i-1
个节点（ i≥ 1）。
?性质 (2)：深度为 k的二叉树至多有 2k-1
个节点（ k ≥ 1）。
?性质 (3)：对任何一棵二叉树 T，如果其
叶节点数为 n0，度为 2的节点数为 n2，则
n0=n2+1。
特殊形态的二叉树：
完全二叉树和满二叉树。
满二叉树：
一棵深度为 k且有 2k-1个节点的二叉
树。
特点：每一层上的节点数都达到了最
大节点数。
完全二叉树：
（ 1）叶子节点只可能在层次最大的
两层上出现；
（ 2）对任一节点，若其右分支下的
子孙节点的最大层次为 k，则其左分支下
的子孙的最大层次不小于 k。
满二叉树是完全二叉树，但完全
二叉树不一定是满二叉树。
1
2
4 5
3
6 7
1
2
4 5
3
6
1
2
4 5
3
1
2
4
3
1
2
4
1
2
43
( b ) 完全二叉树( a ) 满二叉树 ( c ) 完全二叉树 ( d ) 完全二叉树 ( e ) 非完全二叉树 ( f ) 非完全二叉树
图6, 4 特殊形状的二叉树
3
5
完全二叉树的两个重要特性：
性质 (4)：具有 n个节点的完全
二叉树的深度为 ?log2n?+1。
性质 (5)：如果对一棵有 n个节点的完全二叉树 （ 其
深度为 ?log2n? +1） 的节点按层序编号 （ 从第 1
层到第 ?log2n? +1层, 每层从左到右 ）, 则对任
一节点 i（ 1≤ i≤ n）, 有：
① 如果 i = 1,则节点 i是二叉树的根, 无双
亲；如果 i >1,则其双亲 PARENT (i) 是节点
?i/2? 。
② 如果 2i > n,则节点 i无左孩子 （ 节点 i是
叶子节点 ） ；否则其左孩子 LCHILD(i)是节点 2i 。
③ 如果 2i+1>n，则节点 i无右孩子；否则其右
孩子 RCHILD(i) 是节点 2i+1。
6.2.3 二叉树的存储结构
? 顺序存储
以节点在向量中的相对位置来表示节点间
的关系。
不足：一般的二叉树也必须按完全二叉树
的形式来存储，势必会造成存储的浪费。
5
32
1
4
( a ) 二叉树T
∧22
∧1 1
4 ∧
∧5 ∧
3
4
5
∧3 ∧ ∧2
1
4 ∧
∧5 ∧
∧3 ∧
∧
( b ) 二叉树T 的单指针存储 ( c ) 二叉树T 的双指针存储 ( d ) 二叉树T 的三指针存储
图6.6 二叉树链式存储结构示例
root root root
? 链式存储
单叉链表 三叉链表
二叉链表
常用链式存储结构：二叉链表
6.2.4 二叉树操作的实现
? 遍历（周游）算法
深度优先遍历：
先序遍历：若二叉树为空, 则空操
作；否则
(1)访问根节点；
(2)先序遍历左子树；
(3)先序遍历右子树 。
中序遍历：若二叉树为空, 则空操作；
否则
(1)中序遍历左子树；
(2)访问根节点；
(3)中序遍历右子树 。
后序遍历：若二叉树为空, 则空操作；
否则
(1)后序遍历左子树；
(2)后序遍历右子树；
(3)访问根节点。
二叉树遍历的典型应用－－表达式树
cb
-a
*
cb
-a
*
cb
-a
*
cb
-a
*
(a)a*(b-c)的 表达式树T ( b ) 先序遍历表达式树T ( c ) 中序遍历表达式树T ( d ) 后序遍历表达式树T
图6,7 表达式树与三种遍历
先序遍历此二叉树, 得到的二叉树的
先序序列为,*a-bc；
中序遍历此二叉树, 得到该二叉树的
中序序列为,a*b-c；
后序遍历此二叉树，得到该二叉树的
后序序列为,abc-*；
前缀表示（波兰式）
后缀表示（逆波兰式）
中缀表示（中缀式）
非递归实现树的深度优先遍历
利用栈
非递归实现树的广度优先遍历
利用队列
?遍历算法 时间 复杂度,O(N)
?遍历算法 空间 复杂度：至多为 O(N)
6.3 树和森林
? 6.3.1 树的存储结构
三种典型的表示法：
第一种是 双亲表示法 。
第二种是孩子表示法 。
第三种是孩子兄弟表示法 。
R
L M N
P Q
W
R -1
L 0
M 0
N 0
P 1
Q 1
W 3
0
6
5
4
3
2
1
数组下标
数据域 父节点域
( a ) 树的逻辑结构 ( b ) 树的双亲表示法示例
data c 1 c Dc 2 ?
degree c 1 c dc 2 ?data
R
L
M ∧
N
P ∧
Q ∧
W ∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
3
2
0
1
0 0
0
R
L
M
N
P Q
W
root
root
节点的结构
节点的结构
( c ) 树的一种孩子表示法示例
( d ) 树的另一种孩子表示法示例
R
L
M ∧
N
P ∧
Q ∧
W ∧
0
6
5
4
3
2
1
数据域 子节点域
L M N ∧
P Q ∧
W ∧
R
L
M ∧
N
P ∧
Q ∧
W ∧
0
6
5
4
3
2
1
数据域 子节点域
L M N ∧
P Q ∧
W ∧
-1
0
0
0
1
1
3
父节点域
( e ) 树的孩子链表 ( e ) 树的带双亲的孩子链表
图6,8 树的双亲表示法与孩子表示法
R ∧
L
P∧ M∧
N ∧
Q ∧∧
W ∧∧
data nextSiblingfirstChild
节点的数据域
节点的下一个兄弟域节点的第一个孩子域
( a ) 树节点的存储结构 ( b ) 图6, 8 ( a ) 中的树对应的存储结构
图6,9 树的左孩子右兄弟存储结构
6.3.2 树、森林与二叉树的转换
?森林转换成二叉树
如果 F={T1,T2,…,Tm}是森林, 则按如下规
则转化成一棵二叉树 B=(root,lb,rb)。
① 若 F为空, 即 m=0,则 B为空二叉树；
② 若 F非空，即 m?0，则 B的根 root即为森
林中第一棵树的根 root(T1)； B的左子树 lb是从
T1中根节点的子树森林 F1={T11,T12,…,T1k}转化
而成的二叉树；其右子树 rb是从森林
F’={T2,T3,…,Tm}转化而成的二叉树。
A ∧
B∧ C E ∧∧
D ∧∧
A ∧
B∧
C
D ∧∧
E ∧∧
A ∧
B∧
C
E ∧∧D ∧∧
A
B C E
D
D E
B
A
C
树
二叉树
对应
存储 存储
解释解释
图6, 1 0 树与二叉树的对应关系示例
?二叉树转化成森林
如果 B=(root,lb,rb)是一棵二叉树,
则可按如下规则转化成森林
F={T1,T2,…,Tm}
① 若 B为空, 则 F为空；
② 若 B不空，则 F中第一棵树 T1的根
root(T1)即为二叉树 B的根 root； T1中根节
点的子树森林 F1是由 B的左子树 lb转换而成
的森林； F中除 T1之外其余树组成的森林
F’={T2,T3,…,Tm}是由 B的右子树 rb转换而
成的森林。
A
B E
E
A
B C D
F
G
D
B
A
C
E
G
F
D
C
G
F
树与二叉树对应
森林与二叉树对应
树根相连
图6.11 森林与二叉树的对应关系示例
6.3.3 树的遍历
? 树的遍历
先根（次序）遍历,先访问树的根
节点，然后按照从左至右的次序 先根遍
历 根的每棵子树
后根（次序） 遍历：先按照从左至右
的次序 后根遍历 每棵子树，然后访问根
节点。
?森林的两种遍历方法：
(1)先序遍历 森林
若森林非空, 则可按下述规则遍历之：
① 访问森林中第一棵树的根节点；
② 先序遍历第一棵树中根节点的子树森
林；
③ 先序遍历除去第一棵树之后的树构成
的森林。
(2)后序遍历森林
若森林非空, 则可按下述规则遍历之：
① 后序遍历森林中第一棵树的根节点的子
树森林；
② 访问第一棵树的根节点；
③ 按后根次序遍历除去第一棵树之后的其
余树构成的森林。
6.4 树的典型应用
? 6.4.1 回溯法中的解空间树与 0-1背
包问题
0-1背包问题,
给定 n种物品和一个背包 。 物品 i的重
量是 wi,其价值为 pi,背包的容量为 C。
问：应该如何选择装入背包的物品, 使
得装入背包中物品的总价值最大？
要求,对物品 i只有两种选择：要么全部
装入背包，要么全都不装入背包
借助树形结构组织问题的解空间，以便
能用回溯法搜索整个解空间。
A
B
D E
IH KJ
C
F G
ML ON
1
1
1 1 1 1
10
0
0
0 000
图6, 1 2 0 - 1 背包问题的解空间树( n = 3 )
从根结点
到叶节点
的一个路
径就对应
着解空间
的一个解
搜索最优解：回溯法
1,从开始节点（根节点）出发，以深
度优先方式搜索整个解空间。这个开始节点
成为活节点，同时也成为当前的扩展节点。
2,在当前扩展节点处，搜索向纵深方
向移至一个新节点。该新节点成为新的活节点，
并成为当前扩展节点。
3,如果在当前扩展节点处不能再向纵深
方向移动，则当前扩展节点就成为死节点。
往回移动（回溯）至最近的活节点处，
并使这个活节点成为当前扩展节点。
以这种工作方式递归地在解空间中搜索，
直至找到所要求的解或解空间中已无活节点时
为止。
注, 为了避免无效搜索，可使用剪枝
函数把不需要的子树剪去；使用限界函数剪去
得不到最优解的子树,从而提高回溯法的搜索
效率。
具体到 0-1背包问题：
预处理,按 各物品单位重量所包含的
价值从大到小进行排列物品。
设计预估函数，其返回值说明右子树中
是否存在一个比当前解更优的解决方案。以
此作为剪枝的依据。
预估函数的作用：
能够估计出最优解的上界。
0-1背包问题的回溯法效率分析：
预估函数需要 O(N)时间，其中 N为物
品种类的数量。在最坏情况下，有 O(2N)个
右子节点都需要进行预估，故求解 0-1背包
问题的回溯法时间复杂度为 O(N*2N)。
6.4.2 哈夫曼树与贪心算法
? 相关概念：
从树中一个节点到另一个节点之间
的分支构成这两个节点之间的路径；
路径上的分支数目称作路径长度。
考虑节点带权的树：
节点的带权路径长度为从该节点到树
根之间的路径长度与节点上权的乘积。
树的带权路径长度为树中所有叶子节点的
带权路径长度之和，记作：
)0,1(N
1
NklwW P L k
N
k
k ????? ?
?
11 4 23
11 4
2
3
2 3
11
4
(a)WPL=(11+4+3+2)*2=40 (b)WPL=(11+4)*3+3*2+2*1=53 (c)WPL=(2+3)*3+4*2+11*1=34
图6, 1 3 具有不同带权路径长度的二叉树
试构造一棵有 N个叶子结点的二叉树，
则其中带权路径长度 WPL最小的二叉树称作最
优二叉树或哈夫曼（ Huffman）树。
构造哈夫曼树思想：
(1)根据给定的 N个权值 {w1,w2,…,wN}
构成 N棵二叉树的集合 F ={T1,T2,…,TN}，
其中每棵二叉树 Ti中只有一个带权为 wi的根
节点，其左右子树均空；
(2)在 F中选取两棵根节点权值最小的
子树, 分别做为左右子树来构造一棵新的二
叉树, 且置新的二叉树的根节点的权值为其
左右子树上根节点的权值之和；
(3)在 F中删除这两棵树, 同时将新得到
的二叉树加入 F中；
(4)重复 (2),(3)，直到 F仅含一棵树
为止。
－－－－贪心算法
C D
A
B
A B DC
C D
A B
C D
B
A
11 4 3 2
3 2
11 4
11
4
3 2
4
3 2
11
5
9
5
9
5
20
C D
A
B
( a ) 初始集合含4 棵树 ( b ) 集合含3 棵树 ( c ) 集合含2 棵树 ( d ) 集合中只含1 棵树 ( e ) 哈夫曼树的前缀编码
1
1
1 0
0
0
A:0
B:10
C:110
D:111
图6, 1 4 哈夫曼树的构造过程及哈夫曼编码
贪心算法并不从整体最优的角度来考虑
问题。它所做出的选择只是在某种意义上的局
部最优选择。
?哈夫曼树应用：
哈夫曼编码 －－电文的 二进制前缀编码
6.5 本章小结
? 基本内容：
1,树的 基本概念
2,二叉树 的定义、性质和存储结构；
二叉树的遍历和线索化以及 遍历算法 的各
种描述形式；
3,树和森林 与二叉树的转换、树和
森林的遍历；
4.树的 典型应用 ； 回溯法 与 贪心算法 。
? 基本要求：
熟练掌握二叉树的 结构特性, 了解相
应的 证明方法 。
熟悉二叉树的各种 存储结构 的特点及
适用范围 。
熟练掌握各种 遍历策略 的递归算法,
了解遍历过程中, 栈, 的作用和状态, 而
且能灵活运用遍历算法实现二叉树的其他
操作 。 层次遍历 是按另一种搜索策略进行
的遍历 。
熟悉树的各种存储结构及其特点, 掌握树
和森林与二叉树的转换方法 。 掌握各种建立二
叉树和树的存储结构的方法 。
学会编写实现树的各种操作的算法 。
掌握建立哈夫曼编码的方法 。
学习并使用贪心算法与回溯法的思想 。
