1.
5

第
5 
章树和二叉树

树形结构是一种常用的非线性结构,数据元素之间具有一对多的层

次关系,常用于描述各种具有层次关系的数据对象,例如行政组织结构、

文件目录等。本章主要讨论二叉树的存储结构、基本操作的实现及其

应用。

树的定义和基本操作

5.1.1 
树的定义和基本术语
1.树的定义
树(是n(n≥0)个结点的有限集。在任意一棵非空树中:
tre)

(1)有且只有一个称为根(ot)的结点。
ro

(2)除根之外的其余n-1个结点被分为m(m≥0)个互不相交的有
限集,其中每个集合本身又是一棵树,称为根结点的子树(subtre)。
可以看出,树的定义是递归的,即在树的定义中又用到了(_) 树的概念。
递归定义和递归操作在树和二叉树中的应用是比较广泛的,应注意领会递
归的实质。

2.树的表示法
树的表示法有树形表示法、文氏图表示法、广义表表示法和凹入表示
法,如图5.

1所示。

其中,树形表示法是最常用的表示方法。在用树形表示法表示的树

中,边的数目(或称分支数,用e表示)恰好比结点的数目(用n表示)少一

个,即e=n-1。这是树形结构最重要的一个结论。

3.树的基本术语
(1)结点:在树中,通常将数据元素称为结点。从计算机的角度来划
分,可以分为终端结点和非终端结点;以树的特征划分,可以分为根结点、
分支结点和叶子结点;用族谱的关系划分,可以分为双亲结点和孩子结点、
祖先结点和子孙结点、兄弟结点和堂兄弟结点。

116
数据结构(
C 
语言版)(第4版) 


图5.树的几种表示法

1 

(2)度:分为结点的度和树的度两种。结点的度是指与该结点相连接的孩子结点的
数目。树的度是指树中所有结点的度的最大值。
(3)深度:树是一种分层结构,根结点作为第一层,其余结点的深度(或称层次)为其
双亲结点的层数加1。树的深度(或称层数)是指树中所有结点的层次的最大值。
(4)有序树与无序树:如果将树中结点的各棵子树看成是从左到右有次序的(即不
能互换),则称该树为有序树,否则称该树为无序树。
(5)有向树与无向树:如果树的每个分支都是有方向的,则称该树为有向树,否则称
该树为无向树。
(6)n元树:树的度为n的有向树。

(7)位置树:指树中每个结点的孩子结点的位置不能被改变(改变则不是原树)的有
向树。例如,某结点可能没有第一个孩子结点,但却可能有第二个和第三个孩子结点。
(8)
m 
叉树:指树的度为m的有向位置树,即m元位置树。

(9)森林:指m(m≥0)棵互不相交的树的集合。对于树中的每个结点,其子树的集
合就是森林,因此森林和树是密切相关的。森林中的树也可以有顺序关系和位置关系。
5.1.2 
树的基本操作
树的基本操作通常有以下几种。
()初始化操作InitTre(T),用于建立一棵空树T。
()清空操作CleTre(T),用于释放树T占用的存储空间。
()判空操作EmpTre(T),用于判断树T是否为空树。
()求深度操作DepTre(T),用于计算树T的深度。
()插入操作Insid(p,c),用于在树T中插入子树c,使其成为p指向的结点

ChlT,i,

的第i棵子树。
eid(p,用于删除树T中p所指结点的第i棵子树。

(6)删除操作DlChlT,i),
(7)遍历操作TraTre(T),用于按某种次序对树T中的所有结点进行访问,且每个

第
5 
章　树和二叉树　71

结点仅访问一次。

二叉树是一种最简单的树形结构,它有许多好的性质,且任何树都可以转化为二叉
树。因此,下面重点研究二叉树的性质、存储结构及其应用。

5.二叉树
2 

