2009-7-30 软件基础教案（第 7章 树和二叉树）
树二叉树二叉树的设计和实现二叉树的遍历二叉树的应用（哈夫曼编码和二叉排序树）
树、森林与二叉树的转换树的遍历第七章 树和二叉树
Chapter 7 Tree and Binary Tree
2009-7-30 软件基础教案（第 7章 树和二叉树）
7.1树的概念树是由 n (n? 0)个结点组成的有限集合。如果 n = 0，
称为空树；如果 n > 0，则
有一个特定的称之为 根
(root)的结点，它只有直接后继，但没有直接前驱；
b
a
c
g hd e f
i j
1.树的定义
2009-7-30 软件基础教案（第 7章 树和二叉树）
除根以外的其它结点划分为 m (m? 0)个互不相交的有限集合 T0,T1,…,Tm-1，每个集合又是一棵树，
并且称之为根的 子树 (SubTree)。
每棵子树的根结点有且仅有一个直接前驱，但可以有 0个或多个直接后继。
b
a
c
g hd e f
i j
2009-7-30 软件基础教案（第 7章 树和二叉树）
特点：
除根结点之外的所有结点有且只有一个前驱结点，根结点没有前驱结点
树中所有结点可以有零个或多个后继结点
b
a
c
g hd e f
b
a
c
g hd e
f
非树结构树结构描述的是 层次关系
2009-7-30 软件基础教案（第 7章 树和二叉树）
直观表示法 b
a
c
g hd e f
i j
2.树的表示
2009-7-30 软件基础教案（第 7章 树和二叉树）
形式化表示法
T=(D,R)
D:D=?; 空树 R={<Root,ri>,i=1,2,…m }
D;D={Root}? DF ri:是 Root子树的根结点
Root:树的根结点
DF,树的根结点 Root的子树集合
DF= D1? D2? D3 ….,? Dm 并且 Di?Dj=?
(i? j; i=1,2,…m ; j=1,2,…m )
2009-7-30 软件基础教案（第 7章 树和二叉树）
凹入表示
a
b
d
e
i
j
f
c
g
h
----主要用于树的屏幕和打印机显示。
2009-7-30 软件基础教案（第 7章 树和二叉树）
i jd f g h
ab ce
a ( b ( d,e ( i,j ),c ( g,h ) ) )
嵌套集合表示
嵌套括号表示二、树的基本术语
（ 1） 结点,由数据元素和构造数据元素之间关系的指针组成,
（ 2） 结点的度,结点所拥有的子树的个数。
（ 3） 叶子结点,度为 0的结点。
（ 4） 分枝结点,度不为 0的结点。
（ 5） 树的度,树中各结点度的最大值称为该树的度。
（ 6） 孩子、兄弟、双亲,树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它的孩子结点的双亲。具有同一个双亲的孩子结点互为兄弟。
（ 7） 结点的层次,规定树的根结点的层次为 0，其余结点的层次等于它的双亲结点的层次加 1。
（ 8） 树的深度,树中所有结点的最大层次称为树的深度。
（ 9） 有序树和无序树,如果一棵树中结点的各子树从左到右是有次序的，即若交换某结点各子树的相对位置则构成不同的树，称这棵树为有序树；否则为无序树。
（ 10） 森林,零棵或有限棵不相交的树的集合称为森林。
A
DCB
E F G H I
三、树的基本操作
1、初始化
2、求指定结点所在树的根结点
3、求指定结点的双亲结点
4、求指定结点的某一孩子结点
5、求指定结点的最右边兄弟结点
6、将一棵树插入到另一树的指定结点下作为它的子树
7、删除指定结点的某一子树
8、树的遍历遍历：按某种方式访问树中的每个结点，且每个结点只被访问一次。
2009-7-30 软件基础教案（第 7章 树和二叉树）
四、树的存储结构
双亲表示法
孩子表示法
孩子兄弟表示法
双亲孩子表示法多种存储形式，两大类,顺序存储；
链接存储；
2009-7-30 软件基础教案（第 7章 树和二叉树）
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
序号 data parent1.双亲表示法 （顺序存储）
2009-7-30 软件基础教案（第 7章 树和二叉树）
#define MAXNODE 32
typedef struct
{ datatype data; \\ 数据域
int parent; \\ 双亲域
} ptree;
ptree t[MAXNODE];
双亲表示法－－ c语言描述特点：难于实现寻找一个结点的孩子结点的操作便于实现寻找一个结点的双亲结点的操作
2009-7-30 软件基础教案（第 7章 树和二叉树）
改进：
增加两个域：存储该结点的第一个孩子结点，在数组中的序号。
存储该结点的第一个右兄弟结点在数组中的序号。
typedef struct
{ datatype data; \\ 数据域
int parent; \\ 双亲域
int son; \\孩子结点
int next; \\兄弟结点
} ptree;
2009-7-30 软件基础教案（第 7章 树和二叉树）
2.孩子表示法 A
B C D
E F G H I J
A
B ∧ C ∧ ∧ D
E∧ ∧ ∧ F∧ ∧ ∧ G∧ ∧ ∧ H∧ ∧ ∧ I ∧ ∧ ∧ J∧ ∧ ∧
两种方法：
结点的指针域的个数 =树的度。 同构型
结点的指针域的个数 =结点的度 异构型同构型
（多重链表法）
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B C D
E F G H I J
异构型
2009-7-30 软件基础教案（第 7章 树和二叉树）
typedef struct TreeNode
{ int data;
struct TreeNdoe *Son[MAXSON];
} nodetype;
孩子表示法－－ c语言描述 (同构型 )
特点：便于实现寻找一个结点的孩子结点的操作难于实现寻找一个结点的双亲结点的操作
A
B C D
E F G H I J
序号 data parent
将双亲表示与孩子表示结合起来
3、双亲孩子表示法
J 3
A -1
B 0
C 0
D 0
E 1
F 1
G 2
H 3
I 3
1 2 3
7 8 9
4 5
6
0
1
2
3
4
5
6
7
8
9
∧
∧
∧
∧
∧
∧
∧
∧
∧
typedef struct cnode
{ int child; \\ 孩子结点序号
struct cnode *next; \\ 下一个孩子结点
} link;
结点
data parent headptr child next
T[]
孩子链表双亲－－孩子链表表示法
typedef struct
{ datatype data;
int parent;
link *headptr;
} ctree;
ctree T[MAXNODE];
结构体数组
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B
C
E D
F
G
4、孩子兄弟表示法（二重链表法）
B D
A
C
E F
G
左孩子 -右兄弟表示法树的左孩子 -右兄弟表示
data firstChild nextSibling
2009-7-30 软件基础教案（第 7章 树和二叉树）
孩子兄弟表示 —C语言描述
typedef struct TreeNode
{ elemtype data;
struct TreeNode *son;
struct TreeNode *next
} nodetype;
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B
G
D
C
H
E F 二叉树
7.2 二叉树
（ 1）定义,一棵二叉树是结点的一个有限集合。
该集合或者为空
或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
1.二叉树的定义
2009-7-30 软件基础教案（第 7章 树和二叉树）
(2) 二叉树的特点：
度小于等于 2
有序树
(3) 二叉树的五种基本形态左子树 右子树 右子树左子树
(a) (b) (c) (d) (e)
2009-7-30 软件基础教案（第 7章 树和二叉树）
(1) 满二叉树 (Full Binary Tree)
一棵深度为 h且有 2h-1个结点的二叉树。
对树中结点按从上到下、从左到右的顺序进行编号。
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
a
b
d
c
e f
h i j
g
k l m n o
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
2.特殊二叉树若二叉树的深度为 h，且共有 n个结点。对树中结点 按从上到下、从左到右的顺序进行编号，若编号为 i(1≤i≤n)的结点与满二叉树编号为 i的结点位置相同，则此树称为完全二叉树。
除第 h层外，其它各层
(1?h-1)的结点数都达到最大个数，第 h层从右向左连续缺若干结点，这就是完全二叉树。
1
2 3
4 5 6 7
8 9 10 11 12
(2) 完全二叉树 (Complete Binary Tree)
2009-7-30 软件基础教案（第 7章 树和二叉树）
显然，一棵满二叉树一定是一棵完全二叉树
1
2 3
4 5 6 7
8 9 10 11
2 3
4 5 6
7 8 9
1
非完全二叉树 非完全二叉树
(3) 平衡二叉树
A
C
E F
B
D
–平衡因子：二叉树任意结点的左子树深度减去右子树深度的差值，为此结点的平衡因子。
–平衡二叉树：二叉树中每个结点的平衡因子的绝对值都不大于 1，则称这棵二叉树为平衡二叉树,
2 3
4 5
69
1
平衡二叉树 非平衡二叉树
2009-7-30 软件基础教案（第 7章 树和二叉树）
1、创建二叉树
2、撤消二叉树
3、左插入结点
4、右插入结点
5、左删除子树
6、右删除子树
7、遍历二叉树
8、其他,左插入子树,右插入子树,左删除结点,
右删除结点等
3,二叉树 的 基本操作
2009-7-30 软件基础教案（第 7章 树和二叉树）
4,二叉树的性质性质 1 若二叉树的层次从 0开始,则在二叉树的第 i 层最多有 2i个结点。 (i? 0)
证明,i = 0 时，有 2i = 20 =1，成立假定,i = k 时性质成立；即有 2k个结点,
当 i = k+1 时，第 k+1的结点至多是第 k层结点的两倍，即总的结点个数至多为 2× 2k = 2k+1
故命题成立
2009-7-30 软件基础教案（第 7章 树和二叉树）
性质 2 若规定空树的深度为 -1，则深度为 k的二叉树最多有 2k+1-1个结点。 (k? -1)
证明：当深度为 -1时，是空二叉树，为没有结点，
有 2-1+1-1=0，结论成立；
仅当每一层都含有最大结点数时，二叉树的结点数最多，利用性质 1可得二叉树的结点数至多为：
20 + 21 + 22 + 23 + … + 2k = 2k+1 － 1
2009-7-30 软件基础教案（第 7章 树和二叉树）
性质 3 对任何一棵二叉树,如果其叶结点个数为
n0,度为 2的非叶结点个数为 n2,则有
n0＝ n2＋ 1
证明：
1、结点总数为度为 0的结点加上度为 1的结点再加上度为 2的结点,n = n0 + n1 + n2
2、另一方面，二叉树中一度结点有一个孩子，二 度结点有二个孩子，根结点不是任何结点的孩子，因此，
结点总数为,n = n1 + 2n2 + 1
3、两式相减，得到：
n0 = n2 + 1
2009-7-30 软件基础教案（第 7章 树和二叉树）
1
2 3
4 5 6 7
8 9 10 11
5,6为度为 1的结点：也就是 n1=2
1,2,3,4为度为 2的结点：也就是 n2=4
10,11可以分别用 5,6表示，故他们的和为 n1；
8,9用 4表示,6,7用 3表示,4,5用 2表示,2,3用 1表示故 2~9的个数和为 2n2；
结点 1没有表示，但他只有一个，所以总的个数为 n1+2n2+1
2009-7-30 软件基础教案（第 7章 树和二叉树）
性质 4具有 n个结点的完全二叉树的深度为? log2（ n+1)? -1 (“,表示上取整 )
证明：设完全二叉树的深度为 h，则有
2h - 1 < n? 2h+1 - 1
2h< n+1 <= 2h+1
取对数
h< log2(n+1) <= h+1
1
2 3
4 5 6 7
8 9 10 11 12
性质 5具有 n个结点的 满 二叉树,h=log2(n+1)-1从第一层开始,自上而下逐层从左到右给每个结点从 1开始编号,对序号为 j的结点，规律有,
① 若 j≤2 h-1,结点 j的左孩子结点编号为 2*j,右孩子结点编号为 2*j+1;
② 若 j>1,则结点 j的双亲结点的编号为?j/2?(下取整 ).
可见可对其采用 顺序存贮结构,
例,h=log2(n+1)-1=3 2h-1=7
j=3,左孩子结点编号,2*3=6
右孩子结点编号,2*3+1=7
j=5，双亲结点编号,?j/2?
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
2009-7-30 软件基础教案（第 7章 树和二叉树）
性质 6 如果将一棵有 n个结点的 完全二叉树 自顶向下，同一层自左向右连续给结点编号 1,2,…,n-1,n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中,(1
i? n)。则有以下关系：
若 i == 1,则 i 无双亲
若 i > 1,则 i 的双亲为?i /2?
若 2*i <= n,则 i 的左孩子为 2*i； 否则 (2*i > n),i没有左孩子，必定是叶子结点，二叉树中 i>? n/2? 的结点必定是叶结点
1
2
4
3
5 6
8 9 10
7
11 12 13 14 15
16 17
若 2*i+1 <= n,则 i 的右孩子为 2*i+1，否则,i无右孩子
若 i(不为 1)为奇数,且 i<n，则其左兄弟为 i-1，否则无左兄弟；
若 i 为偶数,且小于 n,则其右兄弟为 i+1，否则无右兄弟
i 所在层次为?log2 (i)?
例,i=5,2*i<n,
左孩子,10，右孩子,11
左兄弟,4,右兄弟,6
i=8
i=9
2009-7-30 软件基础教案（第 7章 树和二叉树）
1,顺序存储结构
A
C
GF
B
D E
H I J
0 1 2 3 4 5 6 7 8 9
A B C D E F G H I J
7.3 二叉树的设计和实现
7.3.1二叉树的存储结构
Bt
2009-7-30 软件基础教案（第 7章 树和二叉树）
顺序存储结构
A
CB
G H
D E F
0 1 2 3 4 5 6 7 8 9 10 11 12 13
A B C D E F G HBt
2009-7-30 软件基础教案（第 7章 树和二叉树）
单支树由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。
31
12
17
88
49
31 12 17 88
49
2009-7-30 软件基础教案（第 7章 树和二叉树）
#define MAXNODE <二叉树中结点最大个数 >
Typedef int elemtype;
elemtype bt[MAXNODE];
顺序二叉树结点的 c语言描述
2009-7-30 软件基础教案（第 7章 树和二叉树）
链式存储结构形象化描述 (不带头结点 )
A
B
G
D
C
H
E F
^B
^ D
^ ^G
C
^F^ ^E
^ ^H
A
bt
2,链式存储结构
2009-7-30 软件基础教案（第 7章 树和二叉树）
链式存储结构形象化描述 (带头结点 )
A
B
G
D
C
H
E F
^B
^ D
^ ^G
C
^F^ ^E
^ ^H
A
bt
头结点根结点
2009-7-30 软件基础教案（第 7章 树和二叉树）
左孩子
Lchild
数据
Data
右孩子
Rchild
结点结构
BTreeNode
链式存储结构的 c语言描述
typedef int elemtype;
typedef struct node
{ elemtype data;
struct node *lchild,*rchild;
} bitree;
2009-7-30 软件基础教案（第 7章 树和二叉树）
7.3.2二叉树的操作实现
1001
bt
1.二叉树的初始化
*bt
1001 头结点 **bt
125A
NULL NULL
125A
2009-7-30 软件基础教案（第 7章 树和二叉树）
初始化算法
int Initiate(bitree **bt)
{ if((*bt=(bitree*)malloc(sizeof(bitree)))==NULL)
return 0;
(*bt)->Lchild=NULL;
(*bt)->Rchild=NULL;
return 1;
}
2009-7-30 软件基础教案（第 7章 树和二叉树）
2.二叉树的创建
1001
bt *bt
1001 头结点 **bt
125A
1A05 NULL
125A
X
根结点
1A05
NULL NULL
1.创建一个只有根节点的二叉树
2009-7-30 软件基础教案（第 7章 树和二叉树）
int Initiate(bitree *bt)
{bitree* p;
if((p=(bitree*)malloc(sizeof(bitree)))==NULL)
return 0;
p-> data=x;
p->Lchild=NULL;
p->Rchild=NULL;
bt->Lchild=p;
return 1;
}
2009-7-30 软件基础教案（第 7章 树和二叉树）
x
^B
^ D
^ ^G
117C
C
^F^ ^E
^ ^H
1006
147E
p
117C 1006
从这一过程可以看出，二叉树的建立过程，就是对结点的一一插入。所以我们可以通过插入算法来建立树。
2009-7-30 软件基础教案（第 7章 树和二叉树）
3.二叉树的插入
A
B
G
D
C
H
E F
parent
x
将结点 x插入到结点 parent的左孩子处
A
B
G
D
C
H
E F
parent
G
D
x
2009-7-30 软件基础教案（第 7章 树和二叉树）
147E
p
x
C
^F^ ^E
^ ^H
A
bt
^ ^B
*Parent
NULLNULL
147E
2009-7-30 软件基础教案（第 7章 树和二叉树）
bt
C
^F
^ ^D ^ ^H
A
^ ^B
*Parent
^ ^E
132B147E
p
x NULLNULL132B
147E
Bitree *InsertL(elemtype x,bitree *parent)
{ bitree *p;
if(parent==NULL)
{printf(“/n插入出错,);
return NULL;}
if((p=(bitree*)malloc(sizeof(bitree)))==NULL)
return NULL;
p->data=x;
p->Lchild=NULL;
p->Rchild=NULL;
if(parent->Lchild==NULL) parent->Lchild=p;
else { p->Lchild=parent->Lchild;
parent->Lchild=p;}
return p;
}
判 parent
是否存在申请新结点
xNULL NULL
Parent无左孩子时
Parent有左孩子时二叉树插入算法将结点 x插入到结点 parent的右孩子处原理同上。自学
2009-7-30 软件基础教案（第 7章 树和二叉树）
删除二叉树 bt中结点 parent的左子树
A
B
G
D
C
H
E F
parent
A
B
G
D
C
H
E F
parent
4.二叉树的删除
2009-7-30 软件基础教案（第 7章 树和二叉树）
bt
C
^FD
^ ^H
A
^ ^B
*Parent
^ ^E
132B
^ ^G^ ^I
p
NULL
132B
2009-7-30 软件基础教案（第 7章 树和二叉树）
Bitree *DeleteL(bitree *bt,bitree *parent)
{ bitree *p;
if(parent==NULL || parent->Lchild==NULL )
{printf(“/n出错,);
return NULL;
}
p= parent->Lchild ;
parent->Lchild=NULL;
free(p);
return bt;
}
删除二叉树 bt中结点 parent的右子树，原理同上，自学删除算法
Parent无左孩子时释放结点判 parent是否存在和它的左子树是否存在
2009-7-30 软件基础教案（第 7章 树和二叉树）
Destroy(bitree* bt)
{
if(bt-> Lchild!=NULL)
Destroy(bt-> Lchild);
if(bt-> Rchild!=NULL)
Destroy(bt-> Rchild);
free(bt);
}
一、二叉树的遍历二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且只被访问一次。
7.4 二叉树的遍历由二叉树的 递归 定义，二叉树的三个基本组成单元是,根结点、左子树 和 右子树 。
根
{左子树 } {右子树 }
Preorder（先序）
Inorder（中序）
Postorder（后序）
2009-7-30 软件基础教案（第 7章 树和二叉树）
前序遍历二叉树的 操作定义 为：
若二叉树为空，则空操作；否则
（ 1）访问根结点；
（ 2）前序遍历左子树；
（ 3）前序遍历右子树。
根 左 右
1,前（先）序遍历（ DLR）
2009-7-30 软件基础教案（第 7章 树和二叉树）
C
F
B
G
D
H
E
A
B
G
D
C
H
E F
A
A DB GE H FC
前（根）序遍历
2009-7-30 软件基础教案（第 7章 树和二叉树）
前序遍历算法若二叉树为空，遍历结束。否则，
（ 1）访问根结点；
（ 2）前序遍历根结点的左子树；
（ 3）前序遍历根结点的右子树。
void preorder(treenode *bt)
{
if (bt==NULL) return;
printf(,%d”,bt->data);
if(bt->lchild!=NULL) preorder(bt->lchild);
if(bt->rchild!=NULL) preorder(bt->rchild);
}
2009-7-30 软件基础教案（第 7章 树和二叉树）
2,中序遍历（ LDR）
中序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（ 1）中序遍历左子树；
（ 2）访问根结点；
（ 3）中序遍历右子树。
左 根 右
2009-7-30 软件基础教案（第 7章 树和二叉树）
中（根）序遍历
B
G
D
H
E
A
B
G
D
C
H
E F
A
C
F
D GB HE A FC
2009-7-30 软件基础教案（第 7章 树和二叉树）
中序遍历算法若二叉树为空，遍历结束。否则，
（ 1）中序遍历根结点的左子树；
（ 2）访问根结点；
（ 3）中序遍历根结点的右子树。
void inorder(treenode *bt)
{
if (bt==NULL) return;
if(bt->lchild!=NULL) inorder(bt->lchild);
printf(,%d”,bt->data);
if(bt->rchild!=NULL) inorder(bt->rchild);
}
2009-7-30 软件基础教案（第 7章 树和二叉树）
3,后序遍历（ LRD）
后序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（ 1）后序遍历左子树；
（ 2）后序遍历右子树 ;
（ 3）访问根结点。
左 右 根
2009-7-30 软件基础教案（第 7章 树和二叉树）
B
G
D
H
E
后（根）序遍历
A
B
G
D
C
H
E F
A
C
F
D HG BE F AC
2009-7-30 软件基础教案（第 7章 树和二叉树）
后序遍历算法若二叉树为空，遍历结束。否则，
（ 1）后序遍历根结点的左子树；
（ 2）后序遍历根结点的右子树；
（ 3）访问根结点。
void postorder(treenode *bt)
{
if (bt==NULL) return;
if(bt->lchild!=NULL) postorder(bt->lchild);
if(bt->rchild!=NULL) postorder(bt->rchild);
printf(,%d”,bt->data);
}
层序遍历二叉树算法的步骤是：
1.若二叉树为空，则空操作；
2.否则，根结点入队，如队列不空循环：
（ a）做出队操作，访问该结点；
（ b）若该结点的左、右孩子指针非空，将该结点的左右孩子入队；
最后，出队序列就是层序遍历序列从二叉树的第一层开始，从上至下、从左至右的顺序逐点访问。
A
B
G
D
C
H
E F
如何实现？
采用顺序队列实现
Afrontrear
A
B C
B
D E
C
F
D E
G H
F G H
遍历结果
A B C D E F G H
4,层序遍历
2009-7-30 软件基础教案（第 7章 树和二叉树）
层序遍历算法若二叉树为空，遍历结束。否则，
（ 1）初始化设置一个队列；
（ 2）把根结点指针入队列；
（ 3）当队列非空时，循环执行步骤（ a） ~（ c）：
（ a）出队列取得一个指针结点，访问该结点；
（ b）若该结点的左子树非空，则将该结点的左子树指针入队列；
（ c） 若该结点的右子树非空，则将该结点的右子树指针入队列；
（ 4）结束
2009-7-30 软件基础教案（第 7章 树和二叉树）
表达式语法树
- + / a * e f b - c d
例 (练习 )：
前序遍历结果：
中序遍历结果：
后序遍历结果：
层序遍历结果：
a + b * c - d - e / f
a b c d - * + e f / -
- + a * b - c d / e f
二,遍历算法的应用：
2009-7-30 软件基础教案（第 7章 树和二叉树）
三、定理：一棵二叉树的前序序列和中序序列可以唯一的确定这棵二叉树。（证明略）
假定：前序序列为和中序序列分别为：
{a1,…,am} 和 {b1,…,bm}
若中序序列中与前序序列 a1相同的元素为 bj。
A,j =1时,二叉树无左子树，由 {a2,…,am} 和
{b2,…,bm} 可以唯一的确定二叉树的右子树；
B,j= m时,二叉树无右子树，由 {a2,…,am} 和
{b1,…,bm-1} 可以唯一的确定二叉树的左子树；
2009-7-30 软件基础教案（第 7章 树和二叉树）
C,2<=j<=m-1,则子序列 {a2,…,aj} 和 {b1,…
,bj-1}唯一的确定二叉树的左子树；子序列 {aj+1，
…,am} 和 {bj+1,…,bm}唯一的确定二叉树的右子树各左、右子树进行如上操作。
2009-7-30 软件基础教案（第 7章 树和二叉树）
{a1,a2,…,aj,aj+1,…,am}
{b1,…,bj-1,bj,bj+1,…,bm }
唯一的确定左子树 唯一的确定右子树个数相同若 a1 = bj
前序中序
2009-7-30 软件基础教案（第 7章 树和二叉树）
四、定理：一棵二叉树的后序序列和中序序列可以唯一的确定这棵二叉树。（证明略）
假定：后序序列为和中序序列分别为：
{a1,…,am} 和 {b1,…,bm}
若中序序列中与后序序列 am相同的元素为 bj。
A,j =1时,二叉树无左子树，由 {a1,…,am-1} 和
{b2,…,bm} 可以唯一的确定二叉树的右子树；
B,j= m时,二叉树无右子树，由 {a1,…,am-1} 和
{b1,…,bm-1} 可以唯一的确定二叉树的左子树；
2009-7-30 软件基础教案（第 7章 树和二叉树）
{a1,a2,…,aj,aj+1,…,am}
{b1,…,bj-1,bj,bj+1,…,bm }
唯一的确定左子树 唯一的确定右子树个数相同若 am = bj
后序中序
2009-7-30 软件基础教案（第 7章 树和二叉树）
例：前序序列 { ABHFDECKG } 和中序序列
{ HBDFAEKCG },构造二叉树过程如下：
2009-7-30 软件基础教案（第 7章 树和二叉树）
如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。
前序序列,1,2,3,4,5,6,7,8,9
中序序列 a,3,2,5,4,1,6,8,7,9
中序序列 b,4,3,5,2,1,7,6,8,9
bitree *findnode(bitree *bt,elemtype x)
{bitree *p;
if ( bt == NULL) return NULL;
if ( bt->data == x) return bt;
if ( bt->Lchild != NULL)
{p=findnode(bt->Lchild,x);
if(p!=NULL) return p;
}
if ( bt->Rchild != NULL)
{p=findnode(bt->Rchild,x);
if(p!=NULL) return p;
}
return NULL;
}
例：在二叉树中查找具有给定值的结点查找成功空树在左子树中查找在右子树中查找查找不成功
2009-7-30 软件基础教案（第 7章 树和二叉树）
int count;(全局变量 )
int countleaf(bitree *p)
{
if (p!= NULL)
{
if(p->Lchild==NULL && p->Rchild==NULL)
count++;
else
{
countleaf(p->lchild);
countleaf(p->rchild);
}
}
}
例：求二叉树中叶子结点的个数
2009-7-30 软件基础教案（第 7章 树和二叉树）
7.5 二叉树的应用
7.5.2二叉排序树,
特殊结构的二叉树,也称为树表,用于排序和检索。
二叉树的应用十分广泛,下面介绍几种应用例子,
7.5.1哈夫曼树,(最优树 )
是一种带权路径最短的树,用于信息检索、
判定树、哈夫曼编码等。
最优树，又称哈夫曼树（ Huffman Tree）是一类 带权路径长度 最短的树，本节仅限于讨论最优二叉树。
首先介绍 路径 和 路径长度 的概念 ——
由从树的根结点到其余结点的分支构成一条 路径,
路径上的分支数目称 路径长度 。
一般情况下,树的路径长度 指的是从树根到树中每个叶子结点的路径长度之和。
7.5.1哈夫曼树（ Huffman Tree）
一、基本概念
2009-7-30 软件基础教案（第 7章 树和二叉树）
结点的带权路径长度 则定义为从树根到该结点之间的路径长度与该结点上所带权值的乘积。假设树上有 n 个叶子结点，且每个叶子结点上带有权值为 Wk(k=1,2,…,n),则 树的带权路径长度 定义为树中所有叶子结点的带权路径长度之和，通常记其中 lk 为带权 Wk 的叶子结点的带权路径长度。
例如，图中的四棵二叉树，都有 5个叶子结点且带相同权值 5,6,2,9,7，它们的带权路径长度分别为
WPL = 7*3 + 9*3 + 5*2 + 6*2 + 2*2 = 74
(左上图 )
WPL = 2*1 + 6*3 + 7*4 + 9*4 + 5*2 = 94
(右上图 )
WPL = 6*2 + 7*2 + 5*3 + 2*3 + 9*2 = 65
(左下图 )
WPL = 2*1 + 5*3 + 7*3 + 9*3 + 6*3 = 83
(右下图 )
其中以左下图中二叉树的 带权路径长度 为最小。
2009-7-30 软件基础教案（第 7章 树和二叉树）
假设有 n 个权值 { W1,W2,… Wn},试构造一棵有 n 个叶子结点的二叉树，每个叶子结点带权为 Wi。显然，这样的二叉树可以构造出多棵，其中必存在一棵带权路径长度 WPL 取最小的二叉树，
称该二叉树为 最优二叉树 。
可以验证，左下图中二叉树恰为最优二叉树，即在所有叶子结点带权为 5,6,2,9,7的二叉树中，带权路径长度的最小值为 65。
2009-7-30 软件基础教案（第 7章 树和二叉树）
二、最优树的构造方法哈夫曼最早给出了一个构造最优树的带有一般规律的算法，俗称哈夫曼算法。现以最优二叉树为例叙述如下：
(1) 根据给定的 n 个权值 { w1,w2,…wn},构成 n 棵二叉树的集合 F={ T1,T2,…,Tn},其中每棵二叉树 Ti中只有一个带权为 Wi的根结点，其左右子树均空。
(2) 在 F 中选取两棵根结点的权值最小和次小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
(3) 在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。
(4)重复 (2)和 (3)，直到 F 只含一棵树为止。这棵树便是所求的哈夫曼树。
2009-7-30 软件基础教案（第 7章 树和二叉树）
三、最优前缀编码哈夫曼二叉树在通讯编码中的一个应用是利用它构造一组最优前缀编码。在某些通讯场合，需将传送的文字转换成由二进制字符组成的字符串。
通常有两类二进制编码：
一类为 等长编码 ——
这类编码的二进制串的长度取决于电文中不同的字符个数。
另一类是 不等长编码 ——
即各个字符的编码长度不等。
2009-7-30 软件基础教案（第 7章 树和二叉树）
不等长编码的好处是,可以使传送电文的字符串的总长度尽可能地短 。因为通常各个字符在电文中出现的次数是不相同的，
若对出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。但在实用的不等长编码中,任意一个字符的编码都不能是另一个字符的编码的前缀,这种编码称为 前缀编码 。
2009-7-30 软件基础教案（第 7章 树和二叉树）
例：假设电文总只有 5个字符，且在电文中出现的频率分别为：
5/29,6/29,2/29,9/29,7/29。则所构造的最优前缀编码如右图所示。
2009-7-30 软件基础教案（第 7章 树和二叉树）
18 4534 7951 86
51
34 79
18 45 86
18 4534 7951 86
7.5.2 二叉排序树的生成
2009-7-30 软件基础教案（第 7章 树和二叉树）
一,二叉排序树的定义,
或是空树,或具有以下性质的二叉树,
① 其左子树上所有结点的数据均 小于 根结点的数据值,
② 其右子树上所有结点的数据均 大于或等于根结点的数据值,
③ 左、右子树又各是一棵二叉排序树。
例：
⒉
⒏
⒑
⒒
⒒
⒖
⒗
⒙
⒛
二、二叉排序树的生成生成一棵二叉排序树,过程如下,
① 若二叉排序树为空，则令待插结点为根结点,
② 若二叉排序树非空，则比较待插结点 (k1)和根结点 (k2)的数据值。若 k1<k2,则将其插入到左子树中；否则，将其插入到右子树中,
③ 结点插入二叉排序树的左、右子树过程同上,
例,将序列 {15,10,18,2,11,8,16,25,11}构成一棵二叉排序树,
过程,15
10 18
2 11
8
16 25
11
三、二叉排序树生成算法描述
#define N 10
nodetype *creat_bstree(elemtype a[])
{
int i;
nodetype *bt,*s,*p,*q;
bt=NULL;
for (i=0;i<N;i++)
{
s=(nodetype*)malloc(sizeof(nodetype));
s->data=a[i];
s->lchild=NULL;
s->rchild=NULL;
申请一个新的结点空树的情况寻找合适的插入位置
if (bt==NULL)
bt=s;
else
{
p=bt;
while(p!=NULL)
{
q=p;
if (s->data<p->data)
p=p->lchild;
else
p=p->rchild;
}
2009-7-30 软件基础教案（第 7章 树和二叉树）
if (s->data<q->data)
q->lchild=s;
else
q->rchild=s;
}
}
return bt;
}
插入
2009-7-30 软件基础教案（第 7章 树和二叉树）
① 插入的新结点都是二叉排序树的叶子结点,不必移动其它结点,
② 对二叉排序树采用中序遍历,其结果为一有序序列,
③ 根结点的选择,决定二叉树的形状,其形状决定检索的效率,根结点数据值最好选择元素序列的中间值,
特点,
2009-7-30 软件基础教案（第 7章 树和二叉树）
（ 1）树中所有相同双亲结点的兄弟结点之间加一条连线。
（ 2）对树中不是双亲结点第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删去该结点与双亲之间的连线。
（ 3）整理所有保留的和添加的连线，使每一个结点的第一个孩子结点连线位于左孩子指针位置，使每个结点的右兄弟结点连线位于右孩子的指针位置。
7.6 树、森林与二叉树的转换一、树转换为二叉树
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B
G
DC
E F
A
B
G
DC
E F
A
B
G
D
C
E
F
连线、
抹线 旋转
2009-7-30 软件基础教案（第 7章 树和二叉树）
请作练习：
A
B
H
C
ED F G A
B
H
C
E
D
F
G
树转换为二叉树
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B
H
D
E
C
F G
A
B
H
CE
F
G
D
树转换为二叉树
2009-7-30 软件基础教案（第 7章 树和二叉树）
G
H
A
B
F
C
ED
L
I
KJ
二、森林转换为二叉树
2009-7-30 软件基础教案（第 7章 树和二叉树）
（ 1）若某结点是其双亲结点的左孩子，则把该结点的右孩子，
右孩子的右孩子,…… 都与该结点的双亲结点用线连起来。
（ 2）删除原二叉树中所有双亲结点与右孩子结点的连线。
（ 3）整理所有保留的和添加的连线，使每个结点的所有孩子结点位于相同层次高度。
三、二叉树转换为树
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B
G
DC
E F
A
B
G
D
CE
F
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B
G
DC
E F
A
B D
E F G
C
A EB CF D G
7.7 树的遍历一、先（根）序遍历树的先根遍历序列一定与该树的二叉树的前序遍历序列相同。
2009-7-30 软件基础教案（第 7章 树和二叉树）
二、后（根）序遍历
A
B D
E F G
C
E BF GC D A
A
B
G
DC
E F
树的后根遍历序列一定与该树的二叉树的中序遍历序列相同。
2009-7-30 软件基础教案（第 7章 树和二叉树）
总 结
1.概念,树,树的度,结点的度,树的层次,结点的层次,叶子,
孩子,双亲,兄弟,有序树,二叉树,满二叉树,完全二叉树,
平衡二叉树,二叉排序树。
2.树和二叉树的存储。
3.树的遍历：前序，后序。
二叉树的遍历算法,前序，中序，后序，层序。
计算叶子结点，深度，查找算法。
4.树和森林与二叉树的转换。
5.树和二叉树的应用：哈夫曼树、二叉排序树的生成。
2009-7-30 软件基础教案（第 7章 树和二叉树）
作业,
P195 7-2,7-3,7-14
P195 7-4,7-13
P195 7-7（理解）,7-8（理解）,7-10，
7-11,7-12,7-16
树二叉树二叉树的设计和实现二叉树的遍历二叉树的应用（哈夫曼编码和二叉排序树）
树、森林与二叉树的转换树的遍历第七章 树和二叉树
Chapter 7 Tree and Binary Tree
2009-7-30 软件基础教案（第 7章 树和二叉树）
7.1树的概念树是由 n (n? 0)个结点组成的有限集合。如果 n = 0，
称为空树；如果 n > 0，则
有一个特定的称之为 根
(root)的结点，它只有直接后继，但没有直接前驱；
b
a
c
g hd e f
i j
1.树的定义
2009-7-30 软件基础教案（第 7章 树和二叉树）
除根以外的其它结点划分为 m (m? 0)个互不相交的有限集合 T0,T1,…,Tm-1，每个集合又是一棵树，
并且称之为根的 子树 (SubTree)。
每棵子树的根结点有且仅有一个直接前驱，但可以有 0个或多个直接后继。
b
a
c
g hd e f
i j
2009-7-30 软件基础教案（第 7章 树和二叉树）
特点：
除根结点之外的所有结点有且只有一个前驱结点，根结点没有前驱结点
树中所有结点可以有零个或多个后继结点
b
a
c
g hd e f
b
a
c
g hd e
f
非树结构树结构描述的是 层次关系
2009-7-30 软件基础教案（第 7章 树和二叉树）
直观表示法 b
a
c
g hd e f
i j
2.树的表示
2009-7-30 软件基础教案（第 7章 树和二叉树）
形式化表示法
T=(D,R)
D:D=?; 空树 R={<Root,ri>,i=1,2,…m }
D;D={Root}? DF ri:是 Root子树的根结点
Root:树的根结点
DF,树的根结点 Root的子树集合
DF= D1? D2? D3 ….,? Dm 并且 Di?Dj=?
(i? j; i=1,2,…m ; j=1,2,…m )
2009-7-30 软件基础教案（第 7章 树和二叉树）
凹入表示
a
b
d
e
i
j
f
c
g
h
----主要用于树的屏幕和打印机显示。
2009-7-30 软件基础教案（第 7章 树和二叉树）
i jd f g h
ab ce
a ( b ( d,e ( i,j ),c ( g,h ) ) )
嵌套集合表示
嵌套括号表示二、树的基本术语
（ 1） 结点,由数据元素和构造数据元素之间关系的指针组成,
（ 2） 结点的度,结点所拥有的子树的个数。
（ 3） 叶子结点,度为 0的结点。
（ 4） 分枝结点,度不为 0的结点。
（ 5） 树的度,树中各结点度的最大值称为该树的度。
（ 6） 孩子、兄弟、双亲,树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它的孩子结点的双亲。具有同一个双亲的孩子结点互为兄弟。
（ 7） 结点的层次,规定树的根结点的层次为 0，其余结点的层次等于它的双亲结点的层次加 1。
（ 8） 树的深度,树中所有结点的最大层次称为树的深度。
（ 9） 有序树和无序树,如果一棵树中结点的各子树从左到右是有次序的，即若交换某结点各子树的相对位置则构成不同的树，称这棵树为有序树；否则为无序树。
（ 10） 森林,零棵或有限棵不相交的树的集合称为森林。
A
DCB
E F G H I
三、树的基本操作
1、初始化
2、求指定结点所在树的根结点
3、求指定结点的双亲结点
4、求指定结点的某一孩子结点
5、求指定结点的最右边兄弟结点
6、将一棵树插入到另一树的指定结点下作为它的子树
7、删除指定结点的某一子树
8、树的遍历遍历：按某种方式访问树中的每个结点，且每个结点只被访问一次。
2009-7-30 软件基础教案（第 7章 树和二叉树）
四、树的存储结构
双亲表示法
孩子表示法
孩子兄弟表示法
双亲孩子表示法多种存储形式，两大类,顺序存储；
链接存储；
2009-7-30 软件基础教案（第 7章 树和二叉树）
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
序号 data parent1.双亲表示法 （顺序存储）
2009-7-30 软件基础教案（第 7章 树和二叉树）
#define MAXNODE 32
typedef struct
{ datatype data; \\ 数据域
int parent; \\ 双亲域
} ptree;
ptree t[MAXNODE];
双亲表示法－－ c语言描述特点：难于实现寻找一个结点的孩子结点的操作便于实现寻找一个结点的双亲结点的操作
2009-7-30 软件基础教案（第 7章 树和二叉树）
改进：
增加两个域：存储该结点的第一个孩子结点，在数组中的序号。
存储该结点的第一个右兄弟结点在数组中的序号。
typedef struct
{ datatype data; \\ 数据域
int parent; \\ 双亲域
int son; \\孩子结点
int next; \\兄弟结点
} ptree;
2009-7-30 软件基础教案（第 7章 树和二叉树）
2.孩子表示法 A
B C D
E F G H I J
A
B ∧ C ∧ ∧ D
E∧ ∧ ∧ F∧ ∧ ∧ G∧ ∧ ∧ H∧ ∧ ∧ I ∧ ∧ ∧ J∧ ∧ ∧
两种方法：
结点的指针域的个数 =树的度。 同构型
结点的指针域的个数 =结点的度 异构型同构型
（多重链表法）
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B C D
E F G H I J
异构型
2009-7-30 软件基础教案（第 7章 树和二叉树）
typedef struct TreeNode
{ int data;
struct TreeNdoe *Son[MAXSON];
} nodetype;
孩子表示法－－ c语言描述 (同构型 )
特点：便于实现寻找一个结点的孩子结点的操作难于实现寻找一个结点的双亲结点的操作
A
B C D
E F G H I J
序号 data parent
将双亲表示与孩子表示结合起来
3、双亲孩子表示法
J 3
A -1
B 0
C 0
D 0
E 1
F 1
G 2
H 3
I 3
1 2 3
7 8 9
4 5
6
0
1
2
3
4
5
6
7
8
9
∧
∧
∧
∧
∧
∧
∧
∧
∧
typedef struct cnode
{ int child; \\ 孩子结点序号
struct cnode *next; \\ 下一个孩子结点
} link;
结点
data parent headptr child next
T[]
孩子链表双亲－－孩子链表表示法
typedef struct
{ datatype data;
int parent;
link *headptr;
} ctree;
ctree T[MAXNODE];
结构体数组
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B
C
E D
F
G
4、孩子兄弟表示法（二重链表法）
B D
A
C
E F
G
左孩子 -右兄弟表示法树的左孩子 -右兄弟表示
data firstChild nextSibling
2009-7-30 软件基础教案（第 7章 树和二叉树）
孩子兄弟表示 —C语言描述
typedef struct TreeNode
{ elemtype data;
struct TreeNode *son;
struct TreeNode *next
} nodetype;
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B
G
D
C
H
E F 二叉树
7.2 二叉树
（ 1）定义,一棵二叉树是结点的一个有限集合。
该集合或者为空
或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
1.二叉树的定义
2009-7-30 软件基础教案（第 7章 树和二叉树）
(2) 二叉树的特点：
度小于等于 2
有序树
(3) 二叉树的五种基本形态左子树 右子树 右子树左子树
(a) (b) (c) (d) (e)
2009-7-30 软件基础教案（第 7章 树和二叉树）
(1) 满二叉树 (Full Binary Tree)
一棵深度为 h且有 2h-1个结点的二叉树。
对树中结点按从上到下、从左到右的顺序进行编号。
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
a
b
d
c
e f
h i j
g
k l m n o
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
2.特殊二叉树若二叉树的深度为 h，且共有 n个结点。对树中结点 按从上到下、从左到右的顺序进行编号，若编号为 i(1≤i≤n)的结点与满二叉树编号为 i的结点位置相同，则此树称为完全二叉树。
除第 h层外，其它各层
(1?h-1)的结点数都达到最大个数，第 h层从右向左连续缺若干结点，这就是完全二叉树。
1
2 3
4 5 6 7
8 9 10 11 12
(2) 完全二叉树 (Complete Binary Tree)
2009-7-30 软件基础教案（第 7章 树和二叉树）
显然，一棵满二叉树一定是一棵完全二叉树
1
2 3
4 5 6 7
8 9 10 11
2 3
4 5 6
7 8 9
1
非完全二叉树 非完全二叉树
(3) 平衡二叉树
A
C
E F
B
D
–平衡因子：二叉树任意结点的左子树深度减去右子树深度的差值，为此结点的平衡因子。
–平衡二叉树：二叉树中每个结点的平衡因子的绝对值都不大于 1，则称这棵二叉树为平衡二叉树,
2 3
4 5
69
1
平衡二叉树 非平衡二叉树
2009-7-30 软件基础教案（第 7章 树和二叉树）
1、创建二叉树
2、撤消二叉树
3、左插入结点
4、右插入结点
5、左删除子树
6、右删除子树
7、遍历二叉树
8、其他,左插入子树,右插入子树,左删除结点,
右删除结点等
3,二叉树 的 基本操作
2009-7-30 软件基础教案（第 7章 树和二叉树）
4,二叉树的性质性质 1 若二叉树的层次从 0开始,则在二叉树的第 i 层最多有 2i个结点。 (i? 0)
证明,i = 0 时，有 2i = 20 =1，成立假定,i = k 时性质成立；即有 2k个结点,
当 i = k+1 时，第 k+1的结点至多是第 k层结点的两倍，即总的结点个数至多为 2× 2k = 2k+1
故命题成立
2009-7-30 软件基础教案（第 7章 树和二叉树）
性质 2 若规定空树的深度为 -1，则深度为 k的二叉树最多有 2k+1-1个结点。 (k? -1)
证明：当深度为 -1时，是空二叉树，为没有结点，
有 2-1+1-1=0，结论成立；
仅当每一层都含有最大结点数时，二叉树的结点数最多，利用性质 1可得二叉树的结点数至多为：
20 + 21 + 22 + 23 + … + 2k = 2k+1 － 1
2009-7-30 软件基础教案（第 7章 树和二叉树）
性质 3 对任何一棵二叉树,如果其叶结点个数为
n0,度为 2的非叶结点个数为 n2,则有
n0＝ n2＋ 1
证明：
1、结点总数为度为 0的结点加上度为 1的结点再加上度为 2的结点,n = n0 + n1 + n2
2、另一方面，二叉树中一度结点有一个孩子，二 度结点有二个孩子，根结点不是任何结点的孩子，因此，
结点总数为,n = n1 + 2n2 + 1
3、两式相减，得到：
n0 = n2 + 1
2009-7-30 软件基础教案（第 7章 树和二叉树）
1
2 3
4 5 6 7
8 9 10 11
5,6为度为 1的结点：也就是 n1=2
1,2,3,4为度为 2的结点：也就是 n2=4
10,11可以分别用 5,6表示，故他们的和为 n1；
8,9用 4表示,6,7用 3表示,4,5用 2表示,2,3用 1表示故 2~9的个数和为 2n2；
结点 1没有表示，但他只有一个，所以总的个数为 n1+2n2+1
2009-7-30 软件基础教案（第 7章 树和二叉树）
性质 4具有 n个结点的完全二叉树的深度为? log2（ n+1)? -1 (“,表示上取整 )
证明：设完全二叉树的深度为 h，则有
2h - 1 < n? 2h+1 - 1
2h< n+1 <= 2h+1
取对数
h< log2(n+1) <= h+1
1
2 3
4 5 6 7
8 9 10 11 12
性质 5具有 n个结点的 满 二叉树,h=log2(n+1)-1从第一层开始,自上而下逐层从左到右给每个结点从 1开始编号,对序号为 j的结点，规律有,
① 若 j≤2 h-1,结点 j的左孩子结点编号为 2*j,右孩子结点编号为 2*j+1;
② 若 j>1,则结点 j的双亲结点的编号为?j/2?(下取整 ).
可见可对其采用 顺序存贮结构,
例,h=log2(n+1)-1=3 2h-1=7
j=3,左孩子结点编号,2*3=6
右孩子结点编号,2*3+1=7
j=5，双亲结点编号,?j/2?
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
2009-7-30 软件基础教案（第 7章 树和二叉树）
性质 6 如果将一棵有 n个结点的 完全二叉树 自顶向下，同一层自左向右连续给结点编号 1,2,…,n-1,n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中,(1
i? n)。则有以下关系：
若 i == 1,则 i 无双亲
若 i > 1,则 i 的双亲为?i /2?
若 2*i <= n,则 i 的左孩子为 2*i； 否则 (2*i > n),i没有左孩子，必定是叶子结点，二叉树中 i>? n/2? 的结点必定是叶结点
1
2
4
3
5 6
8 9 10
7
11 12 13 14 15
16 17
若 2*i+1 <= n,则 i 的右孩子为 2*i+1，否则,i无右孩子
若 i(不为 1)为奇数,且 i<n，则其左兄弟为 i-1，否则无左兄弟；
若 i 为偶数,且小于 n,则其右兄弟为 i+1，否则无右兄弟
i 所在层次为?log2 (i)?
例,i=5,2*i<n,
左孩子,10，右孩子,11
左兄弟,4,右兄弟,6
i=8
i=9
2009-7-30 软件基础教案（第 7章 树和二叉树）
1,顺序存储结构
A
C
GF
B
D E
H I J
0 1 2 3 4 5 6 7 8 9
A B C D E F G H I J
7.3 二叉树的设计和实现
7.3.1二叉树的存储结构
Bt
2009-7-30 软件基础教案（第 7章 树和二叉树）
顺序存储结构
A
CB
G H
D E F
0 1 2 3 4 5 6 7 8 9 10 11 12 13
A B C D E F G HBt
2009-7-30 软件基础教案（第 7章 树和二叉树）
单支树由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。
31
12
17
88
49
31 12 17 88
49
2009-7-30 软件基础教案（第 7章 树和二叉树）
#define MAXNODE <二叉树中结点最大个数 >
Typedef int elemtype;
elemtype bt[MAXNODE];
顺序二叉树结点的 c语言描述
2009-7-30 软件基础教案（第 7章 树和二叉树）
链式存储结构形象化描述 (不带头结点 )
A
B
G
D
C
H
E F
^B
^ D
^ ^G
C
^F^ ^E
^ ^H
A
bt
2,链式存储结构
2009-7-30 软件基础教案（第 7章 树和二叉树）
链式存储结构形象化描述 (带头结点 )
A
B
G
D
C
H
E F
^B
^ D
^ ^G
C
^F^ ^E
^ ^H
A
bt
头结点根结点
2009-7-30 软件基础教案（第 7章 树和二叉树）
左孩子
Lchild
数据
Data
右孩子
Rchild
结点结构
BTreeNode
链式存储结构的 c语言描述
typedef int elemtype;
typedef struct node
{ elemtype data;
struct node *lchild,*rchild;
} bitree;
2009-7-30 软件基础教案（第 7章 树和二叉树）
7.3.2二叉树的操作实现
1001
bt
1.二叉树的初始化
*bt
1001 头结点 **bt
125A
NULL NULL
125A
2009-7-30 软件基础教案（第 7章 树和二叉树）
初始化算法
int Initiate(bitree **bt)
{ if((*bt=(bitree*)malloc(sizeof(bitree)))==NULL)
return 0;
(*bt)->Lchild=NULL;
(*bt)->Rchild=NULL;
return 1;
}
2009-7-30 软件基础教案（第 7章 树和二叉树）
2.二叉树的创建
1001
bt *bt
1001 头结点 **bt
125A
1A05 NULL
125A
X
根结点
1A05
NULL NULL
1.创建一个只有根节点的二叉树
2009-7-30 软件基础教案（第 7章 树和二叉树）
int Initiate(bitree *bt)
{bitree* p;
if((p=(bitree*)malloc(sizeof(bitree)))==NULL)
return 0;
p-> data=x;
p->Lchild=NULL;
p->Rchild=NULL;
bt->Lchild=p;
return 1;
}
2009-7-30 软件基础教案（第 7章 树和二叉树）
x
^B
^ D
^ ^G
117C
C
^F^ ^E
^ ^H
1006
147E
p
117C 1006
从这一过程可以看出，二叉树的建立过程，就是对结点的一一插入。所以我们可以通过插入算法来建立树。
2009-7-30 软件基础教案（第 7章 树和二叉树）
3.二叉树的插入
A
B
G
D
C
H
E F
parent
x
将结点 x插入到结点 parent的左孩子处
A
B
G
D
C
H
E F
parent
G
D
x
2009-7-30 软件基础教案（第 7章 树和二叉树）
147E
p
x
C
^F^ ^E
^ ^H
A
bt
^ ^B
*Parent
NULLNULL
147E
2009-7-30 软件基础教案（第 7章 树和二叉树）
bt
C
^F
^ ^D ^ ^H
A
^ ^B
*Parent
^ ^E
132B147E
p
x NULLNULL132B
147E
Bitree *InsertL(elemtype x,bitree *parent)
{ bitree *p;
if(parent==NULL)
{printf(“/n插入出错,);
return NULL;}
if((p=(bitree*)malloc(sizeof(bitree)))==NULL)
return NULL;
p->data=x;
p->Lchild=NULL;
p->Rchild=NULL;
if(parent->Lchild==NULL) parent->Lchild=p;
else { p->Lchild=parent->Lchild;
parent->Lchild=p;}
return p;
}
判 parent
是否存在申请新结点
xNULL NULL
Parent无左孩子时
Parent有左孩子时二叉树插入算法将结点 x插入到结点 parent的右孩子处原理同上。自学
2009-7-30 软件基础教案（第 7章 树和二叉树）
删除二叉树 bt中结点 parent的左子树
A
B
G
D
C
H
E F
parent
A
B
G
D
C
H
E F
parent
4.二叉树的删除
2009-7-30 软件基础教案（第 7章 树和二叉树）
bt
C
^FD
^ ^H
A
^ ^B
*Parent
^ ^E
132B
^ ^G^ ^I
p
NULL
132B
2009-7-30 软件基础教案（第 7章 树和二叉树）
Bitree *DeleteL(bitree *bt,bitree *parent)
{ bitree *p;
if(parent==NULL || parent->Lchild==NULL )
{printf(“/n出错,);
return NULL;
}
p= parent->Lchild ;
parent->Lchild=NULL;
free(p);
return bt;
}
删除二叉树 bt中结点 parent的右子树，原理同上，自学删除算法
Parent无左孩子时释放结点判 parent是否存在和它的左子树是否存在
2009-7-30 软件基础教案（第 7章 树和二叉树）
Destroy(bitree* bt)
{
if(bt-> Lchild!=NULL)
Destroy(bt-> Lchild);
if(bt-> Rchild!=NULL)
Destroy(bt-> Rchild);
free(bt);
}
一、二叉树的遍历二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且只被访问一次。
7.4 二叉树的遍历由二叉树的 递归 定义，二叉树的三个基本组成单元是,根结点、左子树 和 右子树 。
根
{左子树 } {右子树 }
Preorder（先序）
Inorder（中序）
Postorder（后序）
2009-7-30 软件基础教案（第 7章 树和二叉树）
前序遍历二叉树的 操作定义 为：
若二叉树为空，则空操作；否则
（ 1）访问根结点；
（ 2）前序遍历左子树；
（ 3）前序遍历右子树。
根 左 右
1,前（先）序遍历（ DLR）
2009-7-30 软件基础教案（第 7章 树和二叉树）
C
F
B
G
D
H
E
A
B
G
D
C
H
E F
A
A DB GE H FC
前（根）序遍历
2009-7-30 软件基础教案（第 7章 树和二叉树）
前序遍历算法若二叉树为空，遍历结束。否则，
（ 1）访问根结点；
（ 2）前序遍历根结点的左子树；
（ 3）前序遍历根结点的右子树。
void preorder(treenode *bt)
{
if (bt==NULL) return;
printf(,%d”,bt->data);
if(bt->lchild!=NULL) preorder(bt->lchild);
if(bt->rchild!=NULL) preorder(bt->rchild);
}
2009-7-30 软件基础教案（第 7章 树和二叉树）
2,中序遍历（ LDR）
中序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（ 1）中序遍历左子树；
（ 2）访问根结点；
（ 3）中序遍历右子树。
左 根 右
2009-7-30 软件基础教案（第 7章 树和二叉树）
中（根）序遍历
B
G
D
H
E
A
B
G
D
C
H
E F
A
C
F
D GB HE A FC
2009-7-30 软件基础教案（第 7章 树和二叉树）
中序遍历算法若二叉树为空，遍历结束。否则，
（ 1）中序遍历根结点的左子树；
（ 2）访问根结点；
（ 3）中序遍历根结点的右子树。
void inorder(treenode *bt)
{
if (bt==NULL) return;
if(bt->lchild!=NULL) inorder(bt->lchild);
printf(,%d”,bt->data);
if(bt->rchild!=NULL) inorder(bt->rchild);
}
2009-7-30 软件基础教案（第 7章 树和二叉树）
3,后序遍历（ LRD）
后序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（ 1）后序遍历左子树；
（ 2）后序遍历右子树 ;
（ 3）访问根结点。
左 右 根
2009-7-30 软件基础教案（第 7章 树和二叉树）
B
G
D
H
E
后（根）序遍历
A
B
G
D
C
H
E F
A
C
F
D HG BE F AC
2009-7-30 软件基础教案（第 7章 树和二叉树）
后序遍历算法若二叉树为空，遍历结束。否则，
（ 1）后序遍历根结点的左子树；
（ 2）后序遍历根结点的右子树；
（ 3）访问根结点。
void postorder(treenode *bt)
{
if (bt==NULL) return;
if(bt->lchild!=NULL) postorder(bt->lchild);
if(bt->rchild!=NULL) postorder(bt->rchild);
printf(,%d”,bt->data);
}
层序遍历二叉树算法的步骤是：
1.若二叉树为空，则空操作；
2.否则，根结点入队，如队列不空循环：
（ a）做出队操作，访问该结点；
（ b）若该结点的左、右孩子指针非空，将该结点的左右孩子入队；
最后，出队序列就是层序遍历序列从二叉树的第一层开始，从上至下、从左至右的顺序逐点访问。
A
B
G
D
C
H
E F
如何实现？
采用顺序队列实现
Afrontrear
A
B C
B
D E
C
F
D E
G H
F G H
遍历结果
A B C D E F G H
4,层序遍历
2009-7-30 软件基础教案（第 7章 树和二叉树）
层序遍历算法若二叉树为空，遍历结束。否则，
（ 1）初始化设置一个队列；
（ 2）把根结点指针入队列；
（ 3）当队列非空时，循环执行步骤（ a） ~（ c）：
（ a）出队列取得一个指针结点，访问该结点；
（ b）若该结点的左子树非空，则将该结点的左子树指针入队列；
（ c） 若该结点的右子树非空，则将该结点的右子树指针入队列；
（ 4）结束
2009-7-30 软件基础教案（第 7章 树和二叉树）
表达式语法树
- + / a * e f b - c d
例 (练习 )：
前序遍历结果：
中序遍历结果：
后序遍历结果：
层序遍历结果：
a + b * c - d - e / f
a b c d - * + e f / -
- + a * b - c d / e f
二,遍历算法的应用：
2009-7-30 软件基础教案（第 7章 树和二叉树）
三、定理：一棵二叉树的前序序列和中序序列可以唯一的确定这棵二叉树。（证明略）
假定：前序序列为和中序序列分别为：
{a1,…,am} 和 {b1,…,bm}
若中序序列中与前序序列 a1相同的元素为 bj。
A,j =1时,二叉树无左子树，由 {a2,…,am} 和
{b2,…,bm} 可以唯一的确定二叉树的右子树；
B,j= m时,二叉树无右子树，由 {a2,…,am} 和
{b1,…,bm-1} 可以唯一的确定二叉树的左子树；
2009-7-30 软件基础教案（第 7章 树和二叉树）
C,2<=j<=m-1,则子序列 {a2,…,aj} 和 {b1,…
,bj-1}唯一的确定二叉树的左子树；子序列 {aj+1，
…,am} 和 {bj+1,…,bm}唯一的确定二叉树的右子树各左、右子树进行如上操作。
2009-7-30 软件基础教案（第 7章 树和二叉树）
{a1,a2,…,aj,aj+1,…,am}
{b1,…,bj-1,bj,bj+1,…,bm }
唯一的确定左子树 唯一的确定右子树个数相同若 a1 = bj
前序中序
2009-7-30 软件基础教案（第 7章 树和二叉树）
四、定理：一棵二叉树的后序序列和中序序列可以唯一的确定这棵二叉树。（证明略）
假定：后序序列为和中序序列分别为：
{a1,…,am} 和 {b1,…,bm}
若中序序列中与后序序列 am相同的元素为 bj。
A,j =1时,二叉树无左子树，由 {a1,…,am-1} 和
{b2,…,bm} 可以唯一的确定二叉树的右子树；
B,j= m时,二叉树无右子树，由 {a1,…,am-1} 和
{b1,…,bm-1} 可以唯一的确定二叉树的左子树；
2009-7-30 软件基础教案（第 7章 树和二叉树）
{a1,a2,…,aj,aj+1,…,am}
{b1,…,bj-1,bj,bj+1,…,bm }
唯一的确定左子树 唯一的确定右子树个数相同若 am = bj
后序中序
2009-7-30 软件基础教案（第 7章 树和二叉树）
例：前序序列 { ABHFDECKG } 和中序序列
{ HBDFAEKCG },构造二叉树过程如下：
2009-7-30 软件基础教案（第 7章 树和二叉树）
如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。
前序序列,1,2,3,4,5,6,7,8,9
中序序列 a,3,2,5,4,1,6,8,7,9
中序序列 b,4,3,5,2,1,7,6,8,9
bitree *findnode(bitree *bt,elemtype x)
{bitree *p;
if ( bt == NULL) return NULL;
if ( bt->data == x) return bt;
if ( bt->Lchild != NULL)
{p=findnode(bt->Lchild,x);
if(p!=NULL) return p;
}
if ( bt->Rchild != NULL)
{p=findnode(bt->Rchild,x);
if(p!=NULL) return p;
}
return NULL;
}
例：在二叉树中查找具有给定值的结点查找成功空树在左子树中查找在右子树中查找查找不成功
2009-7-30 软件基础教案（第 7章 树和二叉树）
int count;(全局变量 )
int countleaf(bitree *p)
{
if (p!= NULL)
{
if(p->Lchild==NULL && p->Rchild==NULL)
count++;
else
{
countleaf(p->lchild);
countleaf(p->rchild);
}
}
}
例：求二叉树中叶子结点的个数
2009-7-30 软件基础教案（第 7章 树和二叉树）
7.5 二叉树的应用
7.5.2二叉排序树,
特殊结构的二叉树,也称为树表,用于排序和检索。
二叉树的应用十分广泛,下面介绍几种应用例子,
7.5.1哈夫曼树,(最优树 )
是一种带权路径最短的树,用于信息检索、
判定树、哈夫曼编码等。
最优树，又称哈夫曼树（ Huffman Tree）是一类 带权路径长度 最短的树，本节仅限于讨论最优二叉树。
首先介绍 路径 和 路径长度 的概念 ——
由从树的根结点到其余结点的分支构成一条 路径,
路径上的分支数目称 路径长度 。
一般情况下,树的路径长度 指的是从树根到树中每个叶子结点的路径长度之和。
7.5.1哈夫曼树（ Huffman Tree）
一、基本概念
2009-7-30 软件基础教案（第 7章 树和二叉树）
结点的带权路径长度 则定义为从树根到该结点之间的路径长度与该结点上所带权值的乘积。假设树上有 n 个叶子结点，且每个叶子结点上带有权值为 Wk(k=1,2,…,n),则 树的带权路径长度 定义为树中所有叶子结点的带权路径长度之和，通常记其中 lk 为带权 Wk 的叶子结点的带权路径长度。
例如，图中的四棵二叉树，都有 5个叶子结点且带相同权值 5,6,2,9,7，它们的带权路径长度分别为
WPL = 7*3 + 9*3 + 5*2 + 6*2 + 2*2 = 74
(左上图 )
WPL = 2*1 + 6*3 + 7*4 + 9*4 + 5*2 = 94
(右上图 )
WPL = 6*2 + 7*2 + 5*3 + 2*3 + 9*2 = 65
(左下图 )
WPL = 2*1 + 5*3 + 7*3 + 9*3 + 6*3 = 83
(右下图 )
其中以左下图中二叉树的 带权路径长度 为最小。
2009-7-30 软件基础教案（第 7章 树和二叉树）
假设有 n 个权值 { W1,W2,… Wn},试构造一棵有 n 个叶子结点的二叉树，每个叶子结点带权为 Wi。显然，这样的二叉树可以构造出多棵，其中必存在一棵带权路径长度 WPL 取最小的二叉树，
称该二叉树为 最优二叉树 。
可以验证，左下图中二叉树恰为最优二叉树，即在所有叶子结点带权为 5,6,2,9,7的二叉树中，带权路径长度的最小值为 65。
2009-7-30 软件基础教案（第 7章 树和二叉树）
二、最优树的构造方法哈夫曼最早给出了一个构造最优树的带有一般规律的算法，俗称哈夫曼算法。现以最优二叉树为例叙述如下：
(1) 根据给定的 n 个权值 { w1,w2,…wn},构成 n 棵二叉树的集合 F={ T1,T2,…,Tn},其中每棵二叉树 Ti中只有一个带权为 Wi的根结点，其左右子树均空。
(2) 在 F 中选取两棵根结点的权值最小和次小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
(3) 在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。
(4)重复 (2)和 (3)，直到 F 只含一棵树为止。这棵树便是所求的哈夫曼树。
2009-7-30 软件基础教案（第 7章 树和二叉树）
三、最优前缀编码哈夫曼二叉树在通讯编码中的一个应用是利用它构造一组最优前缀编码。在某些通讯场合，需将传送的文字转换成由二进制字符组成的字符串。
通常有两类二进制编码：
一类为 等长编码 ——
这类编码的二进制串的长度取决于电文中不同的字符个数。
另一类是 不等长编码 ——
即各个字符的编码长度不等。
2009-7-30 软件基础教案（第 7章 树和二叉树）
不等长编码的好处是,可以使传送电文的字符串的总长度尽可能地短 。因为通常各个字符在电文中出现的次数是不相同的，
若对出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。但在实用的不等长编码中,任意一个字符的编码都不能是另一个字符的编码的前缀,这种编码称为 前缀编码 。
2009-7-30 软件基础教案（第 7章 树和二叉树）
例：假设电文总只有 5个字符，且在电文中出现的频率分别为：
5/29,6/29,2/29,9/29,7/29。则所构造的最优前缀编码如右图所示。
2009-7-30 软件基础教案（第 7章 树和二叉树）
18 4534 7951 86
51
34 79
18 45 86
18 4534 7951 86
7.5.2 二叉排序树的生成
2009-7-30 软件基础教案（第 7章 树和二叉树）
一,二叉排序树的定义,
或是空树,或具有以下性质的二叉树,
① 其左子树上所有结点的数据均 小于 根结点的数据值,
② 其右子树上所有结点的数据均 大于或等于根结点的数据值,
③ 左、右子树又各是一棵二叉排序树。
例：
⒉
⒏
⒑
⒒
⒒
⒖
⒗
⒙
⒛
二、二叉排序树的生成生成一棵二叉排序树,过程如下,
① 若二叉排序树为空，则令待插结点为根结点,
② 若二叉排序树非空，则比较待插结点 (k1)和根结点 (k2)的数据值。若 k1<k2,则将其插入到左子树中；否则，将其插入到右子树中,
③ 结点插入二叉排序树的左、右子树过程同上,
例,将序列 {15,10,18,2,11,8,16,25,11}构成一棵二叉排序树,
过程,15
10 18
2 11
8
16 25
11
三、二叉排序树生成算法描述
#define N 10
nodetype *creat_bstree(elemtype a[])
{
int i;
nodetype *bt,*s,*p,*q;
bt=NULL;
for (i=0;i<N;i++)
{
s=(nodetype*)malloc(sizeof(nodetype));
s->data=a[i];
s->lchild=NULL;
s->rchild=NULL;
申请一个新的结点空树的情况寻找合适的插入位置
if (bt==NULL)
bt=s;
else
{
p=bt;
while(p!=NULL)
{
q=p;
if (s->data<p->data)
p=p->lchild;
else
p=p->rchild;
}
2009-7-30 软件基础教案（第 7章 树和二叉树）
if (s->data<q->data)
q->lchild=s;
else
q->rchild=s;
}
}
return bt;
}
插入
2009-7-30 软件基础教案（第 7章 树和二叉树）
① 插入的新结点都是二叉排序树的叶子结点,不必移动其它结点,
② 对二叉排序树采用中序遍历,其结果为一有序序列,
③ 根结点的选择,决定二叉树的形状,其形状决定检索的效率,根结点数据值最好选择元素序列的中间值,
特点,
2009-7-30 软件基础教案（第 7章 树和二叉树）
（ 1）树中所有相同双亲结点的兄弟结点之间加一条连线。
（ 2）对树中不是双亲结点第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删去该结点与双亲之间的连线。
（ 3）整理所有保留的和添加的连线，使每一个结点的第一个孩子结点连线位于左孩子指针位置，使每个结点的右兄弟结点连线位于右孩子的指针位置。
7.6 树、森林与二叉树的转换一、树转换为二叉树
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B
G
DC
E F
A
B
G
DC
E F
A
B
G
D
C
E
F
连线、
抹线 旋转
2009-7-30 软件基础教案（第 7章 树和二叉树）
请作练习：
A
B
H
C
ED F G A
B
H
C
E
D
F
G
树转换为二叉树
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B
H
D
E
C
F G
A
B
H
CE
F
G
D
树转换为二叉树
2009-7-30 软件基础教案（第 7章 树和二叉树）
G
H
A
B
F
C
ED
L
I
KJ
二、森林转换为二叉树
2009-7-30 软件基础教案（第 7章 树和二叉树）
（ 1）若某结点是其双亲结点的左孩子，则把该结点的右孩子，
右孩子的右孩子,…… 都与该结点的双亲结点用线连起来。
（ 2）删除原二叉树中所有双亲结点与右孩子结点的连线。
（ 3）整理所有保留的和添加的连线，使每个结点的所有孩子结点位于相同层次高度。
三、二叉树转换为树
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B
G
DC
E F
A
B
G
D
CE
F
2009-7-30 软件基础教案（第 7章 树和二叉树）
A
B
G
DC
E F
A
B D
E F G
C
A EB CF D G
7.7 树的遍历一、先（根）序遍历树的先根遍历序列一定与该树的二叉树的前序遍历序列相同。
2009-7-30 软件基础教案（第 7章 树和二叉树）
二、后（根）序遍历
A
B D
E F G
C
E BF GC D A
A
B
G
DC
E F
树的后根遍历序列一定与该树的二叉树的中序遍历序列相同。
2009-7-30 软件基础教案（第 7章 树和二叉树）
总 结
1.概念,树,树的度,结点的度,树的层次,结点的层次,叶子,
孩子,双亲,兄弟,有序树,二叉树,满二叉树,完全二叉树,
平衡二叉树,二叉排序树。
2.树和二叉树的存储。
3.树的遍历：前序，后序。
二叉树的遍历算法,前序，中序，后序，层序。
计算叶子结点，深度，查找算法。
4.树和森林与二叉树的转换。
5.树和二叉树的应用：哈夫曼树、二叉排序树的生成。
2009-7-30 软件基础教案（第 7章 树和二叉树）
作业,
P195 7-2,7-3,7-14
P195 7-4,7-13
P195 7-7（理解）,7-8（理解）,7-10，
7-11,7-12,7-16
