6.1 树的定义和基本术语
6.2 二叉树
6.3 遍历二叉树和线索二叉树
6.4 树和森林
6.5 赫夫曼树及其与树的应用
第六章 树和二叉树
2
Page 2
6.1 树的定义和基本术语
树的定义
树是由n(n
0)个结点组成的有限集合。如果n = 0，称为空
树；
如果n > 0，则
有一个特定的称之为根(root)的结点，它只有直接后继，但没
有直接前驱；
除根以外的其它结点划分为m (m
0)个互不相交的有限集合
T0,T1,…
,Tm-1，每个集合又是一棵树，并且称之为根的子树。每棵子
树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。
A
B C
E F G H I J
K L M
D
3
Page 3
A
B C
E F G H I J
K L M
D
ROOT
SUBTREE1
SUBTREE2
SUBTREE3
6.1 树的定义和基本术语
4
Page 4
结点(node)：数据元素及其分支
结点的度(degree)：结点拥有的子树的个数
树的度(degree)：树中结点的度的最大值
分支(branch)结点：度不为0的结点
叶子(leaf)结点：度为0的结点
子(child)结点：结点子树的根
双亲(parent)结点：子结点的直接前驱结点
兄弟(sibling)结点：同一双亲的子结点互称兄弟结点
结点的层次(level)：根为第一层；子结点的层次比双亲结
点的层次加1
树的深度(depth)：树中结点的最大层次
有序树：子树从左到右有序
无序树：子树无序
森林(forese)：m（
0）棵互不相交的树的集合
6.1 树的定义和基本术语
5
Page 5
6.2 二叉树
B
C
D
E
F
L
二叉树示例
6.2.1
二叉树的定义
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由
一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树
组成。
二叉树结点的子树要区分左子树和
右子树，即使只有一棵子树也要进
行区分，说明它是左子树，还是右
子树。这是二叉树与树的最主要的
差别。
6
Page 6
D
C
H
E
F
B
A
1
层：结点个数 2
1-1
=2
0
个
2
层：结点个数 2
2-1
=2
1
个
3
层：结点个数 2
3-1
=2
2
个
6.2.2
二叉树的性质
性质1
：在二叉树的第
i
层上至多有 2
i-1
个结点
证： 1)
k = 1
时成立;
2)
设
k = i-1
时成立;
3)
则当
k = i
时，在二叉树的第
i
层上至多有 2
i-1-1
*
2 =
2
i-1
个结点；
原命题成立。
6.2 二叉树
7
Page 7
性质2
：深度为
K
的二叉树至多有2
k
- 1
个结点
证：利用性质 1
，将第 1
层至第
k
层的最多的结点数进行相加，
则：1 + 2 + 2
2
+
…………
+ 2
k-2
+ 2
k-1
= 2
k
- 1
原命题成立。
性质3
：二叉树的叶子结点数
n0
等于度为 2
的结点数n2 + 1
证：设度为 1
的结点数为
n1
，树枝的总数为
B
则：B = n0+n1+n2-1
又
B = n1+2
*
n2
n1+2
*
n2 = n0+n1+n2-1
n0 = n2 + 1
原命题成立。
6.2 二叉树
8
Page 8
满二叉树：深度为k且由2k-1个结点的二叉树，如下图(a)所示。
完全二叉树：如果深度为k、有n个结点的二叉树中每个结点能够与
深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这
样的二叉树为完全二叉树，如下图(b)所示。图(c)、(d)是2棵非完
全二叉树。满二叉树是完全二叉树的特例。
1
2 3
4 5 6
(a)
7
1
2 3
4 5 6
(b)
1
2 3
4 5
(c)
6
1
2 3
4
(d)
5
6.2 二叉树
完全二叉树所
有叶子结点都
出现在第k层
或k－1层。
9
Page 9
性质4：具有n个结点的完全二叉树的深度为
log2n
＋1。
符号
x
表示不大于x的最大整数。
证：设此二叉树的深度为k，则根据性质2及完全二叉树的定义
得到：2k-1－1 < n <= 2k-1 或 2k-1 <= n < 2k
取对数得到：k－1 < log2n < k
k是整数，
k＝
log2n
＋1。
性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号
（从上到下，从左到右),则对任一结点i（1<=i<=n),有：
（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，
则其双亲是结点
i/2
。
（2）如果2i>n，则结点i无左孩子；否则其左孩子是结点2i。
（3）如果2i＋1>n，则结点i无右孩子；否则其右孩子是结点
2i＋1。
6.2 二叉树
10
Page 10
可以先证明（2）和（3），然后从（2）和（3）推出（1）。
证：1 对于i＝1，由完全二叉树的定义，其左孩子是结点2，若2>n，即
不存在结点2，此时结点i无孩子。结点i的右孩子也只能是结点3，若结
点3不存在，即3>n，此时结点i无右孩子。
2 对于i>1，可分为两种情况：
（1）设第j(1<=j<=
log2n
)层的第一个结点的编号为i，由二叉树的
性质2和定义知i＝2j-1，结点i的左、右孩子必定为的j＋1层的第一、二个
结点，其编号为2j＝2*2j-1＝2i和2i+1。如果2i>n，则无左孩子，如果
2i+1>n，则无右孩子。
（2）假设第j层上的某个结点编号为i(2j-1<=i<=2j-1),且2i＋1<n，
其左孩子为2i，右孩子为2i＋1，则编号为i＋1的结点是编号为i的结点
的右兄弟或堂兄弟。若它有左孩子，则其编号必定为2i＋2＝2*(i＋1)；
若它有右孩子，则其编号必定为2i＋3＝2*(i＋1)＋1。
6.2 二叉树
11
Page 11
3 从（2）和（3）推出（1）
当i=1时，结点是根，因此无双亲。当i>1时，设其双亲结点编
号为p，如果i为左孩子，即i=2p，则p=i/2=
i/2
；如果i为右孩
子，i=2p+1,p=(i-1)/2=
i/2
。
证毕。
6.2 二叉树
i/2
i i+1
2i 2i+1 2i+2 2i+3
i+1
2i+2 2i+3
i
2i 2i+1
(a) i和i+1结点在同一层 (b) i和i+1结点不在同一层
……
……
12
Page 12
6.2.3 二叉树的存储结构
1.顺序存储结构
用一组连续的存储
单元存储二叉树的数据
元素。必须把二叉树的
所有结点按层序编号，
结点的序号反映出结点
之间的逻辑关系。
A B C D E F G H I J K L
1 2 3 4 5 6 7 8 9 10 11 12
6.2 二叉树
D
C
G
E
F
B
A
H
K
I
J
L
8 9 10 11 12
4 5 6 7
2 3
1
13
Page 13
A B C D E F Ø Ø Ø G Ø H
1 2 3 4 5 6 7 8 9 10 11 12
顺序存储缺点是有可能对存储空间造成极大的浪费，在最坏的
情况下，一个深度为h且只有h个结点的右单支树确需要2h-1个结点
存储空间。
6.2 二叉树
D
C
E Ø
F
B
A
Ø Ø G Ø
H
8 9 10 11 12
4 5 6 7
2 3
1
D
C
E
F
B
A
G
H
14
Page 14
typedef struct BiTNode
{ TELemType data;
struct BiTNode *lchild;
struct BiTNode *rchild;
} BitTNode, * BiTree;
二叉链表
2 链式存储结构：
6.2 二叉树
data lchild rchild
typedef struct BiTNode
{ TELemType data;
struct BiTNode *lchild;
struct BiTNode *rchild;
struct BiTNode *parent;
} BitTNode, * BiTree;
三叉链表
data lchild rchild parent
15
Page 15
6.2 二叉树
16
Page 16
6.2 二叉树
A
B
D
G
E
F
H
J
I
C
#define MAX_SIZE 10
typedef struct BiTNode
{ TELemType data;
int lchild;
int rchild;
} BitTNode；
typedef BiTNode SqBiTree[MAX_SIZE];
data
lchild
rchild
1 2 3 4 5 6 7 8 9 10
A B C D E F G H I J
2 3 0 6 0 0 8 9 0 0
0 4 5 7 0 0 0 10 0 0
3 静态链式存储结构：
静态链式结构适用于二叉树上的结点个数已知，或不支持动态存
储分配的高级语言。
17
Page 17
6.3 遍历二叉树和线索二叉树
6.3.1
遍历二叉树
1
定义：按照某种顺序访问二叉树中的每个结点，使每个结点被
访问一次且只被访问一次。
线形表的遍历
（1
）顺序表的遍历：
for(i=1; i<=v.last; i++)
visit(v.
elem
[i]);
（2
）链表的遍历：
for(p=L->next; p!=NULL; p=p->next) visit(p->data);
二叉树的遍历：非线形关系，需确定先后次序。
通常按对根结点的处理次序分为：
先序（DLR
）、中序（LDR
）、后序（LRD
）。
18
Page 18
–先序遍历二叉树(
DLR)
的操作定义:
(1)
访问根结点;
(2)
先序遍历左子树
(3)
先序遍历右子树
–中序遍历二叉树(
LDR)
的操作定义:
(1)
中序遍历左子树;
(2)
访问根结点;
(3)
中遍历右子树;
–后序遍历二叉树(
LRD)
的操作定义:
(1)
后序遍历左子树;
(2)
后遍历右子树;
(3)
访问根结点;
D
C
F
E
B
A
先序：A B D C E F
中序：D B A E C F
后序：D B E F C A
6.3 遍历二叉树和线索二叉树
19
Page 19
2
遍历算法（中序）
递归算法：
void inorder(BiTree T)
{ if (T!=NULL)
{ if (T->lchild!=NULL)
inorder(T->lchild);
printf(T->data);
if (T->rchild!=NULL)
inorder(T->rchild);
}
}
void inorder(BiTree T)
{ InitStack(S);
p=T;
while(p||!SatckEmpty(S))
{ if (p) { Push(p);
p=p->lchild;
}
else { Pop(p);
printf(p->data);
p=p->rchild);
}
}
}
非递归算法：
6.3 遍历二叉树和线索二叉树
20
Page 20
3
二叉树算法举例:
int TreeEqual(BiTree T1, BiTree T2)
//如果两树相等，返回1，否则返回0（先序）
{ if (!T1 && !T2) return(1);
else if ( T1 && T2)
{ if (T1->data == T2->data)
if (TreeEqual(T1->lchild, T2->lchild))
return (TreeEqual(T1->rchild, T2->rchild));
}
return(0);
}
6.3 遍历二叉树和线索二叉树
21
Page 21
BiTree TreeCopy(BiTree T) //二叉树复制（先序）
{ if (T)
{ p=(BiTree)malloc(sizeof(BiTNode));
p->data=T->data;
p->lchild=TreeCopy(T->lchild);
p->rchild=TreeCopy(T->rchild);
return(p);
}
else return(NULL);
}
6.3 遍历二叉树和线索二叉树
22
Page 22
6.3 遍历二叉树和线索二叉树
6.3.2
线索二叉树
1
什么是线索二叉树
遍历的实质是对非线形结构的二叉树进行线形化处理。遍历序
列中某结点的前驱、后继的位置只能在遍历的动态过程中得到。
n个结点的二叉链表中有n+1个空链域，可以存放其前驱和后
继的指针。
结点结构： lc h ild lt a g d a t a r t a g r c h ild
ltag=0，lchild指向左子结点
ltag=1，lchild指向前驱结点
rtag=0，rchild指向右子结点
rtag=1，rchild指向后继结点
typedef struct BiThrNode
{ TELemType data;
struct BiThrNode *lchild;
struct BiThrNode *rchild;
unsigned ltag:1;
unsigned rtag:1;
} BitThrNode, * BiThrTree;
23
Page 23
D
C
F
E
B
A
无前驱结点无后继结点
0
0
0
0
0
0
1
1
1
1
1
1
1
1
A
B
D
E
C
F
新增头结点
6.3 遍历二叉树和线索二叉树
注：本小节中的前驱
和后继指遍历序列中
线形化逻辑关系中某
结点的前驱和后继，
不是其父子结点。
24
Page 24
2
前驱与后继的查找
BiThrNode *priornode(BiThrNode *p)
{ BiThrNode *pre=p->lchild;
if(!p->Ltag) // 查找左子树的最右结点
while(!pre->Rtag) pre=pre->rchild;
return(pre);
}
BiThrNode *nextnode(BiThrNode *p)
{ BiThrNode *next=p->rchild;
if(!p->Rtag) // 查找右子树的最左结点
while(!next->Ltag) next=next->lchild;
return(next);
}
6.3 遍历二叉树和线索二叉树
25
Page 25
3
线索二叉树的遍历
为方便起见，为线索二叉树增加一个头结点，使之类似
一个双向循环线索链表。
算法1：P134算法6.5
算法2：利用nextnode函数
Void inorder_thr(BiThrTree T)
{ p=T->lchild;
while(p!=T && !p->Ltag) //查找最左结点
p=p->lchild;
while(p!=T)
{ printf(p->data); p= nextnode(p); }
}
6.3 遍历二叉树和线索二叉树
26
Page 26
4
二叉树的线索化
void inorderthreading(BiThrTree &Thrt, BiThrTree T)
// 设线索化前T中每个结点的Ltag和Rtag域均为0.
{ BiThrNode *pre, *p;
// pre指向上次处理过的结点，p指向当前处理的结点
BiThrNode *pre, *p, *S[MAX]; //S为顺序结构的栈
int i=0; // i为栈顶位置
Thrt=(BiThrNode *)malloc(sizeof(BiThrNode));
Thrt->Ltag=0;
Thrt->Rtag=1;
Thrt->rchild=Thrt;
if(!T) Thrt->lchild=Thrt;
6.3 遍历二叉树和线索二叉树
27
Page 27
else{
Thrt->lchild=T; pre=Thrt; p=T;
do{ while(p) { S[i++]=p; p=p->lchild; }
// 找寻p结点的左子树中的最左结点
if( i>0)
{ p=S[--i];
if(!p->lchild) { p->Ltag=1; p->lchild=pre; }
if(!pre->rchild) { pre->Rtag=1; pre->rchild=p; }
pre=p; // pre为上次循环中处理过的结点
p=p->rchild; // p为本次循环中处理的结点
}
}while(i>0 || p!=NULL);
pre->Rtag=1; pre->rchild=Thrt; Thrt->rchild=pre;
}
}
6.3 遍历二叉树和线索二叉树
28
Page 28
6.4 树和森林
………
A
B
C
D
F
G
H
I
J
E
A 1 2 3
-1
B
4 5 -1 0
C 6 -1 -1 0
D 7 8 -1
0
E -1 -1 -1 1
F -1 -1 -1 1
G -1 -1 -1 2
H 9
-1 -1
3
I -1 -1 -1 3
J -1 -1 -1 7
0
1
2
3
4
5
6
7
8
9
用数组（静态链式
存储）表示左图的
树，-1
表示空。
缺点：空指针域太
多，有(
K -1 )
× n
+ 1
个。
例:
度数
K
＝ 3
的树
6.4.1 树的存储结构
1 孩子表示法：由数据域、
K
个子结点指针域、父结点指针域组成。
data child1 child2 childk parents
29
Page 29
A
B
C
D
F
G
H
I
J
E
A
∧
B
C
D
∧
F
∧ ∧ G
∧ H
∧
I
∧ ∧
E
∧
J
∧
6.4 树和森林
2 孩子兄弟表示法：由数据域、指向它的第一棵子树树根的指针
域、指向它的兄弟结点的指针域组成。实质上是用二叉树表示一
棵树。
firstchild data nextsibling
30
Page 30
A
B
C
D
F
G
H
I
J
E
A
B
C
D
F
G
H
I
J
E
A
B
C
D
F
G
H
I
J
E
6.4 树和森林
6.4.2 树、森林与二叉树的转换
1 树转换成相对应的二叉树：
1
）保留每个结点的最左面的分支，其余分支都被删除。
2
）同一父结点下面的结点成为它的左方结点的兄弟。
31
Page 31
B
C
D
F
G
H
I
J
E
B
C
D
F
G
H
I
J
E
A
B
C
D
F
G
H
I
J
E
A
6.4 树和森林
2 森林转换成相对应的二叉树：
增加一个虚拟的根结点，它的子结点为各棵树的根。
那么，就变成了树转换成二叉树的问题。
32
Page 32
N
B
C
D
F
G
H
I
J
E
A
T
1
T
2
……
T
3
L
R
先根：A B E F C G D H J I
后根：E F B G C J H I D A
6.4 树和森林
6.4.3 树、森林的遍历
1 树的先根、后根遍历：
1
）先根：类似于二叉树的先序遍历（NLR
） N:
根；L
：第一棵子
树，R
：其余的子树，遍历方向由第二棵子树至最后一棵子树。
2
）后根：类似于二叉树的中序遍历（LRN
） L
：第一棵子树，R
：
其余的子树，遍历方向由第二棵子树至最后一棵子树，
N:
根。
33
Page 33
先序：B E F C G D H J I
后序：E F B G C J H I D
B
C
D
F
G
H
I
J
E
A
B
C
D
F
G
H
I
J
E
2 森林的先序、后序遍历：
1
）先序遍历类似于树的先序遍历。增加一个虚拟的根结点，它的
子结点为各棵树的根。对这棵树进行先根遍历，即得到森林的先序序
列（去掉树根结点）。
2
）后序遍历类似于树的后序遍历。增加一个虚拟的根结点，它的
子结点为各棵树的根。对这棵树进行后根遍历，即得到森林的后序序
列（去掉树根结点）。
6.4 树和森林
34
Page 34
6.6 赫夫曼树及其应用
路径长度：结点之间的树枝的总数
树的路径长度：从根到每一结点的路径长度之和
树的带权路径长度(
WPL)
：
叶子结点的带权路径长度之和
最优二叉树或赫夫曼树：树的带权路径长度
WPL
最小的二叉树
E
G
H
L
L
E
H
G
E
G
H
L
7
7
7
5
2
4
4
4
2
2
5
5
WPL=36
WPL=46
WPL=35
6.6.1 最优二叉树（赫夫曼树）
n
i
i
i
l
l
w
w
W P L
W P L
1
35
Page 35
分数
等级
比例
0~59 60~69 70~79 80~89 90~100
E D C B A
0.05 0.15 0.40 0.30 0.10
a<60
a<70
a<80
a<90
E
D
C
B A
Y N
N
N
N
Y
Y
Y
70≤ a<80
C
B
E A
D
Y N
Y
Y
N
80≤ a<90
60≤ a<70
a<60
a<80
a<70 a<90
a<60
E D
C B A
N
N N
N
N
Y N
Y
Y
Y
判定树：
6.6 赫夫曼树及其应用
WPL=3.15
WPL=2.05
WPL=2.2
36
Page 36
(1) 由给定的n个权值{w0, w1, w2, …
, wn-1}，构造具有n棵二叉树
的集合F = {T0, T1, T2, …
, Tn-1}，其中每一棵二叉树Ti只有
一个带有权值wi的根结点，其左、右子树均为空。
(2) 重复以下步骤, 直到F中仅剩下一棵树为止：
① 在F中选取两棵根结点的权值最小的二叉树, 做为左、右
子树构造一棵新的二叉树。置新的二叉树的根结点的权值为
其左、右子树上根结点的权值之和。
② 在F中删去这两棵二叉树。
③ 把新的二叉树加入F。
6.6 赫夫曼树及其应用
赫夫曼算法：
37
Page 37
赫夫曼树的构造过程
38
Page 38
赫夫曼编码主要用途是实现数据压缩。设给出一段报文： CAST CAST
SAT AT A TASA，字符集合是{C,A,S,T}，各个字符出现的频度(次数)是
W={2,7,4,5}。若给每个字符以等长编码 A: 00 T: 10 C: 01 S: 11，
则总编码长度为(2+7+4+5)*2=36。若按各个字符出现的频度不同而给予不
等长编码，可望减少总编码长度。
6.3.2 赫夫曼编码
以各字符出现的频度为权值建立赫夫曼
树。左分支赋0，右分支赋1，得赫夫曼编码
A:0 T:10 C:110 S:111，总编码长度：
7*1+5*2+(2+4)*3=35，比等长编码的总编码
长度要短。
采用赫夫曼编码时，总编码长度正好等
于赫夫曼树的带权路径长度WPL。
赫夫曼编码是一种无前缀编码。解码时不
会混淆。
6
A, 7
S, 4
C, 2
11
T, 5
18
1
1
1
0
0
0
6.6 赫夫曼树及其应用
39
Page 39
6
A, 7
S, 4
C, 2
11
T, 5
18
1
1
1
0
0
0
typedef struct
{ unsigned int weight ;
unsigned int parent, lchild, rchild ;
} HTNode, * HuffmanTree:
typedef char ** HufmanCode ;
赫夫曼编码的实现：
1
建立具有 2
n-1
个单元的数组，
其中
n
个单元用于保存初始结点，
n-1
个结点用于表示内部结点。
2
构造一棵赫夫曼树，即执行
n-1
次循环，每次产生一个内部结点。
权值最小的两个结点为其左右儿子。
3
计算每个字符的赫夫曼编码。
6.6 赫夫曼树及其应用
40
Page 40
void hufmanCode(HufumanTree &HT, HumanCode &HC, int *w, int n)
{ if ( n<=1 ) return;
m = 2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 不用0号单元
for ( p=HT+1, i=1; i<=n; ++i, ++p, ++w ) *p = { *w, 0, 0, 0 } ;
for ( ; i <= m; ++i, ++p ) *p = { 0, 0, 0, 0 } ;
for ( i = n+1; i <= m; ++i )
{ Select ( HT, i-1, s1, s2 ) ;
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2 ;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
6.6 赫夫曼树及其应用
41
Page 41
HC = ( HuffmanCode ) malloc (( n + 1) * sizeof ( char * ));
cd = ( char * ) malloc ( n * sizeof ( char ) );
cd[n-1] =‘/0’ ;
for ( i = 1; i <= n; ++i )
{ start = n-1;
for ( c=i, f=HT[i].parent; f != 0; c=f, f=HT[f].parent )
if (HT[f].lchild == c ) cd[--start ] = ‘0’ ；
else cd [--start ] = ‘1’ ;
HC[i] = ( char * ) malloc (( n - start ) * sizeof ( char * ));
strcpy(HC[i], &cd[start]);
}
free(cd);
}
6.6 赫夫曼树及其应用
演示