5.2.1 
二叉树的定义和基本操作
1.二叉树的定义
二叉树(binarytre)是一种特殊的有向树,也称二元位置树,它的特点是每个结点至
多有两棵子树,即二叉树中的每个结点至多有两个孩子结点,且每个孩子结点都有各自的
位置关系。或者说,二叉树的子树有左右之分,其次序不能任意颠倒。具体地,二叉树或
者为空,或者由一个根结点及两棵不相交的、分别称为左子树和右子树的二叉树组成。

根据二叉树的定义,二叉树有5种形态,2所示。

如图5.


图5.二叉树的5种基本形态

2 

【1】
例5.列举出只有两个结点、三个结点的二叉树的所有形态。

(1)只有两个结点的二叉树的形态有两种,如图5.
3所示。


图5.只有两个结点的二叉树的所有形态

3 

(2)只有三个结点的二叉树的形态有五种,4所示。
如图5.


图5.只有三个结点的二叉树的所有形态

4 


数据结构(
C 
语言版)(第4版) 
满二叉树和完全二叉树是两种特殊形态的二叉树,在实际应用中经常用到。

满二叉树是除叶子结点外的任何结点均有两个孩子结点,且所有叶子结点都在同一
层的二叉树。这种二叉树的特点是每一层上的结点数目都是最大值。图5.5(a)是一棵深
度为4的满二叉树。


图5.满二叉树与完全二叉树

5 

完全二叉树是除去最底层结点后的二叉树是一棵满二叉树,且最底层结点均靠左对
齐的二叉树。在这里,靠左对齐的含义是左边是满的,即没有空隙再放入任何一个结点。
图5.b) 满二叉树是完全二叉树的一个特例。

