第 6章 二叉树和 树
树型结构是一类重要的 非线性结构 。树型结构是 结点之间有分支,并且具有 层次关系的结构,它非常类似于自然界中的树。树结构在客观世界中是大量存在的。例如 家谱、
行政组织机构 都可用树形象地表示。
树结构在计算机领域中也有着广泛的应用,
例如在 编译程序 中,用树结构来表示源程序的 语法结构 ；在 数据库系统 中,可用树结构来组织信息 ；在分析算法的行为时,可 用树结构来描述其执行过程 等等。
华中师范大学魏开平王敬华沈显君
…
系统 软件 办公室应用操作系统 数据库 数据结构 离散数学
…
…
外语中文历史计科教务处科研处总务处
… …… 附中
ds.cs.ccnu.edu.cn
au ee
cn
edu
ccnu
cs
ds
buaa whu…
……
…
…
…
课前导学
6.1 二叉树
6.2 遍历二叉树和线索二叉树
6.3 树和森林
6.4 树的应用
【 学习目标 】
1,领会树和二叉树的类型定义，理解树和二叉树的结构差别。
2,熟记二叉树的主要特性，并掌握它们的证明
3,熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。
4,理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。
5,熟练掌握二叉树和树的各种存储结构及其建立的算法。
6,学会编写实现树的各种操作的算法。
7,了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。
【 重点和难点 】
重点
：
二叉树和树的遍历及其应用难点
：
编写实现二叉树和树的各种操作的递归算法知识点
–
树的类型定义
–
二叉树的类型定义
–
二叉树的存储表示
–
二叉树的遍历以及其它操作的实现
–
线索二叉树
–
树和森林的存储表示
–
树和森林的遍历以及其它操作的实现
–
最优树和赫夫曼编码
【 学习指南 】
本章是整个课程的第三个学习重点，也是整个课程中的一大 难点 。在本章的学习过程中主要应该学会 如何根据二叉树和树的结构及其操作的递归定义编写递归算法 。
本章必须完成的算法设计题为,
6.1,6.3,6.4,6.5,6.6,6.7,
6.8,6.9,6.10,6.11,6.12,6.14,
6.16,6.17,6.18,6.20,6.21,6.24,
6.25,6.26
6.1 二叉树二、二叉树的基本性质一、二叉树的定义和基本术语三、二叉树的存储结构逻辑结构物理结构一、二叉树的定义和基本术语
1、二叉树的定义
2、二叉树的基本术语
3、二叉树的应用举例
4、二叉树的基本操作
1,二叉树定义
二叉树 T是 n个结点的有限集合，其中 n≥0,当 n=0时，
为空树，否则，其中有一个结点为根结点，其余结点划分为两个互不相交的子集 TL,TR，并且 TL、
TR分别构成叫作左、右子树的二叉树。
A
C
D E
F
B
G H
I
K
J
M
L
A的 TL
B的 TL
递归定义二叉树或为空树；或是由一个根结点加上两棵分别称为 左子树 和 右子树的,互不交的 二叉树组成。
A
B
C
D
E
F
G
H K
根结点左子树右子树二叉树的五种基本形态：
N
空树 只含根结点
N N N
L R R
右子树为空树
L
左子树为空树左右子树均不为空树二叉树的注意点
二叉树每个结点的孩子都有 左右之分,每个结点都有左右两个子树。
A
CB
C
B
A
C
B
A
C
B
A
三个节点的二叉树（五棵）
① 每个结点最多只有两棵子树 (不存在度大于 2的结点 )；
②左子树和右子树次序不能颠倒 (有序树 )。
2、基本术语
1.
结点(n
od
e)——
表示树中的元素
，
包括数据项及若干指向其子树的分支
2.
结点的度(de
gre
e)——
结点拥有的子树数
3.
叶子(le
af)
——
度为
0
的结点
4.
孩子(ch
ild
)——
结点子树的根称为该结点的孩子
5.
双亲(p
are
nts
)——
孩子结点的上层结点叫该结点的双亲
6.
深度——
树中结点的最大层次数
7.
结点的层次——
从根结点算起
，
根为第一层
，
它的孩子为第二层
，……
1
2 3
11
4 5
8 9 12
6 7
10
——即根结点 (没有前驱 )
——即上层的那个结点 (直接前驱 )
——即下层结点的子树的根 (直接后继 )
——同一双亲下的同层结点（孩子之间互称兄弟）
——即双亲位于同一层的结点（但并非同一双亲）
——即从根到该结点所经分支的所有结点
——即该结点下层子树中的任一结点根双亲孩子兄弟堂兄弟祖先子孙
A
B C D
E F G H I J
K L M
结点 A的度,3
结点 B的度,2
结点 M的度,0
叶子,K,L,F,G,M,I,J
结点 A的孩子,B,C,D
结点 B的孩子,E,F
结点 I的双亲,D
结点 L的双亲,E
结点 B,C,D为兄弟结点 K,L为兄弟树的度,3
结点 A的层次,1
结点 M的层次,4
树的深度,4
结点 F,G为堂兄弟结点 A是结点 F,G的祖先
3、二叉树的应用举例男
（色盲）
女 女 男男女男
─
E T
NAI M
OGKDWRUS
H V F L P J B X C Y Z Q
──
── ─ ─
──────
国际 Morse码变色力缺陷遗传图 （隔代遗传）
InitBiTree(&T);
DestroyBiTree(&T);
CreateBiTree(&T,definition);
ClearBiTree(&T);
BiTreeEmpty(T);
BiTreeDepth(T);
Parent(T,e);
LeftChild(T,e);
RightChild(T,e);
LeftSibling(T,e);
RightSibling(T,e);
InsertChild(T,p,LR,c);
DeleteChild(T,p,LR);
PreOrderTraverse(T,Visit());
InOrderTraverse(T,Visit());
PostOrderTraverse(T,Visit());
LevelOrderTraverse(T,Visit());
二叉树的基本操作查 找 类插 入 类删 除 类二、二叉树的基本性质
1、层与结点数
2、深度与结点数
3、叶子与结点数
4、完全二叉树与深度
5、完全二叉树与结点序号
1.一棵非空二叉树的第 i 层最多有 2i–1个结点 (i?1)。
证明 (采用归纳法 )
(1).当 i=1时,结论显然正确。非空二叉树的第 1层有且仅有一个结点,即树的根结点,
(2).假设对于第 j层 (1?j?i–1)结论也正确,即第 j层最多有 2j-1个结点,
(3).有定义可知,二叉树中每个结点最多只能有两个孩子结点。若第 i–1层的每个结点都有两棵非空子树,则第 i层的结点数目达到最大,而第 i–1层最多有 2i–2个结点已由假设证明,于是,应有 2?2i–2 = 2i–1
证毕,
二叉树的性质讨论 1：第 i层的结点数至多是多少？
（利用二进制性质可轻松求出）
提问,第 i层上至少有 个结点？
2.深度为 h 的非空二叉树最多有 2h -1个结点,
证明,
由性质 1可知,若深度为 h的二叉树的每一层的结点数目都达到各自所在层的最大值,则二叉树的结点总数一定达到最大。
即有
20+21+22+…+2 i-1+ …+2 h-1 = 2h-1
证毕,
二叉树的性质讨论 2：深度为 k的二叉树，至多有多少个结点？
（利用二进制性质可轻松求出）
提问,深度为 k时至少有 个结点？
3,若非空二叉树有 n0个叶结点,有 n2个度为 2的结点,
则 n0=n2+1
证明,
设该二叉树有 n1个度为 1的结点,结点总数为 n,有
n=n0+n1+n2 --------(1)
设二叉树的分支数目为 B,有
B=n-1 --------(2)
这些分支来自度于为 1的结点与度度为 2结点,即
B=n1+2n2 --------(3)
联列关系 (1),(2)与 (3),可得到
n0=n2+1证毕,
推论,n0=n2+2n3+3n4+? +(m-1)nm +1
二叉树的性质讨论 3：二叉树的叶子数和度为 2的结点数之间有关系吗？
A
B C
GE
I
D
H
F
J
实际意义,叶子数＝ 2度结点数＋ 1
4,具有 n个结点的完全二叉树的深度 h=?log2n?+1.
证明,
二叉树的性质设 完全二叉树的深度为 k
则根据第二条性质得 2k-1≤ n < 2k
即 k-1 ≤ log2 n < k
因为 k 只能是整数，因此,k =?log2n? + 1
证毕,
对于两种特殊形式的二叉树（ 满二叉树 和 完全二叉树 ），还特别具备以下 2个性质：
5,若对具有 n个结点的完全二叉树按照层次从上到下,每层从左到右的顺序进行编号,则编号为 i 的结点具有以下性质,
(1) 当 i=1,则编号为 i的结点为二叉树的根结点 ;
若 i>1,则编号为 i 的结点的双亲结点的编号为?i/2?.
(2) 若 2i>n,则编号为 i 的结点无左子树 ;
若 2i?n,则编号为 i 的结点的左子树的根的编号为 2i.
(3) 若 2i+1>n,则编号为 i 的结点无右子树 ;
若 2i+1?n,则编号为 i 的结点的右子树的根的编号为 2i+1.
1
2 3
4 5 6 7
8 9 10
n=10
二叉树的性质两种特殊形态的二叉树若一棵二叉树中的结点,
或者为叶结点，或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层,这样的二叉树为满二叉树,
1,满二叉树若一棵二叉树中只有最下面两层的结点的度可以小于 2,
并且最下面一层的结点 (叶结点 )都依次排列在该层从左至右的位臵上。这样的二叉树为完全二叉树,
2.完全二叉树二叉树的性质解释,完全二叉树的特点就是，
只有最后一层叶子不满，且全部集中在左边。
这其实是 顺序 二叉树的含义。
在图论概念中的“完全二叉树”
是指 n1=0的情况。
为何要研究这两种特殊形式？
因为它们在顺序存储方式下可以复原 !
（特点：每层都“充满”了结点）
三、二叉树的存储结构
1、顺序存储结构
2、链式存储结构
1
2 3
4 5 6 7
8 9 10
A
B C
D E F G
H I J
BT[1:15]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F G H I J
根据完全二叉树的性质 5,对于深度为 h的完全二叉树,
将树中所有结点的数据信息按照编号的顺序依次存储到一维数组 BT[1:2h-1]中,由于编号与数组的下标一一对应,该数组就是该完全二叉树的顺序存储结构,
1）完全二叉树的顺序存储结构
1、二叉树的顺序存储结构讨论,不是完全二叉树怎么办？
答,一律转为完全二叉树 ！
方法很简单,将各层空缺处统统补上,虚结点,,其内容为空 。
A
B
^
C
^
^
^
D
^
…
E
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
.
[16]
A
B
E
C
D
缺点,① 浪费空间；②插入、删除不便
1、二叉树的顺序存储结构
1
2 3
4 5 6 7
8 9 10
A
B C
D E F G
H IJ
11 12 13
BT[1:15]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F G H J I
A
B C
D E F G
H IJ
2） 一般二叉树的顺序存储结构
1、二叉树的顺序存储结构例如
A B D C E F
0 1 2 3 4 5 6 7 8 9 10 11 12 13
A
B
C
D
E
F
1
4
0
13
2
6
#define MAX_TREE_SIZE 100
// 二叉树的最大结点数
typedef TElemType
SqBiTree[MAX_TREE_SIZE];
// 0号单元存储根结点
SqBiTree bt;
1、二叉树的顺序存储结构用二叉链表即可方便表示。
datalchild rchild
data
left_child right_child
二叉树结点数据类型定义：
typedef struct node *tree_pointer;
typedef struct Binode {
TElemType data;
struct BiNode *lchild,*rchild;
} BiTNode,*BiTree;
一般从根结点开始存储。
（相应地，访问树中结点时也只能从根开始）
注,如果需要倒查某结点的双亲，
可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。
存储结点值的数据域 data
指向右孩子结点的指针指向左孩子结点的指针
2、二叉树的链式存储结构
A
C
B
D
E
F
G
返回
lchild data rchild
2、二叉树的链式存储结构
A
B E ^
^ G ^
^ F^ D ^^ C ^
例：
A
B
E
C
D
^A
B ^
D
^C
^
^E^
2、二叉树的链式存储结构二叉树的链式存储结构 (二叉链表 )
链结点的构造为
lchild data rchild
其中,data 为数据域
lchild 与 rchild 分别为指向左、右子树的指针域,
A
B C
D E F G
IJ
A
B C
D E F G
J I
T
^
^
^ ^ ^
^ ^ ^
^ ^
2、二叉树的链式存储结构 空指针个数,2*n
0+1*n1+0*n2
=2n0+n1
=n0+n1+n0
=n0+n1+n2+1
=n+1
在 n个结点的二叉链表中，有 n+1个空指针域
6.2 二叉树的遍历二、遍历算法一、二叉树的遍历四、线索二叉树三、遍历应用举例一,二叉树的遍历常用的二叉树的遍历方法,
1.前序遍历
2.中序遍历
3.后序遍历
4.按层次遍历右子树左子树根按照一定的顺序 ( 原则 )对叉树中每一个结点都访问一次 (仅访问一次 ),得到一个由该二叉树的所有结点组成的序列,
这一过程称为二叉树的遍历,
A
B
C
D
E
F
G
H K
例如,先序序列：
中序序列：
后序序列：
A B C D E F G H K
B D C A E H G K F
D C B H K G F E A
1、先序遍历
A
B C
D E F G
IJ
前序序列,
A B D E J C F I
原则,
若被遍历的二叉树非空,则
1,访问根结点 ;
2,以先序遍历原则 遍历根结点的左子树 ;
3,以先序遍历原则 遍历根结点的右子树,
G
-
*
A B
C
－
* C
A B
-
*
A B
C
先 序遍历 - * A B C1、前序遍历中序序列,
D B J E A F I C
原则,
若被遍历的二叉树非空,则
1,以中序遍历原则 遍历根结点的左子树 ;
2,访问根结点 ;
3,以中序遍历原则 遍历根结点的右子树,
G
2、中序遍历
A
B C
D E F G
IJ
-
*
A B
C
－
* C
A B
-
*
A B
C
中序遍历 A * B - C2、中序遍历后序序列,
D J E B I F G C
原则,
若被遍历的二叉树非空,则
1,以后序遍历原则 遍历根结点的左子树 ;
2,以后序遍历原则 遍历根结点的右子树,
3,访问根结点 ;
A
A
B C
D E F G
IJ
3、后序遍历
-
*
A B
C
－
* C
A B
-
*
A B
C
后序遍历 A B * C -3、后序遍历
-
+ /
a *
b -
e f
c d
先序遍历：
中序遍历：
后序遍历：
层次遍历：
- + a * b - c d / e f
-+a *b -c d /e f
- + a * b- c d/ e f
-+a *b -c d /e f
例：用二叉树表示算术表达式
+
*
A
*
/
E
D
C
B
先序遍历
+ * * / A B C D E
前缀表示中序遍历
A / B * C * D + E
中缀表示后序遍历
A B / C * D * E +
后缀表示层序遍历
+ * E * D / C A B
例：用二叉树表示算术表达式三、遍历算法
1、先序遍历
2、中序遍历
3、后序遍历
4、无递归 中序遍历
void Preorder( BiTree T,void(*visit)( BiTree) )
{
if (T) {
visit(T);
Preorder( T->lchild,visit );
Preorder( T->rchild,visit );
}
前序遍历
void inorder( BiTree T,void(*visit)( BiTree) )
{
if (T) {
inorder( T->lchild,visit );
visit(T);
inorder( T->rchild,visit );
}
}
中序遍历按层次遍历按层次遍历序列,
A,B,C,D,E,F,G,J,I
void Postorder( BiTree T,void(*visit)( BiTree) )
{
if (T) {
Postorder( T->lchild,visit );
Postorder( T->rchild,visit );
visit(T);
}
}
后序遍历
A
B C
D E F G
IJ
void pre( BiTree T,void(*visit)( BiTree ) )
{
if (T) {
visit(T);
pre( T->lchild,visit );
pre( T->rchild,visit );
}
}
主程序
Pre( T )
返回返回
pre(T R);
返回返回
pre(T R);
A
CB
D
T B
printf(B);
pre(T L);
T A
printf(A);
pre(T L);
T D
printf(D);
pre(T L);
T C
printf(C);
pre(T L);
返回
T
左是空返回
pre(T R);
T
左是空返回
T
右是空返回
T
左是空返回
T
右是空返回
pre(T R);
先序序列,A B D C
遍历算法的执行过程 ---例题说明
模拟算法对如图所示二叉树的中序遍历的执行过程。
A
DC
B
FE
G
H
inorder(^)
inorder(A)
inorder(B) A inorder(G)
inorder(C) B inorder(D) inorder(H) G norder(^)
inorder(^) C inorder(^)
inorder(E) inorder(F)D
inorder(^) H
inorder(^) E inorder(^) inorder(^) F inorder(^)
输出序列
CBEDFAHG
4、非递归算法
A
B
C D
E F
G
p
i
P->A
(1)
A
B
C D
E F
G
p
i
P->A
P->B
(2)
A
B
C D
E F
G
p i
P->A
P->B
P->C
(3)
p=NULL
A
B
C D
E F
G
i
P->A
P->B
访问,C(4)
p A
B
C D
E F
G
i
P->A
访问,C B(5)
A
B
C D
E F
G
i
P->A
P->D
访问,C B
p
(6)
A
B
C D
E F
G
i
P->A
P->D
P->E
访问,C B
p
(7)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E
p (8)
A
B
C D
E F
G
i
P->A
P->D
P->G
访问,C B E
P=NULL
(9)
A
B
C D
E F
G
i
P->A
访问,C B E G D
p
(11)
A
B
C D
E F
G
i
P->A
P->F
访问,C B E G D
p
(12)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E G
p
(10)
A
B
C D
E F
G
i
P->A
访问,C B E G D F
p=NULL
(13)
A
B
C D
E F
G
i
访问,C B E G D F A
p
(14)
i
访问,C B E G D F A
p=NULL
(15)
typedef enum { Travel,Visit } TaskType;
// Travel == 1:遍历,// Visit == 0:访问
typedef struct {
BiTree ptr; // 指向根结点的指针
TaskType task; // 任务性质
} ElemType;
,遍历左子树”,遍历右子树”,访问根结点”
4、中序遍历算法的非递归描述在写算法之前首先需定义栈的元素类型。
void InOrder_iter( BiTree BT )
{
// 利用栈实现中序遍历二叉树,T为指向二叉树的根结点的头指针
InitStack(S);
e.ptr=BT; e.task=Travel;
if (T) Push(S,e); // 布置初始任务
while(!StackEmpty(S)) {
Pop(S,e); // 每次处理一项任务
if (e.task==Visit) visit(e.ptr); // 处理访问任务
else if ( !e.ptr ) { // 处理非空树的遍历任务
p=e.ptr;
e.ptr=p->rchild; Push(S,e); // 最不迫切任务进栈
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
} //if
} //while
} //InOrder_iter
A T
A Te
A
B
D
C
E ^
^
^
^
^ ^
P
A VC TB T
e.ptr=BT; e.task=Travel; if(BT) Push(S,e);
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
B Te
A VC TB T A VC T
P D T
A VC T
B V^ T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
^ Te
P
D TA V
C T
B V^ T D T
A VC T
B V
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
D TA V
C T
B V D T
A VC T
e B V
输出 B
if(e.task==Visit) visit(e.ptr);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^P
D TA V
C T
e D T
A VC T
输出 B
A VC T^ T
D VE T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
e E T
输出 B
A VC T^ T
D VE T
A VC T^ T
D V
A VC T^ T
D V^ T
E V^ T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
e ^ T
输出 B
A VC T^ T
D V^ T
E V^ T
A VC T^ T
D V^ T
E V
A VC T^ T
D V^ T
e E V
输出 E
if(e.task==Visit) visit(e.ptr);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
e ^ T
A VC T^ T
D V^ T
A VC T^ T
D V
A VC T^ T
e D V
输出 D输出 BE
if(e.task==Visit) visit(e.ptr);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^P
e ^ T
A VC T^ T C TA VC T
e A V
输出 A输出 BED
if(e.task==Visit) visit(e.ptr);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
e C T
C T
输出 BEDA
^ TC V
^ T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
e ^ T
输出 BEDA
^ TC V
^ T
^ TC V
C Ve
^ T
输出 C
if(e.task==Visit) visit(e.ptr);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
e ^ T
输出 BEDAC
^ T
OVER
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
四,遍历算法的应用举例
2、求二叉树的深度 (后序遍历 )
1、建立二叉树的存储结构
4、计算表达式的值
3、复制二叉树 (后序遍历 )
1、建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立算法
(1) 以字符串的形式,根 -左子树 -右子树,定义一棵二叉树例如,
A(B(,C(,)),D(,))
A
B
C
D
以下列字符串表示以空白字符,”表示空树只含一个根结点的二叉树 A
以字符串,A,表示按先序遍历序列建立二叉树的二叉链表,
已知先序序列为：
A B C D E? G F
A
B
C D
E F
G
A ^
B
^ C ^ D
^ E ^ F ^
^ G ^
Status CreateBiTree(BiTree &T)
{
scanf(&ch);
if (ch==' ') T=NULL;
else
{
if (!(T = new BiTNode)) exit(OVERFLOW);
T->data = ch; // 生成根结点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return OK;
} // CreateBiTree A
T
B
C
D ^
^ ^
^ ^
A B C D
void CreatebiTree(BiTree &T){
// 在先序遍历二叉树过程中输入结点字符，建立二叉链表存储结 //构，指针 T指向所建二叉树的根结点
cin >> ch ；
if (ch=='#') T=NULL; // 建空树
else {
T = new BiTNode ; // "访问 "操作为生成根结点
T->data = ch;
CreateBiTree(T->lchild); // 递归建 (遍历 )左子树
CreateBiTree(T->rchild); // 递归建 (遍历 )右子树
}//else
}//CreateBiTree
2、求二叉树的深度 (后序遍历 )
算法基本思想,首先分析二叉树的深度和它的左、右子树深度之间的关系。
从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加 1。由此，需先分别求得左、右子树的深度，算法中访问结点的操作为,求得左、右子树深度的最大值，然后加 1 。
int Depth (BiTree T ) { // 返回二叉树的深度
if (!T) depthval = 0;
else {
depthLeft = Depth( T->lchild );
depthRight= Depth( T->rchild );
depthval = 1+(depthLeft>depthRight?depthLeft:depthRight);
}
return depthval;
}
void Depth(BiTree T,int level,int &dval) {
if ( T ) {
if (level>dval) dval = level;
Depth( T->lchild,level+1,dval );
Depth( T->rchild,level+1,dval );
}
}
//调用之前 level 的初值为 1,dval 的初值为 0.
void BiTreeDepth(BiTree T,int h,int &depth){
// h为 T指向的结点所在层次,T指向二叉树的根，则 h的初
//值为 1,depth为当前求得的最大层次,其初值为 0
if (T){
if (h>depth) depth=h;
BiTreeDepth(T->lchild,h+1,depth);
BiTreeDepth(T->rchild,h+1,depth);
}
}//BiTreeDepth
主函数调用：
d=0
BiTreeDepth(r,1,d)
int BiTreeDepth(BiTree T) {
// 后序遍历求 T所指二叉树的深度
if (!T) return 0;
else {
hL=BiTreeDepth(T->lchild);
hR=BiTreeDepth(T->rchild);
if (hL>=hR) return hL+1;
else return hR+1;
}
}//BiTreeDepth
A
B
C
D
E
F
G
H K
A例如，下列二叉树的复制过程如下：
newT
^ B E ^
C ^
^ D ^
F ^
G
^ H ^ ^ K ^
3、复制二叉树 (后序遍历 )
BiTNode *GetTreeNode(TElemType item,BiTNode *lptr,BiTNode *rptr )
{
if (!(T = new BiTNode)) exit(1);
T-> data = item; T-> lchild = lptr; T-> rchild = rptr;
return T;
}
生成一个二叉树的结点 (其数据域为 item,左指针域为 lptr,右指针域为 rptr)
BiTNode *CopyTree(BiTNode *T) {
if (!T) return NULL;
if (T->lchild ) newlptr = CopyTree(T->lchild); //复制左子树
else newlptr = NULL;
if (T->rchild ) newrptr = CopyTree(T->rchild); //复制右子树
else newrptr = NULL;
newT = GetTreeNode(T->data,newlptr,newrptr);
return newT;
} // CopyTree
4、计算表达式的值 (a+b*(c-d))-e/f
－
＋
*a
/
b -
dc
fe
-2
-1
-30
-4
1 -2
32
54
3.1 4.2 2.4 3.8 7.2 2.4abcd-*+ef/- （后缀表达式） opnd
0 1 2 3 4 5
数据结构的表示
a+b
(a+b)× c – d/ea+b× c
表达式的二叉树的表示,
a b
+
a
b c
×
+
a b
c
×
+
(a+b)× c
a b
c d e
-
×
+
/
特点,
操作数 为叶子结点运算符 为分支结点例右图所示的二叉树表达式
(a+b*(c-d))-e/f
若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：
-+a*b-cd/ef （前缀表达式）
按中序遍历,其中序序列为：
a+b*c-d-e/f （中缀表达式）
按后序遍历,其后序序列为：
abcd-*+ef/- （后缀表达式）
－
＋
*a
/
b -
dc
fe
double value(BiTree T,float opnd[]){
// 对以 T为根指针的二叉树表示的算术表达式求值，
// 操作数的数值存放在一维数组 opnd中
if (!T) return 0; // 空树的值为 0
if (T->data>=0) return opnd[T->data];
Lv = value(T->lchild,opnd); // 遍历左子树求第一操作数
Rv = value(T->rchild,opnd); // 遍历右子树求第二操作数
switch (T->data){
case PLUS,v = Lv + Rv;
case MINUS,v = Lv - Rv;
case ASTERISK,v = LV * Rv;
case SLANT,v = Lv / Rv;
default,ERROR("不合法的运算符 ");
} //switch
return v;
}//value
习题讨论：
1,求二叉树深度，或从 x结点开始的子树深度。
算法思路,只查各结点后继链表指针，若左 (右 )孩子的左 (右 )指针非空，则层次数加 1；否则函数返回。
技巧,递归时应当 从叶子开始向上计数，层深者保留。 否则不易确定层数。
2,按层次输出二叉树中所有结点。
算法思路,既然要求从上到下，从左到右，则 利用队列 存放各子树结点的指针是个好办法，而不必拘泥于递归算法。
技巧,当根结点入队后,令其左,右孩子结点入队,而左孩子出队时又令它的左右孩子结点入队,…… 由此便可产生按层次输出的效果 。
3 中序遍历的非递归 (迭代 )算法算法思路,若不用递归，则要实现二叉树遍历的,嵌套,规则，必用堆栈。可直接用 while语句和 push/pop操作。
4.判别给定二叉树是否为完全二叉树（即顺序二叉树）。
算法思路,完全二叉树的特点是：没有左子树空而右子树单独存在的情况 (前 k-1
层都是满的，且第 k层左边也满） 。
技巧,按层序遍历方式,先把所有结点 （ 不管当前结点是否有左右孩子 ） 都入队列,若为完全二叉树,则层序遍历时得到的肯定是一个连续的不包含空指针的序列,
如果序列中出现了空指针,则说明不是完全二叉树 。
三,线索二叉树
1、何谓线索二叉树？
2、线索链表的遍历算法
3、如何建立线索链表？
1）什么是线索二叉树
2）线索二叉树的构造利用二叉链表中空的指针域指出结点在遍历序列中的直接前驱和直接后继 ;这些指向前驱和后继的指针称为 线索,加了线索的二叉树称为 线索二叉树,
利用链结点的 空 的 左指针域 存放该结点的 直接前驱的地址,空 的 右指针域 存放该结点 直接后继 的地址 ;
非空指针域仍然存放结点的左孩子或右孩子的地址,
1、何谓线索二叉树？
线索二叉树 （ Threaded Binary Tree） 的理解普通二叉树只能找到结点的左右孩子信息,而该结点的直接前驱和直接后继只能在遍历过程中获得。
若将 遍历后对应的有关前驱和后继预存 起来，则从 第一个结点 开始就能很快“顺藤摸瓜”而遍历整个树了。
两种解决方法增加两个域,fwd和 bwd；
利用空链域（ n+1个空链域）
存放前驱指针 存放后继指针如何预存这类信息？
例如中序遍历结果,B D C E A F H G，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继！
可能是根、或最左（右）叶子指向该线性序列中的,前驱,和,后继,的指针，称作,线索,
与其相应的二叉树，
称作,线索二叉树,
包含,线索,的存储结构，称作,线索链表,
A B C D E F G H K
^ D ^
C ^
^ B E ^
规 定,1）若结点有左子树，则 lchild指向其左孩子；
否则,lchild指向其直接前驱 (即线索 )；
2）若结点有右子树，则 rchild指向其右孩子；
否则,rchild指向其直接后继 (即线索 ) 。
为了避免混淆，增加两个标志域，如下图所示：
lchild LTag data RTag rchild
约定,当 Tag域为 0时,表示正常情况 ;
当 Tag域为 1时,表示线索情况,
注,在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为 0时，则需要通过一定运算才能找到它的后继。
线索链表,用前页结点结构所构成的二叉链表线索,指向结点前驱和后继的指针线索二叉树,加上线索的二叉树（图形式样）
线索化,对二叉树以某种次序遍历使其变为线索二叉树的过程
data A G E I D J H C F B
ltag 0 0 1 1 1 1 0 1 0 1
rtag 0 0 0 1 0 1 0 1 1 1
A
G
E
I
D
J
H
C F
B
例,带了两个标志的某先序遍历结果如表所示，请画出对应二叉树。
A
B C
GE
I
D
H
F
root
悬空？
悬空？
解,该二叉树中序遍历结果为,H,D,I,B,E,A,F,C,G
所以添加线索应当按如下路径进行：
例,画出以下二叉树对应的中序线索二叉树。
为避免悬空态，应增设一个头结点
typedef struct BiThrNod {
TElemType data;
struct BiThrNode *lchild,*rchild; // 左右指针
PointerThr LTag,RTag; // 左右标志
} BiThrNode,*BiThrTree;
3）线索链表的类型描述
typedef enum { Link,Thread } PointerThr;
// Link==0:指针,Thread==1:线索对应的中序线索二叉树存储结构如图所示：
0 0A
0 0C0 0B
1 1E 1 1F 1 1G0 0D
1 1I1 1H
注：此图中序遍历结果为,H,D,I,B,E,A,F,C,G
0 --root 0
※ 中序遍历的第一个结点?
※ 在中序线索化链表中结点的后继?
左子树上处于“最左下”（没有左子树）
的结点若 无右子树,则为 后继线索所指结点否则为 对其右子树进行中序遍历时访问的第一个结点
2、线索二叉树的遍历
–按中序线索化二叉树
–遍历中序线索二叉树在中序线索二叉树中找结点后继的方法：
（ 1）若 rt=1,则 rc域直接指向其后继
（ 2）若 rt=0,则结点的后继应是其右子树的左链尾
（ lt=1)的结点
A
B
C
D
E
0 A 0
1 B 0 0 D 1
1 C 1 1 E 1
T
中序序列,BCAED
带头结点的中序线索二叉树
0 1
void InOrderTraverse_Thr(BiThrTree T,
void (*Visit)(TElemType e)) {
p = T->lchild; // p指向根结点
while (p != T) { // 空树或遍历结束时,p==T
while (p->LTag==Link) p = p->lchild; // 第 一个结点
while (p->RTag==Thread && p->rchild!=T) {
p = p->rchild; Visit(p->data); // 访问后继结点
}
p = p->rchild; // p进至其右子树根
}
} // InOrderTraverse_Thr
3、线索二叉树的生成线索化过程就是 在遍历过程中修改空指针 的过程：
将空的 lchild改为结点的直接前驱；
将空的 rchild改为结点的直接后继。
非空指针呢？仍然指向孩子结点（称为,正常情况,）
目的,在 依某种顺序遍历 二叉树时修改空指针，添加前驱或后继。
注解,为方便添加结点的前驱或后继，需要设臵两个指针：
p指针 → 当前结点之指针； pre指针 → 前驱结点之指针。
技巧,当结点 p的左 /右域为空 时，只改写它的左域 (装入前驱 pre),
而其右域（后继）留给下一结点来填写。
或者说，当前结点的指针 p应当送到前驱结点的空右域中。
若 p->lchild＝ NULL,则 {p->Ltag=1;p->lchild＝ pre;}
//p的前驱结点指针 pre存入左空域若 pre->rchild＝ NULL,则 {pre->Rtag＝ 1;pre->rchild=p;}
//p存入其前驱结点 pre的右空域线索二叉树的生成算法在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的,前驱,和,后继,信息。遍历过程中，附设指针 pre,
并始终保持指针 pre指向当前访问的、指针 p所指结点的前驱。
void InOrderThreading(BiThrTree &H,BiThrTree T)
{ H = new BiThrNode;
H->lchild = T; H->rchild = NULL;
if ( !T ) { H->pred = H; H->succ = H; }
else {
pre = H;
InThreading( T,pre );
pre->succ = H; H->pred = pre;
}
} void InThreading(BiThrTree p,BiThrTree &pre ){
if (p) {
InThreading(p->lchild);
pre->succ = p; p->pred = pre;
pre = p; // 保持 pre 指向 p 的前驱
InThreading(p->rchild);
}
}1 1
p
0 1
pre
6.3 树和森林一、树和森林的定义二,树和森林的存储结构三,树和森林的的遍历一、树和森林 的定义
1、树的定义
2,森林的定义
3、对 树和森林的操作
1、树的基本概念树 是由 n?0 个结点组成的有穷集合 (不妨用 D表示 )以及结点之间关系组成的集合构成的结构。
当 n=0 时，称该树为 空树 ；
在任何一棵非空的树中，有一个特殊的结点 t?D，
称之为该树的根结点；其余结点 D–{t}被分割成 m>0
个不相交的子集 D1,D2,…,D m,其中每一个子集 Di又为一棵树，分别称之为 t 的 子树 。
递归定义一,树的定义注 1,过去许多书籍中都定义树为 n≥1,曾经有,空树不是树,的说法，但现在树的定义已修改。
注 2,树的定义具有 递归性,即树中还有树。
JIHGFE
A
C XB
A的第 1棵子树 A的第 3棵子树
A的第 2棵子树二,树 (逻辑上 )的特点
1,有且仅有一个结点没有前驱结点,该结点为树的根结点。
2,除了根结点外,每个结点有且仅有一个直接前驱结点。
3,包括根结点在内，每个结点可以有多个后继结点。
A
只有根结点的树
A
B C D
E F G H I J
K L M
有子树的树 根子树任何一棵非空树是一个二元组
Tree = （ root,F）
其中,root 被称为根结点,
F 被称为子树森林
2、森林是 m（ m≥ 0）棵互不相交的树的集合
A
root
B
E F
K L
C
G
D
H I J
M
F
3、树 的表示法
图形表示法
嵌套集合表示法
广义表表示法
目录表示法
左孩子－右兄弟表示法
1） 图形表示法教师 学生 其他人员
2002级 2003级 2004级 2005级
……
华中师范大学物理计算机系 数学 ……
叶子根子树
2）广义表表示法
( A ( B ( E ( K,L ),F ),C ( G ),D ( H ( M ),I,J ) )
根作为 由子树森林组成的 表的名字写在表的左边
data link 1 link 2,.,link n
麻烦问题：应当开设多少个链域?
A( )
T1 T3T2树根
B(E,F(K,L)),C(G),D(H,I,J(M))
A
B C D
E F G H I J
MK L
例如,
3）左孩子－右兄弟表示法
A
B C D
E F G H I J
K L M
( A ( B ( E ( K,L ),F ),C ( G ),D ( H ( M ),I,J ) ) )
数据左孩子 右兄弟
Root(T) // 求树的根结点查找类：
Value(T,cur_e) // 求当前结点的元素值
Parent(T,cur_e) // 求当前结点的双亲结点
LeftChild(T,cur_e) // 求当前结点的最左孩子
RightSibling(T,cur_e) // 求当前结点的右兄弟
TreeEmpty(T) // 判定树是否为空树
TreeDepth(T) // 求树的深度
TraverseTree( T,Visit() ) // 遍历
4、树的操作
InitTree(&T) // 初始化臵空树插入类：
CreateTree(&T,definition) // 按定义构造树
Assign(T,cur_e,value) // 给当前结点赋值
InsertChild(&T,&p,i,c) // 将以 c为根的树插入为结点 p的第 i棵子树
ClearTree(&T) // 将树清空删除类：
DestroyTree(&T) // 销毁树的结构
DeleteChild(&T,&p,i) // 删除结点 p的第 i棵子树要明确：
1,普通树（即多叉树）若不转化为二叉树，则运算很难实现。
2,二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够,遍历,的基础上！
（ 遍历,指每个结点都被访问且仅访问一次，不遗漏不重复 )。
5、若干术语
——即上层的那个结点 (直接前驱 )
——即下层结点的子树的根 (直接后继 )
——同一双亲下的同层结点（孩子之间互称兄弟）
——即双亲位于同一层的结点（但并非同一双亲）
——即从根到该结点所经分支的所有结点
——即该结点下层子树中的任一结点
A
B C
GE I
D
HF J
MLK
根叶子森林有序树无序树
——即根结点 (没有前驱 )
——即终端结点 (没有后继 )
——指 m棵不相交的树的集合 (例如删除 A后的子树个数 )
双亲孩子兄弟堂兄弟祖先子孙
——结点各子树从左至右有序，不能互换（左为第一）
——结点各子树可互换位臵。
5、若干术语（续）
——即树的数据元素
——结点挂接的子树数
（有几个直接后继就是几度
，亦称“次数”）
结点结点的度结点的层次终端结点分支结点树的度树的深度
(或高度 )
A
B C
GE I
D
HF J
MLK
——从根到该结点的层数（根结点算第一层）
——即度为 0的结点，即叶子
——即度不为 0的结点（也称为内部结点）
——所有结点度中的最大值 （ Max{各结点的度 }）
——指所有结点中最大的层数 （ Max{各结点的层次 }）
问,右上图中的结点数＝ ；树的度＝ ；树的深度＝13 3 4
A
B C D
E F G H I J
K L M
结点 A的度,3
结点 B的度,2
结点 M的度,0
叶子,K,L,F,G,M,I,J
结点 A的孩子,B,C,D
结点 B的孩子,E,F
结点 I的双亲,D
结点 L的双亲,E
结点 B,C,D为兄弟结点 K,L为兄弟树的度,3
结点 A的层次,1
结点 M的层次,4
树的深度,4
结点 F,G为堂兄弟结点 A是结点 F,G的祖先线性结构 树型结构第一个数据元素
(无前驱 )
根结点 (无前驱 )
最后一个数据元素
(无后继 )
多个叶子结点 (无后继 )
其它数据元素
(一个前驱、一个后继 )
其它数据元素
(一个前驱、多个后继 )
树的逻辑结构
(特点 )：一对多 (1:n)，有多个直接后继 (如家谱树、目录树等等 )，但只有一个根结点，
且 子树之间互不相交 。
树的存储结构讨论 1,树是非线性结构，该怎样存储？
——仍然有顺序存储、链式存储等方式。
讨论 3,树的 链式存储 方案应该怎样制定？
可规定为,从上至下,从左至右 将树的结点依次存入内存 。
重大缺陷,复原困难 (不能唯一复原就没有实用价值 )。
讨论 2,树的 顺序存储 方案应该怎样制定？
可用多重链表,一个前趋指针,n个后继指针。
细节问题,树中结点的结构类型样式该如何设计？
即应该设计成,等长,还是,不等长,？
缺点,等长结构太浪费（每个结点的度不一定相同）；
不等长结构太复杂（要定义好多种结构类型）。
解决思路,先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。
二叉树二、树和森林 的存储结构
1、双亲表示法
2、孩子连表示法
3、二叉链（孩子兄弟）表示法
4、二叉树、树和森林的转换二、树和森林的存储方式树有三种常用存储方式：
①双亲表示法
②孩子表示法
③孩子兄弟表示法
1、用双亲表示法来存储思路,用一组 连续空间 来存储树的结点，同时在每个结点中 附设一个指示器,指示其双亲结点在链表中的位臵。
parentsdata
结点结构
data parents
1
树结构
2
3
n
1、双亲表示法
A
B C D
E F
G
0 A -1
1 B 0
2 C 0
3 D 0
4 E 2
5 F 2
6 G 5
r=0
n=6
data parent
缺点：求结点的孩子时需要遍历整个结构。
C语言的类型描述
#define MAX_TREE_SIZE 100
结点结构,
typedef struct PTNode {
Elem data;
int parent; // 双亲位臵域
} PTNode;
树结构,
typedef struct {
PTNode nodes [MAX_TREE_SIZE];
int r,n; // 根结点的位置和结点个数
} PTree;
data parent
思路,将每个结点的 孩子 排列起来，形成一个 带表头
（装父结点） 的线性表 （ n个结点要设立 n个链表）；
再将 n个表头用数组存放 起来，这样就形成一个 混合结构。
例如,
a
b
e
c
d
f hg
d e
f g h
g
f
e
d
c
b
a
h
1
2
3
4
5
6
7
8
b c
2、孩子链表表示法
C语言的类型描述,
孩子结点结构
typedef struct CTNode {
int child;
struct CTNode *next;
} *ChildPtr;
双亲结点结构
typedef struct {
Elem data;
ChildPtr firstchild; // 孩子链的头指针
} CTBox;
树结构 typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int n,r; // 结点数和根结点的位置
} CTree;
child next
思路,用 二叉链表 来表示树，但链表中的两个指针域含义不同。
左指针指向该结点的第一个孩子；
右指针指向该结点的下一个兄弟结点。
nextsiblingdatafirstchild
3、用孩子兄弟表示法来存储指向左孩子 指向右兄弟
A
B C D
E F
G
root
A
B
C
E D
F
G
3、树的二叉链表 (孩子 -兄弟）表示法
root
A
B
C
E D
F
G
C语言的类型描述结点结构
typedef struct CSNode{
Elem data;
struct CSNode *firstchild,*nextsibling;
} CSNode,*CSTree
firstchild data nextsibling
1）森林到二叉树的转换 ---方法
如果森林用有序表 T=(T1,T2,……,Tm)来表示，
则将森林 T转换为对应的二叉树 BT的形式化描述如下：
如果 m=0，则 BT为空；否则依次作如下操作,
将 T1的根作为 BT的根；
将 T1的子树森林转换为 BT的左子树；
将 (T2,T3,……,Tm)转换为 BT的右子树。
4、森林、树和二叉树的转换
A
B C D
E
F
G
H
J
I
A
B C D
E
F
G
H
J
I
A
B
C
D
E
F G
H
J
I
1）森林转二叉树 兄弟相连 长兄为父孩子靠左 头根为根
1,将各棵树分别转换成二叉树
2,将每棵树的根结点用线相连
3,以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构
2）二叉树到森林的转换
将二叉树 BT转换为森林 T＝ (T1,T2…… Tm)
的形式化描述如下：
若 BT不空，则依次执行如下操作：
将 BT的根转换为 T1的根；
将 BT的左子树转换为 T1的子树森林；
将 BT的右子树转换为（ T2,…… Tm）
2）二叉树转换成森林
–抹线,将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
–还原,将孤立的二叉树还原成树
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B C D
E
F
G
H I
J
3）将树转换成二叉树
– 加线,在兄弟之间加一连线
– 抹线,对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
– 旋转,以树的根结点为轴心，将整树顺时针转 45°
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B
C
D
E
F
G H
I树转换成的二叉树其右子树一定为空
4）将 二叉 树转换成树
– 加线,若 p结点是双亲结点的左孩子，则将 p的右孩子，右孩子的右孩子,…… 沿分支找到的所有右孩子，都与 p的双亲用线连起来
– 抹线,抹掉原二叉树中双亲与右孩子之间的连线
– 调整,将结点按层次排列，形成树结构
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
IA
B C D
E F G H I
树与二叉树转换
A
CB E
D
树 A
B
C
D E
二叉树
A ^
^ B
C
^ D ^
^ E ^
A ^
^ B C
^ D ^
^ E ^
A ^
^ B
C
^ D ^ ^ E ^
对应三、树和森林 的遍历
1、树的遍历
2、森林的遍历
3、树的遍历举例树和森林的遍历 遍历 深度遍历（先序、中序、后序）
广度遍历（层次）
先序遍历
访问根结点；
依次先序遍历根结点的每棵子树。
1、树的遍历例如,a
b
d
ec 先序序列：
后序序列：
a b c d e
b d c e a
后序遍历
依次后序遍历根结点的每棵子树；
访问根结点。
树没有中序遍历
（因子树不分左右）
按层次遍历,若树不空，则自上而下自左至右访问树中每个结点。
层次遍历时顶点的访问次序：
A
B C D
E F G
H
I J K
先根遍历时顶点的访问次序：
A B E F C D G H I J K
后根遍历时顶点的访问次序：
E F B C I J K H G D A
A B C D E F G H I J K
1）树（森林）的遍历 ---先序遍历
先序遍历森林 T=(T1,T2……Tm)的描述如下：
若 T不空，则依次执行如下操作：
访问 T1的根；
先序遍历 T1的子树森林；
先序遍历森林（ T2,T3……Tm）；
void preorder(Tnode *t) //先序遍历森林
{ if (t!=NULL)
{ visite(t); //访问结点
preorder(t->firstson); //先序遍历 t的子树森林
preorder(t->nextbrother);
} //先序遍历 t的兄弟森林
}
2）树（森林）的遍历 ---后序遍历?
后序遍历森林 T=(T1,T2……Tm)的方法描述如下：
如果 T不空，则依次执行如下操作：
后序遍历 T1的子树森林；
访问 T1的根；
后序遍历森林（ T2,T3……Tm）；
void postorder(Tnode *t)
{ if (t!=NULL)
{ postorder(t->firstson); //后序遍历树 t的子树森林
visite(t); //访问树 t的根结点
postorder(t->nextbrother);
} //后序遍历 t的后续兄弟森林
} 返回讨论：若采用 先转换后遍历 方式，结果是否一样？
a
b
d e
c
先序遍历：
后序遍历：
中序遍历：
d e c b a
a
b
d
ec
a b c d e
b d c e a
1,树的 先序 遍历二法相同；
2,树的 后序 遍历相当于对应二叉树的 中序 遍历；
3,树没有 中序 遍历，因为子树无左右之分。
结论：
先序遍历
若森林为空，返回；
访问森林中第一棵树的根结点；
先序遍历第一棵树中根结点的子树森林；
先序遍历除去第一棵树之后剩余的树构成的森林。
中序遍历
若森林为空，返回；
中序遍历森林中第一棵树的根结点的子树森林；
访问第一棵树的根结点；
中序遍历除去第一棵树之后剩余的树构成的森林。
2、森林的遍历
A
B C D
E
F
G
H
J
I
B C D
E F G
H
I J K
(1) 森林中第一棵树的根结点；
(2) 森林中第一棵树的子树森林；
(3) 森林中其它树构成的森林。
可以分解成三部分：森林讨论,若采用,先转换，后遍历,方式，结果是否相同？
例如：
A
B C D
E
F
G
H
J
I
先序序列：
中序序列：
A B C D E F G H I J
B C D A F E H J I G
A
B
C
D
E
F G
H
J
I
先序序列：
中序序列：
A B C D E F G H I J
B C D A F E H J I G
结论,森林的先序和中序遍历在两种方式下的结果相同。
（但 森林的后序遍历则不一定 ）
树的遍历和二叉树遍历的对应关系？
先根遍历后根遍历树 二叉树森林先序遍历 先序遍历中序遍历 中序遍历设树的存储结构为孩子兄弟链表
typedef struct CSNode{
Elem data;
struct CSNode *firstchild,*nextsibling;
} CSNode,*CSTree;
1）求树的深度
2）输出树中所有从根到叶子的路径
3）建树的存储结构
3、树的遍历举例
int TreeDepth( CSTree T )
{ // T 是树的孩子链表存储结构,返回该树的结点和深度
if ( T.n == 0) return 0;
else return Depth( T,T.r );
} // TreeDepth
1）求树的深度
int TreeDepth(CSTree T)
{
if (T==NULL) return 0;
else {
h1 = TreeDepth(T->firstchild);
h2 = TreeDepth(T->nextsibling);
return Max(h1+1,h2)
}
}
int Depth( CTree T,int root )
{
max = 0;
p = T.nodes[root].firstchild;
while ( p ) {
h = Depth( T,p->child );
if ( h > max ) max = h;
p = p->nextchild;
}//while
return max+1;
}
A
B C D
E F G
H
I J K
2）输出树中所有从根到叶子的路径例如：对左图所示的树，
其输出结果应为：
A B E
A B F
A C
A D G H I
A D G H J
A D G H K
void AllPath( BiTree T,Stack& S )
{ // 输出二叉树上从根到所有叶子结点的路径
if (T) {
Push( S,T->data );
if (!T->Lchild && !T->Rchild ) StackTraverse(S);
else { AllPath( T->Lchild,S ); AllPath( T->Rchild,S ); }
Pop(S);
} // if(T)
} // AllPath
void OutPath( Bitree T,Stack& S )
{ // 输出森林中所有从根到叶的路径
while ( !T ) {
Push(S,T->data );
if ( !T->firstchild ) stackTraverse(S);
else OutPath( T->firstchild,S );
Pop(S);
T = T->nextsibling;
} // while
} // OutPath
A
B C D
E F
G
例如,对下列所示树的输入序列应为,
(‘#’,‘A’)
(‘A’,‘B’)
(‘A’,‘C’)
(‘A’,‘D’)
(‘C’,‘E’)
(‘C’,‘F’)
(‘E’,‘G’)
A
B
C
D
(‘#’,’)
’,’)
可见，算法中需要一个队列保存已建好的结点的指针
3）建树的存储结构 （ 不同的定义相应有不同的算法）
假设以二元组 (F,C)的形式自上而下、自左而右依次输入树的各边，
建立树的孩子 -兄弟链表。
void CreatTree( CSTree &T )
{
T = NULL;
for ( scanf(&fa,&ch); ch!=; scanf(&fa,&ch);) {
p = GetTreeNode(ch); // 创建结点
EnQueue(Q,p); // 指针入队列
if (fa==) T=p; // 所建为根结点
else { //非根结点的情况
GetHead(Q,s); // 取队列头元素 (指针值 )
while (s->data != fa ) { // 查询双亲结点
DeQueue(Q,s); GetHead(Q,s);
}
if (!(s->firstchild)) { s->firstchild = p; r = p; } //链接第一结点
else { r->nextsibling = p; r = p; } //链接其它孩子结点
}
} // for
} // CreateTree
6.4 树的应用一、堆和堆排序二、二叉排序树三,Huffman树一、堆排序堆的定义,n个元素的序列 (k1,k2,……kn)，当且仅当满足下列关系时，称之为 堆或 (i=1,2,…..,?n/2?)ki?k2ik
i?k2i+1
ki?k2i
ki?k2i+1
例（ 96,83,27,38,11,9）
例（ 13,38,27,50,76,65,49,97）
96
27
91138
83
13
2738
49657650
97
可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中
n个元素的最小值或最大值
堆排序,将无序序列建成一个堆，得到关键字最小
（或最大）的记录；输出堆顶的最小（大）值后，使剩余的 n-1个元素重又建成一个堆，则可得到 n个元素的次小值；重复执行，得到一个有序序列，这个过程叫 堆排序
堆排序需解决的两个问题：
– 如何由一个无序序列建成一个堆？
– 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？
第二个问题解决方法 ——筛选
– 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，
直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”
例 含 8个元素的无序序列（ 49,38,65,97,76,13,27,50）
49
6538
27137697
50
49
6538
27137650
97
49
1338
27657650
97
49
1338
27657650
97
13
2738
49657650
97
第一个问题解决方法
–方法：从无序序列的第?n/2?个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选例,小顶堆,降序排序
13
2738
49657650
97
97
2738
49657650
13
输出,13
27
4938
97657650
13
输出,13
97
4938
27657650
13
输出,13 27
38
4950
27657697
13
输出,13 27
65
4950
27387697
13
输出,13 27 38
49
6550
27387697
13
输出,13 27 38
76
6550
27384997
13
输出,13 27 38 49
50
6576
27384997
13
输出,13 27 38 49
97
6576
27384950
13
输出,13 27 38 49 50
65
9776
27384950
13
输出,13 27 38 49 50
97
6576
27384950
13
输出,13 27 38 49 50 65
76
6597
27384950
13
输出,13 27 38 49 50 65
97
6576
27384950
13
输出,13 27 38 49 50 65 76
97
6576
27384950
13
输出,13 27 38 49 50 65 76 97
void HeapSort ( HeapType &H ) {
// 对顺序表 H进行堆排序。
for ( i=H.length/2; i>0; --i )
HeapAdjust ( H,i,H.length );//把 H.r[1..H.length]建成大顶堆
w=H.r[1] ; H.r[1]= H.r[H.length]; H.r[H.length]=w;
//交换 "堆顶 "和 "堆底 "的记录
for ( i=H.length-1; i>1; --i ) {
HeapAdjust(H,1,i);
// 从根开始调整，将 H.r[1..i] 重新调整为大顶堆
w=H.r[1]; H.r[1]=H.r[i]; H.r[i]=w;
// 将堆顶记录和当前的“堆底”记录相互交换
// 使已有序的记录堆积到底部
}
} // HeapSort
void HeapAdjust (HeapType &H,int s,int m) {
// 已知 H.r[s..m]中记录的关键字除 H.r[s].key之外均满足堆的定义，
//本函数依据关键字的大小对 H.r[s]进行调整，使 H.r[s..m]成为一个
//大顶堆 (对其中记录的关键字而言 )
rc = H.r[s]; // 暂存根结点的记录
for ( j=2*s; j<=m; j*=2 ) { // 沿 key较大的孩子结点向下筛选
if ( j<m && H.r[j].key<H.r[j+1].key ) ++j;
// j为 key较大孩子记录的下标
if ( rc.key >= H.r[j].key ) break; // 不需要调整
H.r[s] = H.r[j]; s = j; // 把大关键字记录往上调
}
H.r[s] = rc; // 回移筛选下来的记录
} // HeapAdjust
30
27
91138
83
时间复杂度：最坏情况下 T(n)=O(nlogn)
空间复杂度,S(n)=O(1)
二、二叉排序树
1、二叉排序树的定义
2、二叉排序树的创建
3、二叉排序树的查找
4、二叉排序树的插入
5、二叉排序树的删除二、二叉排序树
1,二叉排序树的定义每一棵子树分别也是二叉排序树,
二叉排序树或者为空二叉树,或者为具有以下性质的二叉树,
若根结点的左子树不空,则左子树上所有结点的值都小于根结点的值 ;
若根结点的右子树不空,则右子树上所有结点的值都大于或者等于根结点的值 ;
递归定义
10
183
8 122
7
3
30
60
58 73
38 64
50
100503510 70
40
中序序列,
10,30,35,38,40,50,50,58,60,64,70,73,100
中序遍历二叉排序树可得到一个关键字的有序序列
2、二叉排序树的建立 (逐点插入法 )
设 K=( k1,k2,k3,…,kn )为具有 n 个数据元素的序列。从序列的第一个元素开始,依次取序列中的元素,每取一个元素 ki,按照下述原则将 ki 插入到二叉树中,
1,若 二叉树 为空,则 ki 作为该二叉树的根结点；
2,若 二叉树 非空,则将 ki 与该二叉树的根结点的值进行比较,若 ki 小于根结点的值,则将 ki插入到根结点的左子树中 ; 否则,将 ki 插入到根结点的右子树中。
将 ki插入到左子树或者右子树中仍然遵循上述原则,
例 K = ( 50,35,70,40,50,65,20,80 )
空 50
35
50
40
7035
50
7035
50
5040
7035
50
65
5040
7035
50
20
65
5040
7035
50
8020
65
5040
7035
50
3、二叉排序树的查找查找过程若二叉排序树为空,则查找失败,结束 。
若二叉排序树非空,则将 被查找元素与二叉排序树的根结点的值进行比较,若等于根结点的值,则查找成功,返回 被查到元素所在链结点的地址,查找结束 ;
若小于根结点的值,则到根结点的左子树中重复上述查找过程 ; 若大于根结点的值,则到根结点的右子树中重复上述查找过程 ; 直到查找成功或者失败。
50
35 75
40 65
38 70
T
^
^ ^^ ^^^
^ ^ ^^^ ^36 66 72
25 80
p
p
p
pp
p
p
p=nil
key=70key=45
查找成功！查找失败！
二叉排序树的插入
– 插入原则,若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
– 二叉排序树生成,从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
4、二叉排序树的插入
50
30
10
90
10070
60
T
^ ^ ^ ^ ^
^^ p 80 ^^p 80 ^^
item=80
插入算法例 { 10,18,3,8,12,2,7,3 }
10 10
18
10
183
10
183
8
10
183
8 12
10
183
8 122
10
183
8 122
7
10
183
8 122
7
3
void Insert_BST( BiTree &T,KeyType e ) {
// 在以 T为根指针的二叉排序树中插入记录 e
s = new BiTNode; // 生成新的结点
s ->data = e; s->lchild = NULL; s->rchild = NULL;
if (!T) T = s; // 插入的结点为根结点
else {
p = T;
while ( p) // 查找插入位置
if ( e,key< p->data,key)
{ f = p; p = p->lchild; } // 应插入在左子树中
else
{ f = p; p = p->rchild; } // 应插入在右子树中
if ( e.key < f->data.key ) f->lchild = s;
// 插入为 f 所指结点的左子树根
else f->rchild = s; // 插入为 f所指结点的右子树根
} //else
} // Insert_BST
10
183
8
void BSTSort( SqTable &L )
{
// 利用二叉排序树对顺序表 L进行排序
BiTree T = NULL; // 初始化二叉排序树为空树
for ( i=1; i<L.length; ++i)
Insert_BST( T,L.r[i] ); // 按顺序表 L构造二叉排序树
i = 0;
InOrder( T,Output(T,L,i) ); // 中序遍历二叉排序树
// 通过函数指针引用 Output,将排序的记录由小到大输出至 L.r[i]
} // BSTSort
其中函数 Output的具体实现如下：
void Output ( BiTree T,SqTable &L,int & i )
{
L.r[++i]=T->data;
}
50
35 75
40 65
38 70
T
^
^
^
^
^ ^ ^
^
50
35 75
40 65
38 70
T
^
^
^
^
^ ^ ^
^
1,被删除结点为叶结点,则直接删除,
2,被删除结点无左子树,则用右子树的根结点取代被删除结点,
3,被删除结点无右子树,则用左子树的根结点取代被删除结点,
5、二叉排序树的删除
50
36 75
40 65
38 70
T
^
^ ^^ ^^^
^
^^^ ^66 72
25 80
50
35 72
40 65
38 70
T
^
^ ^^ ^^^
^ ^
^
^ ^36 66
25 80
50
35 75
40 65
38 70
T
^
^ ^^ ^^^
^ ^ ^^^ ^36 66 72
25 80
4,被删除结点的左、右子树都存在,则用被删除结点的右子树中值最小的结点 (或被删除结点的左子树中值最大的结点 )取代被删除结点,
删除算法例 80
50 120
60 110 150
55 70
53
删除 50
80
60 120
110 15055 70
53
删除 60
80
55 120
110 15053 70
10
4 25
8 13
5
4
删除 10
8
4 25
5 13
4
删除 5
8
4 25
4 13
三,Huffman树
1,最优树与 Huffman树
2,Huffman树的构造
3,Huffman树的实现
4,Huffman树的应用路 径,
路径长度,
树的路径长度,
带权路径长度,
树的带权路径长度,
霍 夫 曼 树,
1,Huffman树定义最优二叉树（ 霍夫曼 树）
由一结点到另一结点间的分支所构成路径上的分支数目从树根到 每一结点 的路径长度之和。
结点到根的路径长度与结点上权的乘积预备知识：若干术语树中所有 叶子结点 的带权路径长度之和带权路径长度最小的树。
a→e 的路径长度＝
树长度＝
2
10
2
4
5 9
WPL = w1*l1 + w2*l2 + … + wn*ln
其中,n为树中叶子结点的个数；
wi为第 i个叶子结点的权值；
l1为第 i个叶子结点的路径长度。
例 有 4个结点，权值分别为 7,5,2,4，构造有 4个叶子结点的二叉树
a b c d
7 5 2 4
WPL=7*2+5*2+2*2+4*2=36d
c
a b
2
4
7 5
WPL=7*3+5*3+2*1+4*2=46
a
b
c d
7
5
2 4
WPL=7*1+5*2+2*3+4*3=35
=
=
n
k
KK LWWPL
1
哈夫曼 树 则 是,WPL 最小的树。
哈夫曼树判定树 在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。
例 将学生百分成绩按分数段分级的程序。
若学生成绩分布是均匀的,可用图 (a)二叉树结构来实现。
a<60
a<70
a<80
a<90
不及格中等良好 优秀及格
Y N
Y N
Y N
Y N
(a)
输入 10000个数据，则需进行 31500次比较。
分数 0—59 60—69 70—79 80—89 90—99
比例 0.05 0.15 0.4 0.3 0.10
70≤a≤ 80
a<60
80≤a<90
60≤a<70
(b)
(c)
学生成绩分布不是均匀的情况：
以比例数为权构造一棵哈夫曼树,如 （ b)判断树所示 。
再将每一比较框的两次比较改为一次,可得到 （ c)判定树 。
输入 10000个数据，仅需进行 22000次比较。
2,Huffman树的构造按照 Huffman树的定义,Huffman最早提出了构造最优树的方法，其基本 思想 是：
⑴ 由给定的 n个权值构成 n棵二叉树的集合 F，其中每一棵二叉树中只有一个带权的根结点；
⑵ 在 F中选取两棵根结点权值最小的二叉树作为左、右子树构造一棵新的二叉树，
且臵新的二叉树的根结点的权值为左、
右子树上根结点权值之和；
⑶ 在 F中删除这两棵二叉树，同时将新得到的二叉树加入到 F中；
⑷ 重复⑵和⑶，直到 F中只含一棵二叉树为止。
例
a
7
b5 c
2
d
4
a
7
b5
c
2
d
4
6
a
7
b5
c
2
d
4
6
11
a
7
b5
c
2
d
4
6
11
18
例 w={5,29,7,8,14,23,3,11}
5 1429 7 8 23 3 11
1429 7 8 23 11
35
8
87
151429 23
35
811
11
35
8
191429 23
87
15
11
35
8
1929 23
14
87
15
29
29
14
87
15
29
11
35
8
1923
42
11
35
8
1923
42
29
14
87
15
29
58
11
35
8
1923
42
29
14
87
15
29
58
100
9
例如,已知权值 W={ 5,6,2,9,7 }
5 6 2 7
5 2
76 9 7
6 7
139
5 2
7
9
5 2
7
16
6 7
13
290
0 0
0
1
1 1
100 01 11
100 101
3,Huffman编码规则：
左,0” 右,1”，是一种前缀码，也称为最小冗余编码、紧致码，等等，它是数据压缩学的基础。
typedef struct {
int weight;
int lchild,rchild;
} HTNode
typedef struct {
HTNode *HTree;
int root;
}Huffman Tree;
3,Huffman树实现 --存储结构
weight lchild rchild
……
HTreeweight lchild rchild00
1
2
…
2n-1
一棵有 n个叶子结点的 Huffman树有 2n-1个结点
采用顺序存储结构 ——一维结构数组赫夫曼算法的实现：
1、建立具有 2n-1个单元的数组，其中 n个单元用于保存初始结点,n-1个结点用于表示内部结点。
2、执行 n-1次循环，每次产生一个内部结点。权值最小的两个结点为其左右儿子。
3、计算每个字符的赫夫曼编码 。
在远程通讯中，要将待传字符转换成由二进制组成的字符串：
设要传送的字符为,ABACCDA
若编码为,A—00
B—01
C—10
D---11
若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码,则转换的二进制字符串便可能减少。
00010010101100
4、哈夫曼树的应用 (哈夫曼编码 )
设要传送的字符为,ABACCDA
若编码为,A—0
B—00
C—1
D---01
关键,要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀。这种编码称作 前缀编码 。
ABACCDA
000011010
但,0000
AAAA ABA BB 重码前缀编码 指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。
利用赫夫曼树可以构造一种 不等长 的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传字符编码（电文）的总长度最短。
设要传送的字符为,ABACCDA
若编码为,A—0
B—110
C—10
D---111
0110010101110A
C
B D
0
0
0
1
1
1
采用二叉树设计二进制前缀编码规定：
左分支用,0”表示；
右分支用,1”表示译码过程,分解接收字符串：遇,0”向左，遇,1”向右；
一旦到达叶子结点，则译出一个字符，反复由根出发，
直到译码完成。
0110010101110
A
C
B D
0
0
0
1
1
1
ABACCDA
求 Huffman编码：由叶子 → 根，若：
（ 1）从左分支下去，则分支为,0”；
（ 2）从右分支下去，则分支为,1”。
例：已知某系统在通讯时，只出现 C,A,S,T,B五种字符，
它们出现的频率依次为 2,4,2,3,3，试设计 Huffman编码。
W(权 )={2,4,2,3,3}，叶子结点个数 n=5
14
8
4
6
4
2 2
0
0
0
1
1
13 3
0 1
构造的
Huffman树
T B A
C S
出现频率越大的字符，其 Huffman编码越短。
由 Huffman树得 Huffman编码为：
T B A C S
00 01 10 110 111
Huffman编码,数据通信用的二进制编码思想,根据字符出现频率编码，使电文总长最短编码,根据字符出现频率构造 Huffman树，然后将树中结点引向其左孩子的分支标,0”，引向其右孩子的分支标,1”；每个字符的编码即为从根到每个叶子的路径上得到的 0,1序列例 要传输的字符集 D={C,A,S,T,; }
字符出现频率 w={2,4,2,3,3}
C S
33
6
4
2 2
4
8
14
T ; A
0
0
1
1 0 1
10
T,00;,01
A,10
C,110
S,111
4,Huffman树的应用
译码,从 Huffman树根开始，从待译码电文中逐位取码。若编码是,0”，则向左走；若编码是,1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束例 电文是 {CAS;CAT;SAT;AT}
其编码,11010111011101000011111000011000”
电文为,1101000”
译文只能是,CAT”
C S
33
6
4
2 2
4
8
14
T ; A
0
0
1
1 0 1
10
T,00;,01
A,10
C,110
S,111
4,Huffman树的应用例,假设用于通信的电文仅由 8个字母
{ a,b,c,d,e,f,g,h } 构成，它们在电文中出现的概率分别为
{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，
试为这 8个字母设计哈夫曼 编码。 如果用 0～ 7的二进制编码方案又如何？
霍夫曼编码的基本思想,概率大的字符用短码，概率小的用长码。 由于 霍夫曼树的 WPL最小,说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。
解,先将概率放大 100倍，以方便构造哈夫曼树。
权值集合 w={7,19,2,6,32,3,21,10}，
按哈夫曼树构造规则（合并、删除、替换），
可得到哈夫曼树。
w4={19,21,28,32}
为清晰起见，重新排序为,
w={2,3,6,7,10,19,21,32}
2 3
56
w1={5,6,7,10,19,21,32}
w2={7,10,11,19,21,32}
w3={11,17,19,21,32}
11
107
17
282119
40
w5={28,32,40}
32
60
w6={40,60}
w7={100}
100
b
c
a d
eg
f
h哈夫曼树
× ×
× ×
× ×
× ×
× ×
× ×
× ×
对应的哈夫曼编码（左 0右 1）：
2 3
56
11
107
32
17
282119
40 60
100
b
c
a d
eg
f
h
0
0
0
0
0
1
11
1
1
1
10
0
符 编码 频率
a 0.07
b 0.19
c 0.02
d 0.06
e 0.32
f 0.03
g 0.21
h 0.10
符 编码 频率
a 0.07
b 0.19
c 0.02
d 0.06
e 0.32
f 0.03
g 0.21
h 0.10
Huffman码的 WPL＝ 2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03)
=1.44+0.92+0.25=2.61
WPL＝ 3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3
1100
00
11110
1110
10
11111
01
1101
000
001
010
011
100
101
110
111
二进制码例,假设用于通信的电文仅由 8个字母 a,b,c,d,e,f,g,h构成，
它们在电文中出现的概率分别为 0.05,0.29,0.07,
0.08,0.14,0.23,0.03,0.11，试为这 8个字母设计哈夫曼 编码。 如果用 0～ 7的二进制编码方案又如何？
解,先将概率放大 100倍，以方便构造哈夫曼树。
权值集合 w={5,29,7,8,14,23,3,11},n=8,则 m=5
typedef struct {
int weight;
int lchild,rchild;
} HTNode
typedef struct {
HTNode *HTree;
int root;
} HuffmanTree;
weight lchild rchild
……
HTreeweight lchild rchild0
1
2
…
2n-1
一棵有 n个叶子结点的 Huffman树有 2n-1个结点采用顺序存储结构 ——一维结构数组
if (n<=1) return;
void Create(HuffmanTree &HT,int *w,int n) {
typedef struct {
int weight;
int lchild,rchild;
} HTNode
typedef struct {
HTNode *HTree;
int root;
} HuffmanTree;
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
HT weight lchild rchild
5 -1 -1
29 -1 -1
7 -1 -1
8 -1 -1
14 -1 -1
23 -1 -1
3 -1 -1
11 -1 -1
8 6 0
15 2 3
19 8 7
29 4 9
42 10 5
58 11 1
100 12 13
0 1 2 3 4 5 6 7
5
15
29
8
19
42 58
100
29
b
7
c
5
a
8
d
14
e
3
g
23
f
11
h0
0
0
0
0
1
1 1
11
1 10
0
wN=8anT ee
weight lchild rchild
HTNode
HT int 29 7 8 14 23 3 11
m=15m = 2 * n - 1;
HT.HTree = new HTNode[m];
for ( p=HT.Tree,i=1; i<=n; ++i,++p,++w)
*p = { *w,-1,-1 };
for ( ; i<=m; ++i,++p ) *p ={ 0,-1,-1 };
0 -1 -1
0 -1 -1
0 -1 -1
0 -1 -1
0 -1 -1
0 -1 -1
0 -1 -1
for (i=n;i<m;++i) {
Select(HT.Htree,i-1,s1,s2);
HT.Htree [i].lchild = s1; HT.Htree[i].rchild = s2;
HT.Htree[i].weight = HT.Htree[s1].weight +HT.Htree[s2].weight;
}
8 6 0
HT.root = m-1;
}
P = HC;
InitStack(S);
Codeing(HT,HT.root,S);
}
if ( T ) {
if ( ( T.Tree[i].lchild==-1 ) && (T.Tree[i].rchild==-1) ) {
*HC[i] = new char[StackLength(S)];
StackTraverse(S);
}
0 0 1
0 1
0 0 0 0
1 1
1 0 1 0
0 0 0 1
1 0 1 1
1 0 0
0
1
2
3
4
5
6
7
HC
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
HT weight lchild rchild
5 -1 -1
29 -1 -1
7 -1 -1
8 -1 -1
14 -1 -1
23 -1 -1
3 -1 -1
11 -1 -1
8 6 0
15 2 3
19 8 7
29 4 9
42 10 5
58 11 1
100 12 13
S
void HuffmanCoding( HuffmanTree HT,HuffmanCode &HC,int n )
{
Stack S;
HC = new (char *)[n];
i (,.r t,);
i Coding( HuffmanTree T,int i,Stack &S )
{
Push( S,‘0’ );
Coding(T,T.Tree[i].lchild,S);
Pop( S,e );
Push( S,‘1’ );
Coding(T,T.Tree[i].rchild,S);
Pop( S,e );
}
} a
b
c
d
e
f
g
h
0001
11
1010
1011
100
01
0000
001 0
15
29
8
19
42 58
100
29
b
7
c
5
a
8
d
14 e
3
g
23
f
11
h0
0
0
0
0
1
1 1
11
1 10
0
14
0
0
01
1
1
1
0
a
b
c
d
e
f
g
h
typedef char ** HuffmanCode
void HuffmanCoding( HuffmanTree HT,HuffmanCode &HC,int n )
{
Stack S;
HC = new (char *)[n]; P = HC;
InitStack(S);
Codeing(HT,HT.root,S);
}
void Coding( HuffmanTree T,int i,Stack &S )
{
if ( T ) {
if ( ( T.Tree[i].lchild==-1 ) && (T.Tree[i].rchild==-1) ) {
*HC[i] = new char[StackLength(S)]; StackTraverse(S);
}
Push( S,‘0’ );
Coding( T,T.Tree[i].lchild,S );
Pop( S,E );
Push( S,‘1’ );
Coding( T,T.Tree[i].rchild,S );
Pop( S,e );
}
}
void Create(HuffmanTree &HT,int *w,int n) {
if (n<=1) return;
m = 2 * n - 1;
HT.HTree = new HTNode[m];
for ( p=HT.Tree,i=1; i<=n; ++i,++p,++w)
*p = { *w,-1,-1 };
for ( ; i<=m; ++i,++p ) *p ={ 0,-1,-1 };
for (i=n;i<m;++i) {
Select(HT.Htree,i-1,s,s2);
HT.Htree [i].lchild = s1; HT.Htree[i].rchild = s2;
HT.Htree[i].weight = HT.Htree[s1].weight +HT.Htree[s2].weight;
}
HT.root = m-1;
}
1,熟练掌握 二叉树的结构特性,了解相应的证明方法。
2,熟悉二叉树的各种 存储结构 的特点及适用范围。
3,遍历二叉树 是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。 层次遍历是按另一种搜索策略进行的遍历。
4,理解二叉树 线索化的实质 是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的 线索化过程 以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的 线索化过程 是 基于 对二叉树进行 遍历,而线索二叉树上的 线索又为相应的遍历提供了方便 。
5,熟悉 树的各种存储结构 及其特点，掌握 树和森林与二叉树的转换 方法。建立存储结构是进行其它操作的前提，因此读者应 掌握 1 至 2 种建立二叉树和树的存储结构的方法。
6,学会编写 实现树的各种操作 的算法。
7,了解 最优树的特性,掌握建立 最优树和哈夫曼编码 的方法,
本章总结本章小结
1、定义和性质
2、存储结构
3、遍历
4、线索化：线索树顺序结构链式结构二叉链表三叉链表先序线索树中序线索树后序线索树树二叉树森林先序遍历后序遍历遍历存储结构 遍历双亲表示孩子表示孩子兄弟先序遍历 后序遍历中序遍历后序遍历先序遍历霍夫曼树 霍夫曼编码
树型结构是一类重要的 非线性结构 。树型结构是 结点之间有分支,并且具有 层次关系的结构,它非常类似于自然界中的树。树结构在客观世界中是大量存在的。例如 家谱、
行政组织机构 都可用树形象地表示。
树结构在计算机领域中也有着广泛的应用,
例如在 编译程序 中,用树结构来表示源程序的 语法结构 ；在 数据库系统 中,可用树结构来组织信息 ；在分析算法的行为时,可 用树结构来描述其执行过程 等等。
华中师范大学魏开平王敬华沈显君
…
系统 软件 办公室应用操作系统 数据库 数据结构 离散数学
…
…
外语中文历史计科教务处科研处总务处
… …… 附中
ds.cs.ccnu.edu.cn
au ee
cn
edu
ccnu
cs
ds
buaa whu…
……
…
…
…
课前导学
6.1 二叉树
6.2 遍历二叉树和线索二叉树
6.3 树和森林
6.4 树的应用
【 学习目标 】
1,领会树和二叉树的类型定义，理解树和二叉树的结构差别。
2,熟记二叉树的主要特性，并掌握它们的证明
3,熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。
4,理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。
5,熟练掌握二叉树和树的各种存储结构及其建立的算法。
6,学会编写实现树的各种操作的算法。
7,了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。
【 重点和难点 】
重点
：
二叉树和树的遍历及其应用难点
：
编写实现二叉树和树的各种操作的递归算法知识点
–
树的类型定义
–
二叉树的类型定义
–
二叉树的存储表示
–
二叉树的遍历以及其它操作的实现
–
线索二叉树
–
树和森林的存储表示
–
树和森林的遍历以及其它操作的实现
–
最优树和赫夫曼编码
【 学习指南 】
本章是整个课程的第三个学习重点，也是整个课程中的一大 难点 。在本章的学习过程中主要应该学会 如何根据二叉树和树的结构及其操作的递归定义编写递归算法 。
本章必须完成的算法设计题为,
6.1,6.3,6.4,6.5,6.6,6.7,
6.8,6.9,6.10,6.11,6.12,6.14,
6.16,6.17,6.18,6.20,6.21,6.24,
6.25,6.26
6.1 二叉树二、二叉树的基本性质一、二叉树的定义和基本术语三、二叉树的存储结构逻辑结构物理结构一、二叉树的定义和基本术语
1、二叉树的定义
2、二叉树的基本术语
3、二叉树的应用举例
4、二叉树的基本操作
1,二叉树定义
二叉树 T是 n个结点的有限集合，其中 n≥0,当 n=0时，
为空树，否则，其中有一个结点为根结点，其余结点划分为两个互不相交的子集 TL,TR，并且 TL、
TR分别构成叫作左、右子树的二叉树。
A
C
D E
F
B
G H
I
K
J
M
L
A的 TL
B的 TL
递归定义二叉树或为空树；或是由一个根结点加上两棵分别称为 左子树 和 右子树的,互不交的 二叉树组成。
A
B
C
D
E
F
G
H K
根结点左子树右子树二叉树的五种基本形态：
N
空树 只含根结点
N N N
L R R
右子树为空树
L
左子树为空树左右子树均不为空树二叉树的注意点
二叉树每个结点的孩子都有 左右之分,每个结点都有左右两个子树。
A
CB
C
B
A
C
B
A
C
B
A
三个节点的二叉树（五棵）
① 每个结点最多只有两棵子树 (不存在度大于 2的结点 )；
②左子树和右子树次序不能颠倒 (有序树 )。
2、基本术语
1.
结点(n
od
e)——
表示树中的元素
，
包括数据项及若干指向其子树的分支
2.
结点的度(de
gre
e)——
结点拥有的子树数
3.
叶子(le
af)
——
度为
0
的结点
4.
孩子(ch
ild
)——
结点子树的根称为该结点的孩子
5.
双亲(p
are
nts
)——
孩子结点的上层结点叫该结点的双亲
6.
深度——
树中结点的最大层次数
7.
结点的层次——
从根结点算起
，
根为第一层
，
它的孩子为第二层
，……
1
2 3
11
4 5
8 9 12
6 7
10
——即根结点 (没有前驱 )
——即上层的那个结点 (直接前驱 )
——即下层结点的子树的根 (直接后继 )
——同一双亲下的同层结点（孩子之间互称兄弟）
——即双亲位于同一层的结点（但并非同一双亲）
——即从根到该结点所经分支的所有结点
——即该结点下层子树中的任一结点根双亲孩子兄弟堂兄弟祖先子孙
A
B C D
E F G H I J
K L M
结点 A的度,3
结点 B的度,2
结点 M的度,0
叶子,K,L,F,G,M,I,J
结点 A的孩子,B,C,D
结点 B的孩子,E,F
结点 I的双亲,D
结点 L的双亲,E
结点 B,C,D为兄弟结点 K,L为兄弟树的度,3
结点 A的层次,1
结点 M的层次,4
树的深度,4
结点 F,G为堂兄弟结点 A是结点 F,G的祖先
3、二叉树的应用举例男
（色盲）
女 女 男男女男
─
E T
NAI M
OGKDWRUS
H V F L P J B X C Y Z Q
──
── ─ ─
──────
国际 Morse码变色力缺陷遗传图 （隔代遗传）
InitBiTree(&T);
DestroyBiTree(&T);
CreateBiTree(&T,definition);
ClearBiTree(&T);
BiTreeEmpty(T);
BiTreeDepth(T);
Parent(T,e);
LeftChild(T,e);
RightChild(T,e);
LeftSibling(T,e);
RightSibling(T,e);
InsertChild(T,p,LR,c);
DeleteChild(T,p,LR);
PreOrderTraverse(T,Visit());
InOrderTraverse(T,Visit());
PostOrderTraverse(T,Visit());
LevelOrderTraverse(T,Visit());
二叉树的基本操作查 找 类插 入 类删 除 类二、二叉树的基本性质
1、层与结点数
2、深度与结点数
3、叶子与结点数
4、完全二叉树与深度
5、完全二叉树与结点序号
1.一棵非空二叉树的第 i 层最多有 2i–1个结点 (i?1)。
证明 (采用归纳法 )
(1).当 i=1时,结论显然正确。非空二叉树的第 1层有且仅有一个结点,即树的根结点,
(2).假设对于第 j层 (1?j?i–1)结论也正确,即第 j层最多有 2j-1个结点,
(3).有定义可知,二叉树中每个结点最多只能有两个孩子结点。若第 i–1层的每个结点都有两棵非空子树,则第 i层的结点数目达到最大,而第 i–1层最多有 2i–2个结点已由假设证明,于是,应有 2?2i–2 = 2i–1
证毕,
二叉树的性质讨论 1：第 i层的结点数至多是多少？
（利用二进制性质可轻松求出）
提问,第 i层上至少有 个结点？
2.深度为 h 的非空二叉树最多有 2h -1个结点,
证明,
由性质 1可知,若深度为 h的二叉树的每一层的结点数目都达到各自所在层的最大值,则二叉树的结点总数一定达到最大。
即有
20+21+22+…+2 i-1+ …+2 h-1 = 2h-1
证毕,
二叉树的性质讨论 2：深度为 k的二叉树，至多有多少个结点？
（利用二进制性质可轻松求出）
提问,深度为 k时至少有 个结点？
3,若非空二叉树有 n0个叶结点,有 n2个度为 2的结点,
则 n0=n2+1
证明,
设该二叉树有 n1个度为 1的结点,结点总数为 n,有
n=n0+n1+n2 --------(1)
设二叉树的分支数目为 B,有
B=n-1 --------(2)
这些分支来自度于为 1的结点与度度为 2结点,即
B=n1+2n2 --------(3)
联列关系 (1),(2)与 (3),可得到
n0=n2+1证毕,
推论,n0=n2+2n3+3n4+? +(m-1)nm +1
二叉树的性质讨论 3：二叉树的叶子数和度为 2的结点数之间有关系吗？
A
B C
GE
I
D
H
F
J
实际意义,叶子数＝ 2度结点数＋ 1
4,具有 n个结点的完全二叉树的深度 h=?log2n?+1.
证明,
二叉树的性质设 完全二叉树的深度为 k
则根据第二条性质得 2k-1≤ n < 2k
即 k-1 ≤ log2 n < k
因为 k 只能是整数，因此,k =?log2n? + 1
证毕,
对于两种特殊形式的二叉树（ 满二叉树 和 完全二叉树 ），还特别具备以下 2个性质：
5,若对具有 n个结点的完全二叉树按照层次从上到下,每层从左到右的顺序进行编号,则编号为 i 的结点具有以下性质,
(1) 当 i=1,则编号为 i的结点为二叉树的根结点 ;
若 i>1,则编号为 i 的结点的双亲结点的编号为?i/2?.
(2) 若 2i>n,则编号为 i 的结点无左子树 ;
若 2i?n,则编号为 i 的结点的左子树的根的编号为 2i.
(3) 若 2i+1>n,则编号为 i 的结点无右子树 ;
若 2i+1?n,则编号为 i 的结点的右子树的根的编号为 2i+1.
1
2 3
4 5 6 7
8 9 10
n=10
二叉树的性质两种特殊形态的二叉树若一棵二叉树中的结点,
或者为叶结点，或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层,这样的二叉树为满二叉树,
1,满二叉树若一棵二叉树中只有最下面两层的结点的度可以小于 2,
并且最下面一层的结点 (叶结点 )都依次排列在该层从左至右的位臵上。这样的二叉树为完全二叉树,
2.完全二叉树二叉树的性质解释,完全二叉树的特点就是，
只有最后一层叶子不满，且全部集中在左边。
这其实是 顺序 二叉树的含义。
在图论概念中的“完全二叉树”
是指 n1=0的情况。
为何要研究这两种特殊形式？
因为它们在顺序存储方式下可以复原 !
（特点：每层都“充满”了结点）
三、二叉树的存储结构
1、顺序存储结构
2、链式存储结构
1
2 3
4 5 6 7
8 9 10
A
B C
D E F G
H I J
BT[1:15]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F G H I J
根据完全二叉树的性质 5,对于深度为 h的完全二叉树,
将树中所有结点的数据信息按照编号的顺序依次存储到一维数组 BT[1:2h-1]中,由于编号与数组的下标一一对应,该数组就是该完全二叉树的顺序存储结构,
1）完全二叉树的顺序存储结构
1、二叉树的顺序存储结构讨论,不是完全二叉树怎么办？
答,一律转为完全二叉树 ！
方法很简单,将各层空缺处统统补上,虚结点,,其内容为空 。
A
B
^
C
^
^
^
D
^
…
E
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
.
[16]
A
B
E
C
D
缺点,① 浪费空间；②插入、删除不便
1、二叉树的顺序存储结构
1
2 3
4 5 6 7
8 9 10
A
B C
D E F G
H IJ
11 12 13
BT[1:15]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F G H J I
A
B C
D E F G
H IJ
2） 一般二叉树的顺序存储结构
1、二叉树的顺序存储结构例如
A B D C E F
0 1 2 3 4 5 6 7 8 9 10 11 12 13
A
B
C
D
E
F
1
4
0
13
2
6
#define MAX_TREE_SIZE 100
// 二叉树的最大结点数
typedef TElemType
SqBiTree[MAX_TREE_SIZE];
// 0号单元存储根结点
SqBiTree bt;
1、二叉树的顺序存储结构用二叉链表即可方便表示。
datalchild rchild
data
left_child right_child
二叉树结点数据类型定义：
typedef struct node *tree_pointer;
typedef struct Binode {
TElemType data;
struct BiNode *lchild,*rchild;
} BiTNode,*BiTree;
一般从根结点开始存储。
（相应地，访问树中结点时也只能从根开始）
注,如果需要倒查某结点的双亲，
可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。
存储结点值的数据域 data
指向右孩子结点的指针指向左孩子结点的指针
2、二叉树的链式存储结构
A
C
B
D
E
F
G
返回
lchild data rchild
2、二叉树的链式存储结构
A
B E ^
^ G ^
^ F^ D ^^ C ^
例：
A
B
E
C
D
^A
B ^
D
^C
^
^E^
2、二叉树的链式存储结构二叉树的链式存储结构 (二叉链表 )
链结点的构造为
lchild data rchild
其中,data 为数据域
lchild 与 rchild 分别为指向左、右子树的指针域,
A
B C
D E F G
IJ
A
B C
D E F G
J I
T
^
^
^ ^ ^
^ ^ ^
^ ^
2、二叉树的链式存储结构 空指针个数,2*n
0+1*n1+0*n2
=2n0+n1
=n0+n1+n0
=n0+n1+n2+1
=n+1
在 n个结点的二叉链表中，有 n+1个空指针域
6.2 二叉树的遍历二、遍历算法一、二叉树的遍历四、线索二叉树三、遍历应用举例一,二叉树的遍历常用的二叉树的遍历方法,
1.前序遍历
2.中序遍历
3.后序遍历
4.按层次遍历右子树左子树根按照一定的顺序 ( 原则 )对叉树中每一个结点都访问一次 (仅访问一次 ),得到一个由该二叉树的所有结点组成的序列,
这一过程称为二叉树的遍历,
A
B
C
D
E
F
G
H K
例如,先序序列：
中序序列：
后序序列：
A B C D E F G H K
B D C A E H G K F
D C B H K G F E A
1、先序遍历
A
B C
D E F G
IJ
前序序列,
A B D E J C F I
原则,
若被遍历的二叉树非空,则
1,访问根结点 ;
2,以先序遍历原则 遍历根结点的左子树 ;
3,以先序遍历原则 遍历根结点的右子树,
G
-
*
A B
C
－
* C
A B
-
*
A B
C
先 序遍历 - * A B C1、前序遍历中序序列,
D B J E A F I C
原则,
若被遍历的二叉树非空,则
1,以中序遍历原则 遍历根结点的左子树 ;
2,访问根结点 ;
3,以中序遍历原则 遍历根结点的右子树,
G
2、中序遍历
A
B C
D E F G
IJ
-
*
A B
C
－
* C
A B
-
*
A B
C
中序遍历 A * B - C2、中序遍历后序序列,
D J E B I F G C
原则,
若被遍历的二叉树非空,则
1,以后序遍历原则 遍历根结点的左子树 ;
2,以后序遍历原则 遍历根结点的右子树,
3,访问根结点 ;
A
A
B C
D E F G
IJ
3、后序遍历
-
*
A B
C
－
* C
A B
-
*
A B
C
后序遍历 A B * C -3、后序遍历
-
+ /
a *
b -
e f
c d
先序遍历：
中序遍历：
后序遍历：
层次遍历：
- + a * b - c d / e f
-+a *b -c d /e f
- + a * b- c d/ e f
-+a *b -c d /e f
例：用二叉树表示算术表达式
+
*
A
*
/
E
D
C
B
先序遍历
+ * * / A B C D E
前缀表示中序遍历
A / B * C * D + E
中缀表示后序遍历
A B / C * D * E +
后缀表示层序遍历
+ * E * D / C A B
例：用二叉树表示算术表达式三、遍历算法
1、先序遍历
2、中序遍历
3、后序遍历
4、无递归 中序遍历
void Preorder( BiTree T,void(*visit)( BiTree) )
{
if (T) {
visit(T);
Preorder( T->lchild,visit );
Preorder( T->rchild,visit );
}
前序遍历
void inorder( BiTree T,void(*visit)( BiTree) )
{
if (T) {
inorder( T->lchild,visit );
visit(T);
inorder( T->rchild,visit );
}
}
中序遍历按层次遍历按层次遍历序列,
A,B,C,D,E,F,G,J,I
void Postorder( BiTree T,void(*visit)( BiTree) )
{
if (T) {
Postorder( T->lchild,visit );
Postorder( T->rchild,visit );
visit(T);
}
}
后序遍历
A
B C
D E F G
IJ
void pre( BiTree T,void(*visit)( BiTree ) )
{
if (T) {
visit(T);
pre( T->lchild,visit );
pre( T->rchild,visit );
}
}
主程序
Pre( T )
返回返回
pre(T R);
返回返回
pre(T R);
A
CB
D
T B
printf(B);
pre(T L);
T A
printf(A);
pre(T L);
T D
printf(D);
pre(T L);
T C
printf(C);
pre(T L);
返回
T
左是空返回
pre(T R);
T
左是空返回
T
右是空返回
T
左是空返回
T
右是空返回
pre(T R);
先序序列,A B D C
遍历算法的执行过程 ---例题说明
模拟算法对如图所示二叉树的中序遍历的执行过程。
A
DC
B
FE
G
H
inorder(^)
inorder(A)
inorder(B) A inorder(G)
inorder(C) B inorder(D) inorder(H) G norder(^)
inorder(^) C inorder(^)
inorder(E) inorder(F)D
inorder(^) H
inorder(^) E inorder(^) inorder(^) F inorder(^)
输出序列
CBEDFAHG
4、非递归算法
A
B
C D
E F
G
p
i
P->A
(1)
A
B
C D
E F
G
p
i
P->A
P->B
(2)
A
B
C D
E F
G
p i
P->A
P->B
P->C
(3)
p=NULL
A
B
C D
E F
G
i
P->A
P->B
访问,C(4)
p A
B
C D
E F
G
i
P->A
访问,C B(5)
A
B
C D
E F
G
i
P->A
P->D
访问,C B
p
(6)
A
B
C D
E F
G
i
P->A
P->D
P->E
访问,C B
p
(7)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E
p (8)
A
B
C D
E F
G
i
P->A
P->D
P->G
访问,C B E
P=NULL
(9)
A
B
C D
E F
G
i
P->A
访问,C B E G D
p
(11)
A
B
C D
E F
G
i
P->A
P->F
访问,C B E G D
p
(12)
A
B
C D
E F
G
i
P->A
P->D
访问,C B E G
p
(10)
A
B
C D
E F
G
i
P->A
访问,C B E G D F
p=NULL
(13)
A
B
C D
E F
G
i
访问,C B E G D F A
p
(14)
i
访问,C B E G D F A
p=NULL
(15)
typedef enum { Travel,Visit } TaskType;
// Travel == 1:遍历,// Visit == 0:访问
typedef struct {
BiTree ptr; // 指向根结点的指针
TaskType task; // 任务性质
} ElemType;
,遍历左子树”,遍历右子树”,访问根结点”
4、中序遍历算法的非递归描述在写算法之前首先需定义栈的元素类型。
void InOrder_iter( BiTree BT )
{
// 利用栈实现中序遍历二叉树,T为指向二叉树的根结点的头指针
InitStack(S);
e.ptr=BT; e.task=Travel;
if (T) Push(S,e); // 布置初始任务
while(!StackEmpty(S)) {
Pop(S,e); // 每次处理一项任务
if (e.task==Visit) visit(e.ptr); // 处理访问任务
else if ( !e.ptr ) { // 处理非空树的遍历任务
p=e.ptr;
e.ptr=p->rchild; Push(S,e); // 最不迫切任务进栈
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
} //if
} //while
} //InOrder_iter
A T
A Te
A
B
D
C
E ^
^
^
^
^ ^
P
A VC TB T
e.ptr=BT; e.task=Travel; if(BT) Push(S,e);
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
B Te
A VC TB T A VC T
P D T
A VC T
B V^ T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
^ Te
P
D TA V
C T
B V^ T D T
A VC T
B V
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
D TA V
C T
B V D T
A VC T
e B V
输出 B
if(e.task==Visit) visit(e.ptr);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^P
D TA V
C T
e D T
A VC T
输出 B
A VC T^ T
D VE T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
e E T
输出 B
A VC T^ T
D VE T
A VC T^ T
D V
A VC T^ T
D V^ T
E V^ T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
e ^ T
输出 B
A VC T^ T
D V^ T
E V^ T
A VC T^ T
D V^ T
E V
A VC T^ T
D V^ T
e E V
输出 E
if(e.task==Visit) visit(e.ptr);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
e ^ T
A VC T^ T
D V^ T
A VC T^ T
D V
A VC T^ T
e D V
输出 D输出 BE
if(e.task==Visit) visit(e.ptr);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^P
e ^ T
A VC T^ T C TA VC T
e A V
输出 A输出 BED
if(e.task==Visit) visit(e.ptr);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
e C T
C T
输出 BEDA
^ TC V
^ T
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
e ^ T
输出 BEDA
^ TC V
^ T
^ TC V
C Ve
^ T
输出 C
if(e.task==Visit) visit(e.ptr);
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
A
B
D
C
E ^
^
^
^
^ ^
P
e ^ T
输出 BEDAC
^ T
OVER
void InOrder_iter( BiTree BT )
{ InitStack(S);
e.ptr=BT; e.task=Travel; if (T) Push(S,e);
while(!StackEmpty(S)) {
Pop(S,e);
if (e.task==Visit) visit(e.ptr);
else if ( !e.ptr ) {
p=e.ptr;
e.ptr=p->rchild; Push(S,e);
e.ptr=p; e.task=Visit; Push(S,e);
e.ptr=p->lchild; e.task=Travel; Push(S,e);
}
}
}
四,遍历算法的应用举例
2、求二叉树的深度 (后序遍历 )
1、建立二叉树的存储结构
4、计算表达式的值
3、复制二叉树 (后序遍历 )
1、建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立算法
(1) 以字符串的形式,根 -左子树 -右子树,定义一棵二叉树例如,
A(B(,C(,)),D(,))
A
B
C
D
以下列字符串表示以空白字符,”表示空树只含一个根结点的二叉树 A
以字符串,A,表示按先序遍历序列建立二叉树的二叉链表,
已知先序序列为：
A B C D E? G F
A
B
C D
E F
G
A ^
B
^ C ^ D
^ E ^ F ^
^ G ^
Status CreateBiTree(BiTree &T)
{
scanf(&ch);
if (ch==' ') T=NULL;
else
{
if (!(T = new BiTNode)) exit(OVERFLOW);
T->data = ch; // 生成根结点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return OK;
} // CreateBiTree A
T
B
C
D ^
^ ^
^ ^
A B C D
void CreatebiTree(BiTree &T){
// 在先序遍历二叉树过程中输入结点字符，建立二叉链表存储结 //构，指针 T指向所建二叉树的根结点
cin >> ch ；
if (ch=='#') T=NULL; // 建空树
else {
T = new BiTNode ; // "访问 "操作为生成根结点
T->data = ch;
CreateBiTree(T->lchild); // 递归建 (遍历 )左子树
CreateBiTree(T->rchild); // 递归建 (遍历 )右子树
}//else
}//CreateBiTree
2、求二叉树的深度 (后序遍历 )
算法基本思想,首先分析二叉树的深度和它的左、右子树深度之间的关系。
从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加 1。由此，需先分别求得左、右子树的深度，算法中访问结点的操作为,求得左、右子树深度的最大值，然后加 1 。
int Depth (BiTree T ) { // 返回二叉树的深度
if (!T) depthval = 0;
else {
depthLeft = Depth( T->lchild );
depthRight= Depth( T->rchild );
depthval = 1+(depthLeft>depthRight?depthLeft:depthRight);
}
return depthval;
}
void Depth(BiTree T,int level,int &dval) {
if ( T ) {
if (level>dval) dval = level;
Depth( T->lchild,level+1,dval );
Depth( T->rchild,level+1,dval );
}
}
//调用之前 level 的初值为 1,dval 的初值为 0.
void BiTreeDepth(BiTree T,int h,int &depth){
// h为 T指向的结点所在层次,T指向二叉树的根，则 h的初
//值为 1,depth为当前求得的最大层次,其初值为 0
if (T){
if (h>depth) depth=h;
BiTreeDepth(T->lchild,h+1,depth);
BiTreeDepth(T->rchild,h+1,depth);
}
}//BiTreeDepth
主函数调用：
d=0
BiTreeDepth(r,1,d)
int BiTreeDepth(BiTree T) {
// 后序遍历求 T所指二叉树的深度
if (!T) return 0;
else {
hL=BiTreeDepth(T->lchild);
hR=BiTreeDepth(T->rchild);
if (hL>=hR) return hL+1;
else return hR+1;
}
}//BiTreeDepth
A
B
C
D
E
F
G
H K
A例如，下列二叉树的复制过程如下：
newT
^ B E ^
C ^
^ D ^
F ^
G
^ H ^ ^ K ^
3、复制二叉树 (后序遍历 )
BiTNode *GetTreeNode(TElemType item,BiTNode *lptr,BiTNode *rptr )
{
if (!(T = new BiTNode)) exit(1);
T-> data = item; T-> lchild = lptr; T-> rchild = rptr;
return T;
}
生成一个二叉树的结点 (其数据域为 item,左指针域为 lptr,右指针域为 rptr)
BiTNode *CopyTree(BiTNode *T) {
if (!T) return NULL;
if (T->lchild ) newlptr = CopyTree(T->lchild); //复制左子树
else newlptr = NULL;
if (T->rchild ) newrptr = CopyTree(T->rchild); //复制右子树
else newrptr = NULL;
newT = GetTreeNode(T->data,newlptr,newrptr);
return newT;
} // CopyTree
4、计算表达式的值 (a+b*(c-d))-e/f
－
＋
*a
/
b -
dc
fe
-2
-1
-30
-4
1 -2
32
54
3.1 4.2 2.4 3.8 7.2 2.4abcd-*+ef/- （后缀表达式） opnd
0 1 2 3 4 5
数据结构的表示
a+b
(a+b)× c – d/ea+b× c
表达式的二叉树的表示,
a b
+
a
b c
×
+
a b
c
×
+
(a+b)× c
a b
c d e
-
×
+
/
特点,
操作数 为叶子结点运算符 为分支结点例右图所示的二叉树表达式
(a+b*(c-d))-e/f
若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：
-+a*b-cd/ef （前缀表达式）
按中序遍历,其中序序列为：
a+b*c-d-e/f （中缀表达式）
按后序遍历,其后序序列为：
abcd-*+ef/- （后缀表达式）
－
＋
*a
/
b -
dc
fe
double value(BiTree T,float opnd[]){
// 对以 T为根指针的二叉树表示的算术表达式求值，
// 操作数的数值存放在一维数组 opnd中
if (!T) return 0; // 空树的值为 0
if (T->data>=0) return opnd[T->data];
Lv = value(T->lchild,opnd); // 遍历左子树求第一操作数
Rv = value(T->rchild,opnd); // 遍历右子树求第二操作数
switch (T->data){
case PLUS,v = Lv + Rv;
case MINUS,v = Lv - Rv;
case ASTERISK,v = LV * Rv;
case SLANT,v = Lv / Rv;
default,ERROR("不合法的运算符 ");
} //switch
return v;
}//value
习题讨论：
1,求二叉树深度，或从 x结点开始的子树深度。
算法思路,只查各结点后继链表指针，若左 (右 )孩子的左 (右 )指针非空，则层次数加 1；否则函数返回。
技巧,递归时应当 从叶子开始向上计数，层深者保留。 否则不易确定层数。
2,按层次输出二叉树中所有结点。
算法思路,既然要求从上到下，从左到右，则 利用队列 存放各子树结点的指针是个好办法，而不必拘泥于递归算法。
技巧,当根结点入队后,令其左,右孩子结点入队,而左孩子出队时又令它的左右孩子结点入队,…… 由此便可产生按层次输出的效果 。
3 中序遍历的非递归 (迭代 )算法算法思路,若不用递归，则要实现二叉树遍历的,嵌套,规则，必用堆栈。可直接用 while语句和 push/pop操作。
4.判别给定二叉树是否为完全二叉树（即顺序二叉树）。
算法思路,完全二叉树的特点是：没有左子树空而右子树单独存在的情况 (前 k-1
层都是满的，且第 k层左边也满） 。
技巧,按层序遍历方式,先把所有结点 （ 不管当前结点是否有左右孩子 ） 都入队列,若为完全二叉树,则层序遍历时得到的肯定是一个连续的不包含空指针的序列,
如果序列中出现了空指针,则说明不是完全二叉树 。
三,线索二叉树
1、何谓线索二叉树？
2、线索链表的遍历算法
3、如何建立线索链表？
1）什么是线索二叉树
2）线索二叉树的构造利用二叉链表中空的指针域指出结点在遍历序列中的直接前驱和直接后继 ;这些指向前驱和后继的指针称为 线索,加了线索的二叉树称为 线索二叉树,
利用链结点的 空 的 左指针域 存放该结点的 直接前驱的地址,空 的 右指针域 存放该结点 直接后继 的地址 ;
非空指针域仍然存放结点的左孩子或右孩子的地址,
1、何谓线索二叉树？
线索二叉树 （ Threaded Binary Tree） 的理解普通二叉树只能找到结点的左右孩子信息,而该结点的直接前驱和直接后继只能在遍历过程中获得。
若将 遍历后对应的有关前驱和后继预存 起来，则从 第一个结点 开始就能很快“顺藤摸瓜”而遍历整个树了。
两种解决方法增加两个域,fwd和 bwd；
利用空链域（ n+1个空链域）
存放前驱指针 存放后继指针如何预存这类信息？
例如中序遍历结果,B D C E A F H G，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继！
可能是根、或最左（右）叶子指向该线性序列中的,前驱,和,后继,的指针，称作,线索,
与其相应的二叉树，
称作,线索二叉树,
包含,线索,的存储结构，称作,线索链表,
A B C D E F G H K
^ D ^
C ^
^ B E ^
规 定,1）若结点有左子树，则 lchild指向其左孩子；
否则,lchild指向其直接前驱 (即线索 )；
2）若结点有右子树，则 rchild指向其右孩子；
否则,rchild指向其直接后继 (即线索 ) 。
为了避免混淆，增加两个标志域，如下图所示：
lchild LTag data RTag rchild
约定,当 Tag域为 0时,表示正常情况 ;
当 Tag域为 1时,表示线索情况,
注,在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为 0时，则需要通过一定运算才能找到它的后继。
线索链表,用前页结点结构所构成的二叉链表线索,指向结点前驱和后继的指针线索二叉树,加上线索的二叉树（图形式样）
线索化,对二叉树以某种次序遍历使其变为线索二叉树的过程
data A G E I D J H C F B
ltag 0 0 1 1 1 1 0 1 0 1
rtag 0 0 0 1 0 1 0 1 1 1
A
G
E
I
D
J
H
C F
B
例,带了两个标志的某先序遍历结果如表所示，请画出对应二叉树。
A
B C
GE
I
D
H
F
root
悬空？
悬空？
解,该二叉树中序遍历结果为,H,D,I,B,E,A,F,C,G
所以添加线索应当按如下路径进行：
例,画出以下二叉树对应的中序线索二叉树。
为避免悬空态，应增设一个头结点
typedef struct BiThrNod {
TElemType data;
struct BiThrNode *lchild,*rchild; // 左右指针
PointerThr LTag,RTag; // 左右标志
} BiThrNode,*BiThrTree;
3）线索链表的类型描述
typedef enum { Link,Thread } PointerThr;
// Link==0:指针,Thread==1:线索对应的中序线索二叉树存储结构如图所示：
0 0A
0 0C0 0B
1 1E 1 1F 1 1G0 0D
1 1I1 1H
注：此图中序遍历结果为,H,D,I,B,E,A,F,C,G
0 --root 0
※ 中序遍历的第一个结点?
※ 在中序线索化链表中结点的后继?
左子树上处于“最左下”（没有左子树）
的结点若 无右子树,则为 后继线索所指结点否则为 对其右子树进行中序遍历时访问的第一个结点
2、线索二叉树的遍历
–按中序线索化二叉树
–遍历中序线索二叉树在中序线索二叉树中找结点后继的方法：
（ 1）若 rt=1,则 rc域直接指向其后继
（ 2）若 rt=0,则结点的后继应是其右子树的左链尾
（ lt=1)的结点
A
B
C
D
E
0 A 0
1 B 0 0 D 1
1 C 1 1 E 1
T
中序序列,BCAED
带头结点的中序线索二叉树
0 1
void InOrderTraverse_Thr(BiThrTree T,
void (*Visit)(TElemType e)) {
p = T->lchild; // p指向根结点
while (p != T) { // 空树或遍历结束时,p==T
while (p->LTag==Link) p = p->lchild; // 第 一个结点
while (p->RTag==Thread && p->rchild!=T) {
p = p->rchild; Visit(p->data); // 访问后继结点
}
p = p->rchild; // p进至其右子树根
}
} // InOrderTraverse_Thr
3、线索二叉树的生成线索化过程就是 在遍历过程中修改空指针 的过程：
将空的 lchild改为结点的直接前驱；
将空的 rchild改为结点的直接后继。
非空指针呢？仍然指向孩子结点（称为,正常情况,）
目的,在 依某种顺序遍历 二叉树时修改空指针，添加前驱或后继。
注解,为方便添加结点的前驱或后继，需要设臵两个指针：
p指针 → 当前结点之指针； pre指针 → 前驱结点之指针。
技巧,当结点 p的左 /右域为空 时，只改写它的左域 (装入前驱 pre),
而其右域（后继）留给下一结点来填写。
或者说，当前结点的指针 p应当送到前驱结点的空右域中。
若 p->lchild＝ NULL,则 {p->Ltag=1;p->lchild＝ pre;}
//p的前驱结点指针 pre存入左空域若 pre->rchild＝ NULL,则 {pre->Rtag＝ 1;pre->rchild=p;}
//p存入其前驱结点 pre的右空域线索二叉树的生成算法在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的,前驱,和,后继,信息。遍历过程中，附设指针 pre,
并始终保持指针 pre指向当前访问的、指针 p所指结点的前驱。
void InOrderThreading(BiThrTree &H,BiThrTree T)
{ H = new BiThrNode;
H->lchild = T; H->rchild = NULL;
if ( !T ) { H->pred = H; H->succ = H; }
else {
pre = H;
InThreading( T,pre );
pre->succ = H; H->pred = pre;
}
} void InThreading(BiThrTree p,BiThrTree &pre ){
if (p) {
InThreading(p->lchild);
pre->succ = p; p->pred = pre;
pre = p; // 保持 pre 指向 p 的前驱
InThreading(p->rchild);
}
}1 1
p
0 1
pre
6.3 树和森林一、树和森林的定义二,树和森林的存储结构三,树和森林的的遍历一、树和森林 的定义
1、树的定义
2,森林的定义
3、对 树和森林的操作
1、树的基本概念树 是由 n?0 个结点组成的有穷集合 (不妨用 D表示 )以及结点之间关系组成的集合构成的结构。
当 n=0 时，称该树为 空树 ；
在任何一棵非空的树中，有一个特殊的结点 t?D，
称之为该树的根结点；其余结点 D–{t}被分割成 m>0
个不相交的子集 D1,D2,…,D m,其中每一个子集 Di又为一棵树，分别称之为 t 的 子树 。
递归定义一,树的定义注 1,过去许多书籍中都定义树为 n≥1,曾经有,空树不是树,的说法，但现在树的定义已修改。
注 2,树的定义具有 递归性,即树中还有树。
JIHGFE
A
C XB
A的第 1棵子树 A的第 3棵子树
A的第 2棵子树二,树 (逻辑上 )的特点
1,有且仅有一个结点没有前驱结点,该结点为树的根结点。
2,除了根结点外,每个结点有且仅有一个直接前驱结点。
3,包括根结点在内，每个结点可以有多个后继结点。
A
只有根结点的树
A
B C D
E F G H I J
K L M
有子树的树 根子树任何一棵非空树是一个二元组
Tree = （ root,F）
其中,root 被称为根结点,
F 被称为子树森林
2、森林是 m（ m≥ 0）棵互不相交的树的集合
A
root
B
E F
K L
C
G
D
H I J
M
F
3、树 的表示法
图形表示法
嵌套集合表示法
广义表表示法
目录表示法
左孩子－右兄弟表示法
1） 图形表示法教师 学生 其他人员
2002级 2003级 2004级 2005级
……
华中师范大学物理计算机系 数学 ……
叶子根子树
2）广义表表示法
( A ( B ( E ( K,L ),F ),C ( G ),D ( H ( M ),I,J ) )
根作为 由子树森林组成的 表的名字写在表的左边
data link 1 link 2,.,link n
麻烦问题：应当开设多少个链域?
A( )
T1 T3T2树根
B(E,F(K,L)),C(G),D(H,I,J(M))
A
B C D
E F G H I J
MK L
例如,
3）左孩子－右兄弟表示法
A
B C D
E F G H I J
K L M
( A ( B ( E ( K,L ),F ),C ( G ),D ( H ( M ),I,J ) ) )
数据左孩子 右兄弟
Root(T) // 求树的根结点查找类：
Value(T,cur_e) // 求当前结点的元素值
Parent(T,cur_e) // 求当前结点的双亲结点
LeftChild(T,cur_e) // 求当前结点的最左孩子
RightSibling(T,cur_e) // 求当前结点的右兄弟
TreeEmpty(T) // 判定树是否为空树
TreeDepth(T) // 求树的深度
TraverseTree( T,Visit() ) // 遍历
4、树的操作
InitTree(&T) // 初始化臵空树插入类：
CreateTree(&T,definition) // 按定义构造树
Assign(T,cur_e,value) // 给当前结点赋值
InsertChild(&T,&p,i,c) // 将以 c为根的树插入为结点 p的第 i棵子树
ClearTree(&T) // 将树清空删除类：
DestroyTree(&T) // 销毁树的结构
DeleteChild(&T,&p,i) // 删除结点 p的第 i棵子树要明确：
1,普通树（即多叉树）若不转化为二叉树，则运算很难实现。
2,二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够,遍历,的基础上！
（ 遍历,指每个结点都被访问且仅访问一次，不遗漏不重复 )。
5、若干术语
——即上层的那个结点 (直接前驱 )
——即下层结点的子树的根 (直接后继 )
——同一双亲下的同层结点（孩子之间互称兄弟）
——即双亲位于同一层的结点（但并非同一双亲）
——即从根到该结点所经分支的所有结点
——即该结点下层子树中的任一结点
A
B C
GE I
D
HF J
MLK
根叶子森林有序树无序树
——即根结点 (没有前驱 )
——即终端结点 (没有后继 )
——指 m棵不相交的树的集合 (例如删除 A后的子树个数 )
双亲孩子兄弟堂兄弟祖先子孙
——结点各子树从左至右有序，不能互换（左为第一）
——结点各子树可互换位臵。
5、若干术语（续）
——即树的数据元素
——结点挂接的子树数
（有几个直接后继就是几度
，亦称“次数”）
结点结点的度结点的层次终端结点分支结点树的度树的深度
(或高度 )
A
B C
GE I
D
HF J
MLK
——从根到该结点的层数（根结点算第一层）
——即度为 0的结点，即叶子
——即度不为 0的结点（也称为内部结点）
——所有结点度中的最大值 （ Max{各结点的度 }）
——指所有结点中最大的层数 （ Max{各结点的层次 }）
问,右上图中的结点数＝ ；树的度＝ ；树的深度＝13 3 4
A
B C D
E F G H I J
K L M
结点 A的度,3
结点 B的度,2
结点 M的度,0
叶子,K,L,F,G,M,I,J
结点 A的孩子,B,C,D
结点 B的孩子,E,F
结点 I的双亲,D
结点 L的双亲,E
结点 B,C,D为兄弟结点 K,L为兄弟树的度,3
结点 A的层次,1
结点 M的层次,4
树的深度,4
结点 F,G为堂兄弟结点 A是结点 F,G的祖先线性结构 树型结构第一个数据元素
(无前驱 )
根结点 (无前驱 )
最后一个数据元素
(无后继 )
多个叶子结点 (无后继 )
其它数据元素
(一个前驱、一个后继 )
其它数据元素
(一个前驱、多个后继 )
树的逻辑结构
(特点 )：一对多 (1:n)，有多个直接后继 (如家谱树、目录树等等 )，但只有一个根结点，
且 子树之间互不相交 。
树的存储结构讨论 1,树是非线性结构，该怎样存储？
——仍然有顺序存储、链式存储等方式。
讨论 3,树的 链式存储 方案应该怎样制定？
可规定为,从上至下,从左至右 将树的结点依次存入内存 。
重大缺陷,复原困难 (不能唯一复原就没有实用价值 )。
讨论 2,树的 顺序存储 方案应该怎样制定？
可用多重链表,一个前趋指针,n个后继指针。
细节问题,树中结点的结构类型样式该如何设计？
即应该设计成,等长,还是,不等长,？
缺点,等长结构太浪费（每个结点的度不一定相同）；
不等长结构太复杂（要定义好多种结构类型）。
解决思路,先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。
二叉树二、树和森林 的存储结构
1、双亲表示法
2、孩子连表示法
3、二叉链（孩子兄弟）表示法
4、二叉树、树和森林的转换二、树和森林的存储方式树有三种常用存储方式：
①双亲表示法
②孩子表示法
③孩子兄弟表示法
1、用双亲表示法来存储思路,用一组 连续空间 来存储树的结点，同时在每个结点中 附设一个指示器,指示其双亲结点在链表中的位臵。
parentsdata
结点结构
data parents
1
树结构
2
3
n
1、双亲表示法
A
B C D
E F
G
0 A -1
1 B 0
2 C 0
3 D 0
4 E 2
5 F 2
6 G 5
r=0
n=6
data parent
缺点：求结点的孩子时需要遍历整个结构。
C语言的类型描述
#define MAX_TREE_SIZE 100
结点结构,
typedef struct PTNode {
Elem data;
int parent; // 双亲位臵域
} PTNode;
树结构,
typedef struct {
PTNode nodes [MAX_TREE_SIZE];
int r,n; // 根结点的位置和结点个数
} PTree;
data parent
思路,将每个结点的 孩子 排列起来，形成一个 带表头
（装父结点） 的线性表 （ n个结点要设立 n个链表）；
再将 n个表头用数组存放 起来，这样就形成一个 混合结构。
例如,
a
b
e
c
d
f hg
d e
f g h
g
f
e
d
c
b
a
h
1
2
3
4
5
6
7
8
b c
2、孩子链表表示法
C语言的类型描述,
孩子结点结构
typedef struct CTNode {
int child;
struct CTNode *next;
} *ChildPtr;
双亲结点结构
typedef struct {
Elem data;
ChildPtr firstchild; // 孩子链的头指针
} CTBox;
树结构 typedef struct {
CTBox nodes[MAX_TREE_SIZE];
int n,r; // 结点数和根结点的位置
} CTree;
child next
思路,用 二叉链表 来表示树，但链表中的两个指针域含义不同。
左指针指向该结点的第一个孩子；
右指针指向该结点的下一个兄弟结点。
nextsiblingdatafirstchild
3、用孩子兄弟表示法来存储指向左孩子 指向右兄弟
A
B C D
E F
G
root
A
B
C
E D
F
G
3、树的二叉链表 (孩子 -兄弟）表示法
root
A
B
C
E D
F
G
C语言的类型描述结点结构
typedef struct CSNode{
Elem data;
struct CSNode *firstchild,*nextsibling;
} CSNode,*CSTree
firstchild data nextsibling
1）森林到二叉树的转换 ---方法
如果森林用有序表 T=(T1,T2,……,Tm)来表示，
则将森林 T转换为对应的二叉树 BT的形式化描述如下：
如果 m=0，则 BT为空；否则依次作如下操作,
将 T1的根作为 BT的根；
将 T1的子树森林转换为 BT的左子树；
将 (T2,T3,……,Tm)转换为 BT的右子树。
4、森林、树和二叉树的转换
A
B C D
E
F
G
H
J
I
A
B C D
E
F
G
H
J
I
A
B
C
D
E
F G
H
J
I
1）森林转二叉树 兄弟相连 长兄为父孩子靠左 头根为根
1,将各棵树分别转换成二叉树
2,将每棵树的根结点用线相连
3,以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构
2）二叉树到森林的转换
将二叉树 BT转换为森林 T＝ (T1,T2…… Tm)
的形式化描述如下：
若 BT不空，则依次执行如下操作：
将 BT的根转换为 T1的根；
将 BT的左子树转换为 T1的子树森林；
将 BT的右子树转换为（ T2,…… Tm）
2）二叉树转换成森林
–抹线,将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
–还原,将孤立的二叉树还原成树
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B
C
D
E
F
G
H
I
J
A
B C D
E
F
G
H I
J
3）将树转换成二叉树
– 加线,在兄弟之间加一连线
– 抹线,对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
– 旋转,以树的根结点为轴心，将整树顺时针转 45°
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B C D
E F G H I
A
B
C
D
E
F
G H
I树转换成的二叉树其右子树一定为空
4）将 二叉 树转换成树
– 加线,若 p结点是双亲结点的左孩子，则将 p的右孩子，右孩子的右孩子,…… 沿分支找到的所有右孩子，都与 p的双亲用线连起来
– 抹线,抹掉原二叉树中双亲与右孩子之间的连线
– 调整,将结点按层次排列，形成树结构
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
I
A
B
C
D
E
F
G H
IA
B C D
E F G H I
树与二叉树转换
A
CB E
D
树 A
B
C
D E
二叉树
A ^
^ B
C
^ D ^
^ E ^
A ^
^ B C
^ D ^
^ E ^
A ^
^ B
C
^ D ^ ^ E ^
对应三、树和森林 的遍历
1、树的遍历
2、森林的遍历
3、树的遍历举例树和森林的遍历 遍历 深度遍历（先序、中序、后序）
广度遍历（层次）
先序遍历
访问根结点；
依次先序遍历根结点的每棵子树。
1、树的遍历例如,a
b
d
ec 先序序列：
后序序列：
a b c d e
b d c e a
后序遍历
依次后序遍历根结点的每棵子树；
访问根结点。
树没有中序遍历
（因子树不分左右）
按层次遍历,若树不空，则自上而下自左至右访问树中每个结点。
层次遍历时顶点的访问次序：
A
B C D
E F G
H
I J K
先根遍历时顶点的访问次序：
A B E F C D G H I J K
后根遍历时顶点的访问次序：
E F B C I J K H G D A
A B C D E F G H I J K
1）树（森林）的遍历 ---先序遍历
先序遍历森林 T=(T1,T2……Tm)的描述如下：
若 T不空，则依次执行如下操作：
访问 T1的根；
先序遍历 T1的子树森林；
先序遍历森林（ T2,T3……Tm）；
void preorder(Tnode *t) //先序遍历森林
{ if (t!=NULL)
{ visite(t); //访问结点
preorder(t->firstson); //先序遍历 t的子树森林
preorder(t->nextbrother);
} //先序遍历 t的兄弟森林
}
2）树（森林）的遍历 ---后序遍历?
后序遍历森林 T=(T1,T2……Tm)的方法描述如下：
如果 T不空，则依次执行如下操作：
后序遍历 T1的子树森林；
访问 T1的根；
后序遍历森林（ T2,T3……Tm）；
void postorder(Tnode *t)
{ if (t!=NULL)
{ postorder(t->firstson); //后序遍历树 t的子树森林
visite(t); //访问树 t的根结点
postorder(t->nextbrother);
} //后序遍历 t的后续兄弟森林
} 返回讨论：若采用 先转换后遍历 方式，结果是否一样？
a
b
d e
c
先序遍历：
后序遍历：
中序遍历：
d e c b a
a
b
d
ec
a b c d e
b d c e a
1,树的 先序 遍历二法相同；
2,树的 后序 遍历相当于对应二叉树的 中序 遍历；
3,树没有 中序 遍历，因为子树无左右之分。
结论：
先序遍历
若森林为空，返回；
访问森林中第一棵树的根结点；
先序遍历第一棵树中根结点的子树森林；
先序遍历除去第一棵树之后剩余的树构成的森林。
中序遍历
若森林为空，返回；
中序遍历森林中第一棵树的根结点的子树森林；
访问第一棵树的根结点；
中序遍历除去第一棵树之后剩余的树构成的森林。
2、森林的遍历
A
B C D
E
F
G
H
J
I
B C D
E F G
H
I J K
(1) 森林中第一棵树的根结点；
(2) 森林中第一棵树的子树森林；
(3) 森林中其它树构成的森林。
可以分解成三部分：森林讨论,若采用,先转换，后遍历,方式，结果是否相同？
例如：
A
B C D
E
F
G
H
J
I
先序序列：
中序序列：
A B C D E F G H I J
B C D A F E H J I G
A
B
C
D
E
F G
H
J
I
先序序列：
中序序列：
A B C D E F G H I J
B C D A F E H J I G
结论,森林的先序和中序遍历在两种方式下的结果相同。
（但 森林的后序遍历则不一定 ）
树的遍历和二叉树遍历的对应关系？
先根遍历后根遍历树 二叉树森林先序遍历 先序遍历中序遍历 中序遍历设树的存储结构为孩子兄弟链表
typedef struct CSNode{
Elem data;
struct CSNode *firstchild,*nextsibling;
} CSNode,*CSTree;
1）求树的深度
2）输出树中所有从根到叶子的路径
3）建树的存储结构
3、树的遍历举例
int TreeDepth( CSTree T )
{ // T 是树的孩子链表存储结构,返回该树的结点和深度
if ( T.n == 0) return 0;
else return Depth( T,T.r );
} // TreeDepth
1）求树的深度
int TreeDepth(CSTree T)
{
if (T==NULL) return 0;
else {
h1 = TreeDepth(T->firstchild);
h2 = TreeDepth(T->nextsibling);
return Max(h1+1,h2)
}
}
int Depth( CTree T,int root )
{
max = 0;
p = T.nodes[root].firstchild;
while ( p ) {
h = Depth( T,p->child );
if ( h > max ) max = h;
p = p->nextchild;
}//while
return max+1;
}
A
B C D
E F G
H
I J K
2）输出树中所有从根到叶子的路径例如：对左图所示的树，
其输出结果应为：
A B E
A B F
A C
A D G H I
A D G H J
A D G H K
void AllPath( BiTree T,Stack& S )
{ // 输出二叉树上从根到所有叶子结点的路径
if (T) {
Push( S,T->data );
if (!T->Lchild && !T->Rchild ) StackTraverse(S);
else { AllPath( T->Lchild,S ); AllPath( T->Rchild,S ); }
Pop(S);
} // if(T)
} // AllPath
void OutPath( Bitree T,Stack& S )
{ // 输出森林中所有从根到叶的路径
while ( !T ) {
Push(S,T->data );
if ( !T->firstchild ) stackTraverse(S);
else OutPath( T->firstchild,S );
Pop(S);
T = T->nextsibling;
} // while
} // OutPath
A
B C D
E F
G
例如,对下列所示树的输入序列应为,
(‘#’,‘A’)
(‘A’,‘B’)
(‘A’,‘C’)
(‘A’,‘D’)
(‘C’,‘E’)
(‘C’,‘F’)
(‘E’,‘G’)
A
B
C
D
(‘#’,’)
’,’)
可见，算法中需要一个队列保存已建好的结点的指针
3）建树的存储结构 （ 不同的定义相应有不同的算法）
假设以二元组 (F,C)的形式自上而下、自左而右依次输入树的各边，
建立树的孩子 -兄弟链表。
void CreatTree( CSTree &T )
{
T = NULL;
for ( scanf(&fa,&ch); ch!=; scanf(&fa,&ch);) {
p = GetTreeNode(ch); // 创建结点
EnQueue(Q,p); // 指针入队列
if (fa==) T=p; // 所建为根结点
else { //非根结点的情况
GetHead(Q,s); // 取队列头元素 (指针值 )
while (s->data != fa ) { // 查询双亲结点
DeQueue(Q,s); GetHead(Q,s);
}
if (!(s->firstchild)) { s->firstchild = p; r = p; } //链接第一结点
else { r->nextsibling = p; r = p; } //链接其它孩子结点
}
} // for
} // CreateTree
6.4 树的应用一、堆和堆排序二、二叉排序树三,Huffman树一、堆排序堆的定义,n个元素的序列 (k1,k2,……kn)，当且仅当满足下列关系时，称之为 堆或 (i=1,2,…..,?n/2?)ki?k2ik
i?k2i+1
ki?k2i
ki?k2i+1
例（ 96,83,27,38,11,9）
例（ 13,38,27,50,76,65,49,97）
96
27
91138
83
13
2738
49657650
97
可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中
n个元素的最小值或最大值
堆排序,将无序序列建成一个堆，得到关键字最小
（或最大）的记录；输出堆顶的最小（大）值后，使剩余的 n-1个元素重又建成一个堆，则可得到 n个元素的次小值；重复执行，得到一个有序序列，这个过程叫 堆排序
堆排序需解决的两个问题：
– 如何由一个无序序列建成一个堆？
– 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？
第二个问题解决方法 ——筛选
– 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，
直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”
例 含 8个元素的无序序列（ 49,38,65,97,76,13,27,50）
49
6538
27137697
50
49
6538
27137650
97
49
1338
27657650
97
49
1338
27657650
97
13
2738
49657650
97
第一个问题解决方法
–方法：从无序序列的第?n/2?个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选例,小顶堆,降序排序
13
2738
49657650
97
97
2738
49657650
13
输出,13
27
4938
97657650
13
输出,13
97
4938
27657650
13
输出,13 27
38
4950
27657697
13
输出,13 27
65
4950
27387697
13
输出,13 27 38
49
6550
27387697
13
输出,13 27 38
76
6550
27384997
13
输出,13 27 38 49
50
6576
27384997
13
输出,13 27 38 49
97
6576
27384950
13
输出,13 27 38 49 50
65
9776
27384950
13
输出,13 27 38 49 50
97
6576
27384950
13
输出,13 27 38 49 50 65
76
6597
27384950
13
输出,13 27 38 49 50 65
97
6576
27384950
13
输出,13 27 38 49 50 65 76
97
6576
27384950
13
输出,13 27 38 49 50 65 76 97
void HeapSort ( HeapType &H ) {
// 对顺序表 H进行堆排序。
for ( i=H.length/2; i>0; --i )
HeapAdjust ( H,i,H.length );//把 H.r[1..H.length]建成大顶堆
w=H.r[1] ; H.r[1]= H.r[H.length]; H.r[H.length]=w;
//交换 "堆顶 "和 "堆底 "的记录
for ( i=H.length-1; i>1; --i ) {
HeapAdjust(H,1,i);
// 从根开始调整，将 H.r[1..i] 重新调整为大顶堆
w=H.r[1]; H.r[1]=H.r[i]; H.r[i]=w;
// 将堆顶记录和当前的“堆底”记录相互交换
// 使已有序的记录堆积到底部
}
} // HeapSort
void HeapAdjust (HeapType &H,int s,int m) {
// 已知 H.r[s..m]中记录的关键字除 H.r[s].key之外均满足堆的定义，
//本函数依据关键字的大小对 H.r[s]进行调整，使 H.r[s..m]成为一个
//大顶堆 (对其中记录的关键字而言 )
rc = H.r[s]; // 暂存根结点的记录
for ( j=2*s; j<=m; j*=2 ) { // 沿 key较大的孩子结点向下筛选
if ( j<m && H.r[j].key<H.r[j+1].key ) ++j;
// j为 key较大孩子记录的下标
if ( rc.key >= H.r[j].key ) break; // 不需要调整
H.r[s] = H.r[j]; s = j; // 把大关键字记录往上调
}
H.r[s] = rc; // 回移筛选下来的记录
} // HeapAdjust
30
27
91138
83
时间复杂度：最坏情况下 T(n)=O(nlogn)
空间复杂度,S(n)=O(1)
二、二叉排序树
1、二叉排序树的定义
2、二叉排序树的创建
3、二叉排序树的查找
4、二叉排序树的插入
5、二叉排序树的删除二、二叉排序树
1,二叉排序树的定义每一棵子树分别也是二叉排序树,
二叉排序树或者为空二叉树,或者为具有以下性质的二叉树,
若根结点的左子树不空,则左子树上所有结点的值都小于根结点的值 ;
若根结点的右子树不空,则右子树上所有结点的值都大于或者等于根结点的值 ;
递归定义
10
183
8 122
7
3
30
60
58 73
38 64
50
100503510 70
40
中序序列,
10,30,35,38,40,50,50,58,60,64,70,73,100
中序遍历二叉排序树可得到一个关键字的有序序列
2、二叉排序树的建立 (逐点插入法 )
设 K=( k1,k2,k3,…,kn )为具有 n 个数据元素的序列。从序列的第一个元素开始,依次取序列中的元素,每取一个元素 ki,按照下述原则将 ki 插入到二叉树中,
1,若 二叉树 为空,则 ki 作为该二叉树的根结点；
2,若 二叉树 非空,则将 ki 与该二叉树的根结点的值进行比较,若 ki 小于根结点的值,则将 ki插入到根结点的左子树中 ; 否则,将 ki 插入到根结点的右子树中。
将 ki插入到左子树或者右子树中仍然遵循上述原则,
例 K = ( 50,35,70,40,50,65,20,80 )
空 50
35
50
40
7035
50
7035
50
5040
7035
50
65
5040
7035
50
20
65
5040
7035
50
8020
65
5040
7035
50
3、二叉排序树的查找查找过程若二叉排序树为空,则查找失败,结束 。
若二叉排序树非空,则将 被查找元素与二叉排序树的根结点的值进行比较,若等于根结点的值,则查找成功,返回 被查到元素所在链结点的地址,查找结束 ;
若小于根结点的值,则到根结点的左子树中重复上述查找过程 ; 若大于根结点的值,则到根结点的右子树中重复上述查找过程 ; 直到查找成功或者失败。
50
35 75
40 65
38 70
T
^
^ ^^ ^^^
^ ^ ^^^ ^36 66 72
25 80
p
p
p
pp
p
p
p=nil
key=70key=45
查找成功！查找失败！
二叉排序树的插入
– 插入原则,若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
– 二叉排序树生成,从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
4、二叉排序树的插入
50
30
10
90
10070
60
T
^ ^ ^ ^ ^
^^ p 80 ^^p 80 ^^
item=80
插入算法例 { 10,18,3,8,12,2,7,3 }
10 10
18
10
183
10
183
8
10
183
8 12
10
183
8 122
10
183
8 122
7
10
183
8 122
7
3
void Insert_BST( BiTree &T,KeyType e ) {
// 在以 T为根指针的二叉排序树中插入记录 e
s = new BiTNode; // 生成新的结点
s ->data = e; s->lchild = NULL; s->rchild = NULL;
if (!T) T = s; // 插入的结点为根结点
else {
p = T;
while ( p) // 查找插入位置
if ( e,key< p->data,key)
{ f = p; p = p->lchild; } // 应插入在左子树中
else
{ f = p; p = p->rchild; } // 应插入在右子树中
if ( e.key < f->data.key ) f->lchild = s;
// 插入为 f 所指结点的左子树根
else f->rchild = s; // 插入为 f所指结点的右子树根
} //else
} // Insert_BST
10
183
8
void BSTSort( SqTable &L )
{
// 利用二叉排序树对顺序表 L进行排序
BiTree T = NULL; // 初始化二叉排序树为空树
for ( i=1; i<L.length; ++i)
Insert_BST( T,L.r[i] ); // 按顺序表 L构造二叉排序树
i = 0;
InOrder( T,Output(T,L,i) ); // 中序遍历二叉排序树
// 通过函数指针引用 Output,将排序的记录由小到大输出至 L.r[i]
} // BSTSort
其中函数 Output的具体实现如下：
void Output ( BiTree T,SqTable &L,int & i )
{
L.r[++i]=T->data;
}
50
35 75
40 65
38 70
T
^
^
^
^
^ ^ ^
^
50
35 75
40 65
38 70
T
^
^
^
^
^ ^ ^
^
1,被删除结点为叶结点,则直接删除,
2,被删除结点无左子树,则用右子树的根结点取代被删除结点,
3,被删除结点无右子树,则用左子树的根结点取代被删除结点,
5、二叉排序树的删除
50
36 75
40 65
38 70
T
^
^ ^^ ^^^
^
^^^ ^66 72
25 80
50
35 72
40 65
38 70
T
^
^ ^^ ^^^
^ ^
^
^ ^36 66
25 80
50
35 75
40 65
38 70
T
^
^ ^^ ^^^
^ ^ ^^^ ^36 66 72
25 80
4,被删除结点的左、右子树都存在,则用被删除结点的右子树中值最小的结点 (或被删除结点的左子树中值最大的结点 )取代被删除结点,
删除算法例 80
50 120
60 110 150
55 70
53
删除 50
80
60 120
110 15055 70
53
删除 60
80
55 120
110 15053 70
10
4 25
8 13
5
4
删除 10
8
4 25
5 13
4
删除 5
8
4 25
4 13
三,Huffman树
1,最优树与 Huffman树
2,Huffman树的构造
3,Huffman树的实现
4,Huffman树的应用路 径,
路径长度,
树的路径长度,
带权路径长度,
树的带权路径长度,
霍 夫 曼 树,
1,Huffman树定义最优二叉树（ 霍夫曼 树）
由一结点到另一结点间的分支所构成路径上的分支数目从树根到 每一结点 的路径长度之和。
结点到根的路径长度与结点上权的乘积预备知识：若干术语树中所有 叶子结点 的带权路径长度之和带权路径长度最小的树。
a→e 的路径长度＝
树长度＝
2
10
2
4
5 9
WPL = w1*l1 + w2*l2 + … + wn*ln
其中,n为树中叶子结点的个数；
wi为第 i个叶子结点的权值；
l1为第 i个叶子结点的路径长度。
例 有 4个结点，权值分别为 7,5,2,4，构造有 4个叶子结点的二叉树
a b c d
7 5 2 4
WPL=7*2+5*2+2*2+4*2=36d
c
a b
2
4
7 5
WPL=7*3+5*3+2*1+4*2=46
a
b
c d
7
5
2 4
WPL=7*1+5*2+2*3+4*3=35
=
=
n
k
KK LWWPL
1
哈夫曼 树 则 是,WPL 最小的树。
哈夫曼树判定树 在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。
例 将学生百分成绩按分数段分级的程序。
若学生成绩分布是均匀的,可用图 (a)二叉树结构来实现。
a<60
a<70
a<80
a<90
不及格中等良好 优秀及格
Y N
Y N
Y N
Y N
(a)
输入 10000个数据，则需进行 31500次比较。
分数 0—59 60—69 70—79 80—89 90—99
比例 0.05 0.15 0.4 0.3 0.10
70≤a≤ 80
a<60
80≤a<90
60≤a<70
(b)
(c)
学生成绩分布不是均匀的情况：
以比例数为权构造一棵哈夫曼树,如 （ b)判断树所示 。
再将每一比较框的两次比较改为一次,可得到 （ c)判定树 。
输入 10000个数据，仅需进行 22000次比较。
2,Huffman树的构造按照 Huffman树的定义,Huffman最早提出了构造最优树的方法，其基本 思想 是：
⑴ 由给定的 n个权值构成 n棵二叉树的集合 F，其中每一棵二叉树中只有一个带权的根结点；
⑵ 在 F中选取两棵根结点权值最小的二叉树作为左、右子树构造一棵新的二叉树，
且臵新的二叉树的根结点的权值为左、
右子树上根结点权值之和；
⑶ 在 F中删除这两棵二叉树，同时将新得到的二叉树加入到 F中；
⑷ 重复⑵和⑶，直到 F中只含一棵二叉树为止。
例
a
7
b5 c
2
d
4
a
7
b5
c
2
d
4
6
a
7
b5
c
2
d
4
6
11
a
7
b5
c
2
d
4
6
11
18
例 w={5,29,7,8,14,23,3,11}
5 1429 7 8 23 3 11
1429 7 8 23 11
35
8
87
151429 23
35
811
11
35
8
191429 23
87
15
11
35
8
1929 23
14
87
15
29
29
14
87
15
29
11
35
8
1923
42
11
35
8
1923
42
29
14
87
15
29
58
11
35
8
1923
42
29
14
87
15
29
58
100
9
例如,已知权值 W={ 5,6,2,9,7 }
5 6 2 7
5 2
76 9 7
6 7
139
5 2
7
9
5 2
7
16
6 7
13
290
0 0
0
1
1 1
100 01 11
100 101
3,Huffman编码规则：
左,0” 右,1”，是一种前缀码，也称为最小冗余编码、紧致码，等等，它是数据压缩学的基础。
typedef struct {
int weight;
int lchild,rchild;
} HTNode
typedef struct {
HTNode *HTree;
int root;
}Huffman Tree;
3,Huffman树实现 --存储结构
weight lchild rchild
……
HTreeweight lchild rchild00
1
2
…
2n-1
一棵有 n个叶子结点的 Huffman树有 2n-1个结点
采用顺序存储结构 ——一维结构数组赫夫曼算法的实现：
1、建立具有 2n-1个单元的数组，其中 n个单元用于保存初始结点,n-1个结点用于表示内部结点。
2、执行 n-1次循环，每次产生一个内部结点。权值最小的两个结点为其左右儿子。
3、计算每个字符的赫夫曼编码 。
在远程通讯中，要将待传字符转换成由二进制组成的字符串：
设要传送的字符为,ABACCDA
若编码为,A—00
B—01
C—10
D---11
若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码,则转换的二进制字符串便可能减少。
00010010101100
4、哈夫曼树的应用 (哈夫曼编码 )
设要传送的字符为,ABACCDA
若编码为,A—0
B—00
C—1
D---01
关键,要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀。这种编码称作 前缀编码 。
ABACCDA
000011010
但,0000
AAAA ABA BB 重码前缀编码 指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。
利用赫夫曼树可以构造一种 不等长 的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传字符编码（电文）的总长度最短。
设要传送的字符为,ABACCDA
若编码为,A—0
B—110
C—10
D---111
0110010101110A
C
B D
0
0
0
1
1
1
采用二叉树设计二进制前缀编码规定：
左分支用,0”表示；
右分支用,1”表示译码过程,分解接收字符串：遇,0”向左，遇,1”向右；
一旦到达叶子结点，则译出一个字符，反复由根出发，
直到译码完成。
0110010101110
A
C
B D
0
0
0
1
1
1
ABACCDA
求 Huffman编码：由叶子 → 根，若：
（ 1）从左分支下去，则分支为,0”；
（ 2）从右分支下去，则分支为,1”。
例：已知某系统在通讯时，只出现 C,A,S,T,B五种字符，
它们出现的频率依次为 2,4,2,3,3，试设计 Huffman编码。
W(权 )={2,4,2,3,3}，叶子结点个数 n=5
14
8
4
6
4
2 2
0
0
0
1
1
13 3
0 1
构造的
Huffman树
T B A
C S
出现频率越大的字符，其 Huffman编码越短。
由 Huffman树得 Huffman编码为：
T B A C S
00 01 10 110 111
Huffman编码,数据通信用的二进制编码思想,根据字符出现频率编码，使电文总长最短编码,根据字符出现频率构造 Huffman树，然后将树中结点引向其左孩子的分支标,0”，引向其右孩子的分支标,1”；每个字符的编码即为从根到每个叶子的路径上得到的 0,1序列例 要传输的字符集 D={C,A,S,T,; }
字符出现频率 w={2,4,2,3,3}
C S
33
6
4
2 2
4
8
14
T ; A
0
0
1
1 0 1
10
T,00;,01
A,10
C,110
S,111
4,Huffman树的应用
译码,从 Huffman树根开始，从待译码电文中逐位取码。若编码是,0”，则向左走；若编码是,1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束例 电文是 {CAS;CAT;SAT;AT}
其编码,11010111011101000011111000011000”
电文为,1101000”
译文只能是,CAT”
C S
33
6
4
2 2
4
8
14
T ; A
0
0
1
1 0 1
10
T,00;,01
A,10
C,110
S,111
4,Huffman树的应用例,假设用于通信的电文仅由 8个字母
{ a,b,c,d,e,f,g,h } 构成，它们在电文中出现的概率分别为
{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，
试为这 8个字母设计哈夫曼 编码。 如果用 0～ 7的二进制编码方案又如何？
霍夫曼编码的基本思想,概率大的字符用短码，概率小的用长码。 由于 霍夫曼树的 WPL最小,说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。
解,先将概率放大 100倍，以方便构造哈夫曼树。
权值集合 w={7,19,2,6,32,3,21,10}，
按哈夫曼树构造规则（合并、删除、替换），
可得到哈夫曼树。
w4={19,21,28,32}
为清晰起见，重新排序为,
w={2,3,6,7,10,19,21,32}
2 3
56
w1={5,6,7,10,19,21,32}
w2={7,10,11,19,21,32}
w3={11,17,19,21,32}
11
107
17
282119
40
w5={28,32,40}
32
60
w6={40,60}
w7={100}
100
b
c
a d
eg
f
h哈夫曼树
× ×
× ×
× ×
× ×
× ×
× ×
× ×
对应的哈夫曼编码（左 0右 1）：
2 3
56
11
107
32
17
282119
40 60
100
b
c
a d
eg
f
h
0
0
0
0
0
1
11
1
1
1
10
0
符 编码 频率
a 0.07
b 0.19
c 0.02
d 0.06
e 0.32
f 0.03
g 0.21
h 0.10
符 编码 频率
a 0.07
b 0.19
c 0.02
d 0.06
e 0.32
f 0.03
g 0.21
h 0.10
Huffman码的 WPL＝ 2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03)
=1.44+0.92+0.25=2.61
WPL＝ 3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3
1100
00
11110
1110
10
11111
01
1101
000
001
010
011
100
101
110
111
二进制码例,假设用于通信的电文仅由 8个字母 a,b,c,d,e,f,g,h构成，
它们在电文中出现的概率分别为 0.05,0.29,0.07,
0.08,0.14,0.23,0.03,0.11，试为这 8个字母设计哈夫曼 编码。 如果用 0～ 7的二进制编码方案又如何？
解,先将概率放大 100倍，以方便构造哈夫曼树。
权值集合 w={5,29,7,8,14,23,3,11},n=8,则 m=5
typedef struct {
int weight;
int lchild,rchild;
} HTNode
typedef struct {
HTNode *HTree;
int root;
} HuffmanTree;
weight lchild rchild
……
HTreeweight lchild rchild0
1
2
…
2n-1
一棵有 n个叶子结点的 Huffman树有 2n-1个结点采用顺序存储结构 ——一维结构数组
if (n<=1) return;
void Create(HuffmanTree &HT,int *w,int n) {
typedef struct {
int weight;
int lchild,rchild;
} HTNode
typedef struct {
HTNode *HTree;
int root;
} HuffmanTree;
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
HT weight lchild rchild
5 -1 -1
29 -1 -1
7 -1 -1
8 -1 -1
14 -1 -1
23 -1 -1
3 -1 -1
11 -1 -1
8 6 0
15 2 3
19 8 7
29 4 9
42 10 5
58 11 1
100 12 13
0 1 2 3 4 5 6 7
5
15
29
8
19
42 58
100
29
b
7
c
5
a
8
d
14
e
3
g
23
f
11
h0
0
0
0
0
1
1 1
11
1 10
0
wN=8anT ee
weight lchild rchild
HTNode
HT int 29 7 8 14 23 3 11
m=15m = 2 * n - 1;
HT.HTree = new HTNode[m];
for ( p=HT.Tree,i=1; i<=n; ++i,++p,++w)
*p = { *w,-1,-1 };
for ( ; i<=m; ++i,++p ) *p ={ 0,-1,-1 };
0 -1 -1
0 -1 -1
0 -1 -1
0 -1 -1
0 -1 -1
0 -1 -1
0 -1 -1
for (i=n;i<m;++i) {
Select(HT.Htree,i-1,s1,s2);
HT.Htree [i].lchild = s1; HT.Htree[i].rchild = s2;
HT.Htree[i].weight = HT.Htree[s1].weight +HT.Htree[s2].weight;
}
8 6 0
HT.root = m-1;
}
P = HC;
InitStack(S);
Codeing(HT,HT.root,S);
}
if ( T ) {
if ( ( T.Tree[i].lchild==-1 ) && (T.Tree[i].rchild==-1) ) {
*HC[i] = new char[StackLength(S)];
StackTraverse(S);
}
0 0 1
0 1
0 0 0 0
1 1
1 0 1 0
0 0 0 1
1 0 1 1
1 0 0
0
1
2
3
4
5
6
7
HC
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
HT weight lchild rchild
5 -1 -1
29 -1 -1
7 -1 -1
8 -1 -1
14 -1 -1
23 -1 -1
3 -1 -1
11 -1 -1
8 6 0
15 2 3
19 8 7
29 4 9
42 10 5
58 11 1
100 12 13
S
void HuffmanCoding( HuffmanTree HT,HuffmanCode &HC,int n )
{
Stack S;
HC = new (char *)[n];
i (,.r t,);
i Coding( HuffmanTree T,int i,Stack &S )
{
Push( S,‘0’ );
Coding(T,T.Tree[i].lchild,S);
Pop( S,e );
Push( S,‘1’ );
Coding(T,T.Tree[i].rchild,S);
Pop( S,e );
}
} a
b
c
d
e
f
g
h
0001
11
1010
1011
100
01
0000
001 0
15
29
8
19
42 58
100
29
b
7
c
5
a
8
d
14 e
3
g
23
f
11
h0
0
0
0
0
1
1 1
11
1 10
0
14
0
0
01
1
1
1
0
a
b
c
d
e
f
g
h
typedef char ** HuffmanCode
void HuffmanCoding( HuffmanTree HT,HuffmanCode &HC,int n )
{
Stack S;
HC = new (char *)[n]; P = HC;
InitStack(S);
Codeing(HT,HT.root,S);
}
void Coding( HuffmanTree T,int i,Stack &S )
{
if ( T ) {
if ( ( T.Tree[i].lchild==-1 ) && (T.Tree[i].rchild==-1) ) {
*HC[i] = new char[StackLength(S)]; StackTraverse(S);
}
Push( S,‘0’ );
Coding( T,T.Tree[i].lchild,S );
Pop( S,E );
Push( S,‘1’ );
Coding( T,T.Tree[i].rchild,S );
Pop( S,e );
}
}
void Create(HuffmanTree &HT,int *w,int n) {
if (n<=1) return;
m = 2 * n - 1;
HT.HTree = new HTNode[m];
for ( p=HT.Tree,i=1; i<=n; ++i,++p,++w)
*p = { *w,-1,-1 };
for ( ; i<=m; ++i,++p ) *p ={ 0,-1,-1 };
for (i=n;i<m;++i) {
Select(HT.Htree,i-1,s,s2);
HT.Htree [i].lchild = s1; HT.Htree[i].rchild = s2;
HT.Htree[i].weight = HT.Htree[s1].weight +HT.Htree[s2].weight;
}
HT.root = m-1;
}
1,熟练掌握 二叉树的结构特性,了解相应的证明方法。
2,熟悉二叉树的各种 存储结构 的特点及适用范围。
3,遍历二叉树 是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。 层次遍历是按另一种搜索策略进行的遍历。
4,理解二叉树 线索化的实质 是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的 线索化过程 以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的 线索化过程 是 基于 对二叉树进行 遍历,而线索二叉树上的 线索又为相应的遍历提供了方便 。
5,熟悉 树的各种存储结构 及其特点，掌握 树和森林与二叉树的转换 方法。建立存储结构是进行其它操作的前提，因此读者应 掌握 1 至 2 种建立二叉树和树的存储结构的方法。
6,学会编写 实现树的各种操作 的算法。
7,了解 最优树的特性,掌握建立 最优树和哈夫曼编码 的方法,
本章总结本章小结
1、定义和性质
2、存储结构
3、遍历
4、线索化：线索树顺序结构链式结构二叉链表三叉链表先序线索树中序线索树后序线索树树二叉树森林先序遍历后序遍历遍历存储结构 遍历双亲表示孩子表示孩子兄弟先序遍历 后序遍历中序遍历后序遍历先序遍历霍夫曼树 霍夫曼编码
