第六章 树和二叉树第六章树和二叉树一、树
树的 ADT定义
– 从关系约束的角度定义树
– 以递归形式定义树
相关术语
– 根结点 -叶结点 -非叶结点
– 父结点 -子结点
– 祖先结点 -子孙结点
– 结点的度 -树的度
– 路径 -路径长度
– 有向树 -无向树
– 结点的层数
– 树的深度第六章树和二叉树二、二叉树
二叉树的定义
– 度不大于 2的有向树称为二叉树。
相关术语
– 左子结点 -右子结点第六章树和二叉树二、二叉树
二叉树的性质第 i层最多有 2i个结点深度为 h，则最少有 h个结点，最多有 2h-1个结点结点数为 n，则深度最多为 n，最少为 ┌log(n+1)┐
满二叉树完全二叉树
7 8 9 10 11 12 13
3 4 5 6
1 2
0
第六章树和二叉树二、二叉树
二叉树的性质对完全二叉树，结点 i的左子结点序号为 2i+1
对完全二叉树，结点 i的右子结点序号为 2i+2
对完全二叉树，结点 i的父结点序号为 └(i-1)/2┘
7 8 9 10 11 12 13
3 4 5 6
1 2
0
第六章树和二叉树二、二叉树
二叉树的实现
– 二叉链结构
– 父链结构
– 三叉链结构 a
b c
e f
g h i
d
CODING
a
b
∧
c
d
∧ ∧
e f
∧
i
∧ ∧
h
∧ ∧
g
∧ ∧
第六章树和二叉树二、二叉树
二叉树的遍历
– 前序遍历：根 左子 右子
– 中序遍历：左子 根 右子
– 后序遍历：左子 右子 根
– 层次遍历：逐层
a
b c
e f
g h i
d
j k
abdcegjkhfi
dbajgkehcfi
dbjkgheifca
abcdefghijk
CODING
第六章树和二叉树二、二叉树
二叉树的遍历
– 应用举例：遍历与输入二叉树
abd###ceg##h##f#i##
a
b c
e f
g h i
d
a
b c
e f
g h i
d
CODING
第六章树和二叉树二、二叉树
二叉树的遍历
–应用举例：二叉树的撤销
CODING
第六章树和二叉树二、二叉树
二叉树的遍历
–遍历序与二叉树的对应
前序遍历序 +中序遍历序唯一确定二叉树 a
b c
e f
g h i
d
前序遍历序,abdceghfi
中序遍历序,dbagehcfi
第六章树和二叉树二、二叉树
线索化二叉树
– 定义
a
b
∧
c
d
∧ ∧
e f
∧
i
∧ ∧
h
∧ ∧
g
∧ ∧
a
b c
d e f
ihg
中序线索化二叉树第六章树和二叉树二、二叉树
线索化二叉树
– 中序线索化二叉树的遍历
– 二叉树的中序线索化
a
b c
d e f
ihg
CODING
第六章树和二叉树二、二叉树
二叉树应用举例
– 表达式运算树
A+(B*(C-D))/E-F*(G+H)
A
B
C D
E G
F +
H
*
-
*
/
+
-
第六章树和二叉树三、森林、树、二叉树
树的物理结构
– 父链结构
– 子链结构
– 子链 -兄弟链结构
a
∧
b
c
d
∧
e
∧
f
∧ ∧
j
∧
k
∧
l
∧ ∧
i
∧ ∧
a
b
e
dc
if j k l
第六章树和二叉树三、森林、树、二叉树
树与森林
–树 =根 +子树森林
a
b
e
dc
if j k l m
qn o p
第六章树和二叉树三、森林、树、二叉树
树的二叉树表示
– 树?二叉树
– 二叉树?树
a
b
e
dc
if j k l m
qn o p
a
b
e
d
c
i
f j
k
l
m
q
n
o
p
Tree=(root,T1,…,Tn)
BiTree=(root,Tl,Tr)
第六章树和二叉树三、森林、树、二叉树
森林与二叉树
–森林?二叉树
–二叉树?森林
b
e
dc
if j k l m
qn o p
b
e
d
c
i
f j
k
l
m
q
n
o
p
Forest=(T1,…,Tn)=((root,T11,…,T1m),…Tn)
BiTree=(root,Tl,Tr)
第六章树和二叉树四、哈夫曼树
哈夫曼树（最优二叉树）
–叶结点带权的二叉树
50
12
25
7 32
8
树的总权值,50*2+12*3+25*4+8*2+7*3+32*3 = 369
第六章树和二叉树四、哈夫曼树
哈夫曼树（最优二叉树）
–哈夫曼树
a12 b7 c3 d6 e21
a
12
b
7
c
3
d
6
e
21
a
12
b
7
c
3
d
6
e
21
第六章树和二叉树四、哈夫曼树
哈夫曼算法初始时，将每个叶结点看作一个独立的二叉树，叶结点即根结点；
重复 n-1次：
选出两棵根结点权值最小的二叉树；
新增一个根结点；
将选出的两棵二叉树作为新增根结点的左子和右子；
新增根结点的权值为选出两棵二叉树根结点的权值之和；
CODING
第六章树和二叉树
a3 b7 c8 d6 e21
9
a
3
b
7
c
8
d
6
e
21
9
a
3
b
7
c
8
d
6
e
21
15
9
a
3
b
7
c
8
d
6
e
21
15
24
9
a
3
b
7
c
8
d
6
e
21
15
24
45
第六章树和二叉树四、哈夫曼树
哈夫曼编码
–定长编码与变长编码
–最优变长编码 ——哈夫曼编码
a:100
b:110
c:111
d:101
e:0
9
a
3
b
7
c
8
d
6
e
21
0 1
15
0 1
24
0 1
45
10
CODING
第六章树和二叉树四、哈夫曼树
哈夫曼编码
–编码构造
–信息编码
–信息解码
a:100
b:110
c:111
d:101
e:0
9
a
3
b
7
c
8
d
6
e
21
0 1
15
0 1
24
0 1
45
10
发送方 接收方
aebaeceddec 1000110100011101011010111 aebaeceddec
树的 ADT定义
– 从关系约束的角度定义树
– 以递归形式定义树
相关术语
– 根结点 -叶结点 -非叶结点
– 父结点 -子结点
– 祖先结点 -子孙结点
– 结点的度 -树的度
– 路径 -路径长度
– 有向树 -无向树
– 结点的层数
– 树的深度第六章树和二叉树二、二叉树
二叉树的定义
– 度不大于 2的有向树称为二叉树。
相关术语
– 左子结点 -右子结点第六章树和二叉树二、二叉树
二叉树的性质第 i层最多有 2i个结点深度为 h，则最少有 h个结点，最多有 2h-1个结点结点数为 n，则深度最多为 n，最少为 ┌log(n+1)┐
满二叉树完全二叉树
7 8 9 10 11 12 13
3 4 5 6
1 2
0
第六章树和二叉树二、二叉树
二叉树的性质对完全二叉树，结点 i的左子结点序号为 2i+1
对完全二叉树，结点 i的右子结点序号为 2i+2
对完全二叉树，结点 i的父结点序号为 └(i-1)/2┘
7 8 9 10 11 12 13
3 4 5 6
1 2
0
第六章树和二叉树二、二叉树
二叉树的实现
– 二叉链结构
– 父链结构
– 三叉链结构 a
b c
e f
g h i
d
CODING
a
b
∧
c
d
∧ ∧
e f
∧
i
∧ ∧
h
∧ ∧
g
∧ ∧
第六章树和二叉树二、二叉树
二叉树的遍历
– 前序遍历：根 左子 右子
– 中序遍历：左子 根 右子
– 后序遍历：左子 右子 根
– 层次遍历：逐层
a
b c
e f
g h i
d
j k
abdcegjkhfi
dbajgkehcfi
dbjkgheifca
abcdefghijk
CODING
第六章树和二叉树二、二叉树
二叉树的遍历
– 应用举例：遍历与输入二叉树
abd###ceg##h##f#i##
a
b c
e f
g h i
d
a
b c
e f
g h i
d
CODING
第六章树和二叉树二、二叉树
二叉树的遍历
–应用举例：二叉树的撤销
CODING
第六章树和二叉树二、二叉树
二叉树的遍历
–遍历序与二叉树的对应
前序遍历序 +中序遍历序唯一确定二叉树 a
b c
e f
g h i
d
前序遍历序,abdceghfi
中序遍历序,dbagehcfi
第六章树和二叉树二、二叉树
线索化二叉树
– 定义
a
b
∧
c
d
∧ ∧
e f
∧
i
∧ ∧
h
∧ ∧
g
∧ ∧
a
b c
d e f
ihg
中序线索化二叉树第六章树和二叉树二、二叉树
线索化二叉树
– 中序线索化二叉树的遍历
– 二叉树的中序线索化
a
b c
d e f
ihg
CODING
第六章树和二叉树二、二叉树
二叉树应用举例
– 表达式运算树
A+(B*(C-D))/E-F*(G+H)
A
B
C D
E G
F +
H
*
-
*
/
+
-
第六章树和二叉树三、森林、树、二叉树
树的物理结构
– 父链结构
– 子链结构
– 子链 -兄弟链结构
a
∧
b
c
d
∧
e
∧
f
∧ ∧
j
∧
k
∧
l
∧ ∧
i
∧ ∧
a
b
e
dc
if j k l
第六章树和二叉树三、森林、树、二叉树
树与森林
–树 =根 +子树森林
a
b
e
dc
if j k l m
qn o p
第六章树和二叉树三、森林、树、二叉树
树的二叉树表示
– 树?二叉树
– 二叉树?树
a
b
e
dc
if j k l m
qn o p
a
b
e
d
c
i
f j
k
l
m
q
n
o
p
Tree=(root,T1,…,Tn)
BiTree=(root,Tl,Tr)
第六章树和二叉树三、森林、树、二叉树
森林与二叉树
–森林?二叉树
–二叉树?森林
b
e
dc
if j k l m
qn o p
b
e
d
c
i
f j
k
l
m
q
n
o
p
Forest=(T1,…,Tn)=((root,T11,…,T1m),…Tn)
BiTree=(root,Tl,Tr)
第六章树和二叉树四、哈夫曼树
哈夫曼树（最优二叉树）
–叶结点带权的二叉树
50
12
25
7 32
8
树的总权值,50*2+12*3+25*4+8*2+7*3+32*3 = 369
第六章树和二叉树四、哈夫曼树
哈夫曼树（最优二叉树）
–哈夫曼树
a12 b7 c3 d6 e21
a
12
b
7
c
3
d
6
e
21
a
12
b
7
c
3
d
6
e
21
第六章树和二叉树四、哈夫曼树
哈夫曼算法初始时，将每个叶结点看作一个独立的二叉树，叶结点即根结点；
重复 n-1次：
选出两棵根结点权值最小的二叉树；
新增一个根结点；
将选出的两棵二叉树作为新增根结点的左子和右子；
新增根结点的权值为选出两棵二叉树根结点的权值之和；
CODING
第六章树和二叉树
a3 b7 c8 d6 e21
9
a
3
b
7
c
8
d
6
e
21
9
a
3
b
7
c
8
d
6
e
21
15
9
a
3
b
7
c
8
d
6
e
21
15
24
9
a
3
b
7
c
8
d
6
e
21
15
24
45
第六章树和二叉树四、哈夫曼树
哈夫曼编码
–定长编码与变长编码
–最优变长编码 ——哈夫曼编码
a:100
b:110
c:111
d:101
e:0
9
a
3
b
7
c
8
d
6
e
21
0 1
15
0 1
24
0 1
45
10
CODING
第六章树和二叉树四、哈夫曼树
哈夫曼编码
–编码构造
–信息编码
–信息解码
a:100
b:110
c:111
d:101
e:0
9
a
3
b
7
c
8
d
6
e
21
0 1
15
0 1
24
0 1
45
10
发送方 接收方
aebaeceddec 1000110100011101011010111 aebaeceddec