5(是一棵深度为4的完全二叉树。实质上, 

2.二叉树的基本操作
二叉树的基本操作通常有以下几种。

(1)创建操作CreBiTre(bt),用于建立一棵二叉树bt。
(2)先序遍历操作PreOrder(bt),用于先序遍历二叉树bt。
(3)中序遍历操作InOrder(bt),用于中序遍历二叉树bt。
(4)后序遍历操作PostOrder(bt),用于后序遍历二叉树bt。
(5)查找操作Search(bt,x,p),用于在二叉树bt中查找值为x的结点,并通过p带
回该结点的指针。
(6)插入操作InsTre(bt,p,x),用于在二叉树bt中p指向的结点位置插入一个值
为x的结点。
(7)删除操作DelTre(bt,p),用于在二叉树bt中删除p指向的结点。
5.2.2 
二叉树的性质
二叉树有许多性质,也就是说,二叉树的理论基础较强,应用也较为广泛,下面依次进

行讨论
性质。
1:在二叉树的第i(i≥1)层上至多有2i-1个结点。
该性质的证明利用数学归纳法很容易实现,留给读者自行思考。
性质2:深度为k(k≥1)的二叉树上至多有2k-1个结点。
该性质的证明直接利用性质1即可,留给读者自行思考。
性质3:在任意一棵二叉树中,叶子结点的数目(用n0 表示)总是比度为2的结点的


第5 章　树和二叉树　1 19 
数目(用n2 表示)多一个,即n0=n2+1。
证明:设二叉树的结点总数为n,度为1的结点数为n1,则有
n=n0 +n1 +n2 (5-1) 
在二叉树中,除根结点之外的每个结点都有唯一的一个分支进入。设分支总数为e, 
则有
e=n-1 (5-2) 
由于这些分支或者是度为1的结点射出的,或者是度为2的结点射出的,所以有
e=n1 +2n2 (5-3) 
由式(5-2)和式(5-3)可以得到
n=n1 +2n2 +1 (5-4) 
由式(5-1)和式(5-4)可以得到
n0 =n2 +1 
证毕。
性质4:具有n个结点的完全二叉树的深度为log2n +1。
证明:设具有n个结点的完全二叉树的深度为k,则由性质2可知
2k-1 -1<n≤2k -1 
即
2k-1 ≤n<2k 
取以2为底的对数,得
k-1≤log2n<k 
因为log2n处于两个连续的整数k-1和k之间,所以k-1= log2n ,即
k= log2n +1 
证毕。
性质5:具有n个结点的完全二叉树,若按照从上至下、从左至右的顺序对二叉树中
的所有结点从1开始顺序编号,则对于序号为i(1≤i≤n)的结点,有: 
(1)其双亲结点的编号为.i/2.(1<i≤n)。
(2)其左孩子结点的编号为2i(1≤i≤n/2)。
(3)其右孩子结点的编号为2i+1(1≤i≤(n-1)/2)。
先利用数学归纳法证明(2)和(3),再从(2)和(3)推出(1),具体证明过程留给读者自
行思考。
性质6:在有n个结点的完全二叉树中,度为1的结点数为(n+1)%2。
证明:设完全二叉树中的分支数为e,则根据树的定义可知e=n-1。
若n为偶数,则分支数e为奇数,根据完全二叉树的定义可知,在完全二叉树中仅有
一个度为1的结点。
同理,若n为奇数,则分支数e为偶数,在完全二叉树中没有度为1的结点。
证毕。
性质7:具有n个结点的完全二叉树,若按照从上至下、从左至右的顺序对二叉树中
的所有结点从1开始顺序编号,则完全二叉树中编号大于.n/2.的结点均为叶子结点。

1 20 数据结构(C 语言版)(第4 版) 
证明:设完全二叉树中度为0的结点数为n0,度为1的结点数为n1,度为2的结点数
为n2。
(1)当n为偶数时,由性质6可知
n1 =1 (5-5) 
由性质3可知
n0 =n2 +1 (5-6) 
由式(5-5)和式(5-6)可以得到
n0 =n2 +n1 (5-7) 
又因结点总数为
n=n0 +n1 +n2 (5-8) 
由式(5-7)和式(5-8)可以得到
n0 =n1 +n2 = n/2 
即,当n为偶数时,编号大于.n/2.的结点均为叶子结点。
(2)当n为奇数时,由性质6可知
n1 =0 (5-9) 
又因结点总数为
n=n0 +n1 +n2 (5-10) 
由式(5-9)和式(5-10)可以得到
n=n0 +n2 (5-11) 
由性质3可知
n0 =n2 +1 (5-12) 
由式(5-11)和式(5-12)可以得到
n1 +n2 =(n-1)/2= n/2 
即,当n为奇数时,编号大于n/2的结点均为叶子结点。
证毕。
在此需要注意的是,一般二叉树的性质可用于完全二叉树,但完全二叉树的性质不能
用于一般二叉树。
【例5.2】 已知一棵完全二叉树中有234个结点,试问: 
(1)树的高度是多少? 
(2)第7层和第8层上各有多少个结点? 
(3)树中有多少个叶子结点? 有多少个度为2的结点? 有多少个度为1的结点? 
本例的分析如下。
(1)由性质4可知,该完全二叉树的高度(k)为
k=.log2234.+1=log227 +1=8 
(2)由性质1可知,第7层上的结点数为27-1=26=64(个)。
由性质2可知,第8层上的结点数为234-(27-1)=107(个)。
(3)由性质7可知,树中叶子结点的个数为234-.234/2.=117(个)。
由性质2可知,度为2的结点数为117-1=116(个)。
由性质6可知,度为1的结点数为1(个)。

第 5章　树和二叉树　121
5.2.3 
二叉树的遍历
二叉树的遍历是二叉树最基本的操作,通过遍历可以完成二叉树的很多操作。二叉
树遍历是指按照某种次序访问二叉树中的每个结点,且每个结点仅被访问一次。在这里, 
访问的含义比较广泛。访问并非一定是输出结点数据,还可能是查看结点属性值、更新结
点数据值、增加或删除结点等,这些都可以看成是访问。不失一般性,在此将以输出结点
值为例研究二叉树的遍历过程。

第2章中介绍的线性表的遍历比较简单,只需要从头至尾扫描一遍即可。由于二叉
树描述的数据元素之间的关系是一对多的关系,因此很难从头至尾一遍扫描完。从二叉
树的定义可以看出,一棵二叉树由根结点、左子树和右子树三部分组成。因此,只要依次
遍历这3部分,即可完成整个二叉树的遍历。假如以L、D、R分别表示遍历左子树、访问
根结点和遍历右子树,则有LDR 、LRD 、DLR 、DRL 、RLD 、RDL 六种遍历方式。在遍历
时,常常规定“先左子树(L), 后右子树(R)的(”) 顺序,因此遍历二叉树就有DLR 、LDR 和
LRD 这3种方式。根据根结点在遍历时的访问顺序,分别称以上3种方式为二叉树的先
(根)序遍历、中(根)序遍历和后(根)序遍历。

由图5.从根结点出发, 每个结点都分别从

6可以看出, 逆时针沿着二叉树外缘移动, 
左侧、正下方和右侧途经3次。访问的时机不同,就是不同的遍历。若结点访问均是第1 
次途经进行的,则是先序遍历;若结点访问均是第2次途经进行的,则是中序遍历;若结点
访问均是第3次途经进行的,则是后序遍历。图5.

6中的“”表示空指针。
【例5.已知一棵二叉树如图5.写出其先序、中序和后序遍历序列。

3】7所示, 


图5.二叉树的3种遍历访问结点的时机例5.

图5.3的二叉树

67 

先序遍历序列为-+a*b-cd/ef
。
中序遍历序列为a+b*c-d-e/f
。
后序遍历序列为abcd-*+ef/-
。


【4】
例5.已知一棵二叉树的先序遍历序列和中序遍历序列分别为KAFGIBEDHJC 
和AGFKEDBHJIC,试画出这棵二叉树。


数据结构(
C 
语言版)( 第4版) 
分析:先序遍历序列中的第一个元素一定是(子)树的根结点,在中序遍历序列中,排
在这个根结点前面的结点一定是其左子树上的结点,排在这个根结点后面的结点一定是
其右子树上的结点。如此依次作用于各子序列,就可以画出
整个二叉树的树形,而且是唯一的,8所示。

如图5.
【例5.已知一棵二叉树的后序遍历序列和中序遍
历


5】

序列分别为FBCGIEJDAH 和BFGCHIEADJ,试画出这棵
二叉树。

分析:后序遍历序列中的最后一个元素一定是(子)树的
根结点,在中序遍历序列中,排在这个根结点前面的结点一
定是其左子树上的结点,排在这个根结点后面的结点一定是
其右子树上的结点。如此依次作用于各子序列,就可以画出
整个二叉树的树形,而且是唯一的,9所示。

如图5.
【例5.已知一棵二叉树的先序遍历序列和后序遍历序列分别为AB 和BA,

6】试画
出这棵二叉树。
分析:由先序遍历序列可知,A一定是根结点,综合两种遍历序列可知,B既可能是
A的左孩子结点,也可能是A的右孩子结点, 如图5.

所以这棵树的形状是不确定的, 10 
所示。

图5.8例5.4的结果
图5.9 
例5.图5.例5.

5的结果10 
6的结果

与线性表类似,二叉树也有顺序存储和链式存储两种存储结构,所不同的是,这两种
存储结构不是表示数据的线性关系,而是表示一种层次关系。

5.2.4 
二叉树的顺序存储结构
将二叉树上的结点值按从上至下、从左至右的顺序存储到一个线性结构(通常为数
组)中,这种存储方式称为二叉树的顺序存储结构。但是,为了方便计算,并不能简单地将
各个结点顺序存放到数组的各个单元中,而必须增加一些虚结点,使之变成满二叉树的树
形。这样处理的目的是能够明确表示出树中各个结点之间的相互关系,给操作带来便利。
11(a) 11(b)

例如,对于图5.所示的二叉树,增加虚结点后的满二叉树如图5.所示,二叉树
的顺序存储示意图如图5.c)所示。其中,数组中下标为0的单元可用于存放满二叉树

11(
中结点的总数或二叉树的深度(图5.c)中存放的是深度为4的满二叉树的结点数), 而
虚结点可以用一个特殊的标志识别。
11(


第5 章　树和二叉树　1 23 
图5.11 二叉树及其顺序存储示意图
二叉树的顺序存储结构类型说明为 
#define MAXSIZE 100 /*存储空间最大容量*/ 
typedef char ElemType; /*结点值类型*/ 
#define VirNode '0' /*虚结点值*/ 
typedef ElemType SeqTree[MAXSIZE]; 
/*SeqTree[0]单元存放结点数,通常存放对应的满二叉树的结点数*/ 
下面介绍顺序存储二叉树基本操作的实现。
1.建立二叉树
算法思路:将结点值(包括虚结点)按层次依次存入相应单元,下标为0的单元存放
对应的满二叉树的结点数。 
void CreBiTree(SeqTree bt,int n) /*n 为真实结点总数*/ 
{ int i=1,j,m=0; 
while(m<n) 
{ for(j=i;j<2*i;j++) /*按层次输入,虚结点值一起输入*/ 
{ scanf("%c",bt+j); 
if(bt[j]!=VirNode) m++; 
} 
i=2*i; 
} 
bt[0]=i-1; /*0 号单元存放满二叉树的结点总数*/ 
} 
2.层次遍历
算法思路:从下标(编号)为1的单元开始,若是虚结点,则输出一个“*”号,否则输
出结点值,输出一层后换行。重复此操作,直到下标(编号)大于bt[0]为止。 
void LevelTree(SeqTree bt) /*按满二叉树遍历(输出)*/ 
{ int i=1,j; 
while(i<=bt[0]) /*按层扫描*/

1 24 数据结构(C 语言版)(第4 版) 
{ for(j=i;j<2*i;j++) /*扫描第i 层结点*/ 
if(bt[j]==VirNode) printf("*"); /*若是虚结点,则输出一个"*"号*/ 
else printf("%c",bt[j]); 
printf("\n"); 
i=2*i; /*跳到下一层的第一个结点*/ 
} 
} 
3.先序递归遍历
算法思路:若根结点编号不大于满二叉树的结点数,且为实结点,则进行下列操作: 
(1)访问根结点; 
(2)先序递归遍历根的左子树; 
(3)先序递归遍历根的右子树。 
void PreOrder(SeqTree bt,int i) /*i 是根结点存储位置(下标或编号)*/ 
{ if(i<=bt[0]) 
{ if(bt[i]!=VirNode) 
{ printf("%4c",bt[i]); /*访问根结点*/ 
PreOrder(bt,2*i); /*先序遍历根结点的左子树*/ 
PreOrder(bt,2*i+1); /*先序遍历根结点的右子树*/ 
} 
} 
} 
4.中序递归遍历
算法思路:若根结点编号不大于满二叉树的结点数,且为实结点,则进行下列操作: 
(1)中序递归遍历根的左子树; 
(2)访问根结点; 
(3)中序递归遍历根的右子树。 
void InOrder(SeqTree bt,int i) /*i 是根结点存储位置(下标或编号)*/ 
{ if(i<=bt[0]) 
{ if(bt[i]!=VirNode) 
{ InOrder(bt,2*i); /*中序遍历根结点的左子树*/ 
printf("%4c",bt[i]); /*访问根结点*/ 
InOrder(bt,2*i+1); /*中序遍历根结点的右子树*/ 
} 
} 
} 
5.后序递归遍历
算法思路:若根结点编号不大于满二叉树的结点数,且为实结点,则进行下列操作: 
(1)后序递归遍历根的左子树; 
(2)后序递归遍历根的右子树;