第5章树和二叉树
5.1　内容概述
本章首先介绍树的定义和基本术语,然后介绍二叉树的定义、性质、存
储结构、遍历和线索二叉树,之后介绍树的存储结构、遍历、树(森林)与二
叉树的转换,最后介绍哈夫曼树及其应用。本章的知识结构如图5.1所示。
图5.1 第5章知识结构
考核要求:掌握树的定义和基本术语,掌握二叉树的定义和性质,掌握

1 10 　数据结构学习与实验指导（C 语言版）（第4 版） 
满二叉树和完全二叉树的特点,掌握二叉树的遍历方法及算法实现,了解二叉树的线索化
过程及其算法实现,掌握树的存储、遍历以及树(森林)与二叉树的转换,掌握哈夫曼树的
构造方法。
重点难点:本章的重点是二叉树的遍历算法及其相关应用,难点是如何利用本章的
相关知识设计出实现某种功能的有效算法。
核心考点:二叉树的定义和性质,满二叉树和完全二叉树的特点,二叉树的存储结
构,二叉树的遍历过程,二叉树的线索化过程,哈夫曼树的构造方法,二叉树上递归算法的
设计。
5.2　典型题解析
5.2.1 二叉树的定义及其性质 
二叉树的特点是每个结点至多有两棵子树,即任何结点的度不大于2,而且二叉树的
子树有左右之分,其次序不能任意颠倒。二叉树的性质是计算或证明二叉树中某类结点
的个数或高度的基础。
【例5.1】 下列关于二叉树度的说法中正确的是( )。
A.二叉树的度为2 B.一棵二叉树的度可以小于2 
C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2 
解析:二叉树中每个结点至多有两棵子树,即二叉树中任何一个结点的度都不大于
2。由此可知,二叉树中可以没有度为2的结点,此时二叉树的度或者为1(结点数≥2), 
或者为0(结点数≤1)。
答案:B 
【例5.2】 下列叙述中正确的是( )。
A.二叉树是度为2的有序树
B.完全二叉树一定存在度为1的结点
C.对于有n个结点的二叉树,其高度为.log2n.+1 
D.深度为k的二叉树中的结点总数≤2k-1 
解析:二叉树是度不大于2的有序树,选项A 错误。当结点个数n为偶数时,完全二
叉树中有且仅有一个度为1的结点;当结点个数n为奇数时,完全二叉树中没有度为1的
结点,选项B错误。具有n个结点的完全二叉树的深度为.log2n.+1,选项C错误。深度
为k(k≥1)的二叉树上至多有2k-1个结点,选项D正确。
答案:D 
【例5.3】 若一棵二叉树有10个度为2的结点,5个度为1的结点,则度为0的结点
的个数是( )。
A.9 B.11 C.15 D.不确定
解析:任意一棵二叉树中,叶子结点的数目(用n0表示)总比度为2的结点的数目(用
n2表示)多一个,即n0=n2+1。

第5 章　树和二叉树　1 11 
答案:B 
【例5.4】 一个具有1025个结点的二叉树,其高度最小为( )。
A.10 B.11 C.12 D.不确定
解析:在结点数相同的所有形态的二叉树中,完全二叉树的深度最小,且具有n个结
点的完全二叉树的深度为.log2n.+1。由此可知,具有1025个结点的二叉树的最小深度
为.log21025.+1=10+1=11。
答案:B 
【例5.5】 高度为K的二叉树最多有( )个结点。
A.2K B.2K-1 C.2K-1 D.2K-1-1 
解析:在所有高度为K的二叉树中,满二叉树的结点数最多,结点数为2K-1。
答案:C 
【例5.6】 有n个结点且高度为n的二叉树的数目是多少? 
解析:有n个结点且高度为n的二叉树是从根结点到叶子结点的单枝树,单枝树的
数目由单枝树的形态所决定,单枝树的形态由叶子结点的位置所决定。深度为n的单枝
树的叶子结点共有2n-1种不同的位置,所以二叉树的数目是2n-1。由此可知,本题等价于
高度为n的满二叉树有多少个叶子结点。
【例5.7】 已知完全二叉树的第7层有10个叶子结点,则整个二叉树的结点数最多
是多少? 
解析:第7层共有27-1=64个结点,已知有10个叶子,其余54个结点均为分支结
点。由于本题求二叉树的结点数最多是多少,所以第8层上有108个叶子结点。该二叉
树的结点数最多为27-1+108=235。
【例5.8】 已知一棵满二叉树的结点数在20~40之间,此二叉树的叶子结点有多
少个?
解析:因为深度为k的满二叉树的结点数为2k-1,所以结点数在20~40之间的满
二叉树的深度为5。由此可知,其叶子结点数为25-1=16。
【例5.9】 假设高度为h的二叉树上只有度为0和2的结点,问此类二叉树中的结点
数可能达到的最大值和最小值各为多少? 
解析:当二叉树是满二叉树时,结点数达到最大值,结点数为2h-1;当二叉树除第一
层外其余每层均有两个结点时,结点数达到最小值,结点数为2h-1。
【例5.10】 已知一棵完全二叉树顺序存储在A[1..N]中,如何求出A[i]和A[j]的最
近的公共祖先? 
解析:根据顺序存储的完全二叉树的性质,编号为i的结点的双亲的编号是.i/2.,故
A[i]和A[j]的最近公共祖先可如下求出: 
while(i/2!=j/2) 
if(i>j) i=i/2; else j=j/2; 
退出while循环后,若i/2==0,则最近的公共祖先为根结点,否则最近的公共祖先是i/2 
(或j/2)。

1 12 　数据结构学习与实验指导（C 语言版）（第4 版） 
5.2.2 二叉树的存储及其遍历
二叉树有顺序存储和链式存储(二叉链表)两种。二叉树遍历有先序遍历、中序遍历、
后序遍历和层次遍历四种。考查的重点是二叉树的递归遍历和非递归遍历的思想及算法
实现。考查方式主要有两种:一是对给定的二叉树,写出其先序、中序和后序遍历序列, 
或根据给定的遍历序列画出二叉树;二是算法设计,如建立给定遍历序列的存储结构、计
算满足条件的结点数、计算二叉树的高度(深度)、交换二叉树的左右子树、将叶子结点连
接成链表等。
【例5.11】 对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左
右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用
( )遍历实现编号。
A.先序 B.中序
C.后序 D.从根开始按层次
解析:由于每个结点的编号大于其左右孩子的编号,所以先遍历该结点的孩子,再遍
历该结点。在同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,所以先遍历
左孩子,再遍历右孩子。由此可知,遍历的顺序为左孩子→右孩子→根结点,故可采用后
序遍历实现编号。
答案:C 
【例5.12】 若一个二叉树的先序序列和后序序列正好相反,则该二叉树一定是
( )的二叉树。
A.空或只有一个结点 B.任一结点无左子树
C.高度等于其结点数 D.任一结点无右子树
解析:若二叉树的高度等于其结点数,则每层只有一个结点,其先序序列和后序序列
正好相反。选项A、B和D都是二叉树的高度等于其结点数的特殊情况,都不够全面。
答案:C 
【例5.13】 已知一棵二叉树的中序序列和后序序列,编写一个建立该二叉树的二叉
链表的存储结构的算法。已知一棵二叉树的中序遍历序列为CEIFGBADH,后序遍历序
列为EICBGAHDF,试画出该二叉树。
解析:首先建立根结点,根结点数据是后序遍历序列的最后一个元素,然后在中序序
列中查找根结点数据,根结点之前的元素在根结点的左子树上,根结点之后的元素在根结
点的右子树上,递归建立根结点的左右子树。 
typedef char ElemType; /*数据元素类型*/ 
typedef struct Node 
{ ElemType data; /*数据域*/ 
struct Node *lchild,*rchild; /*左右指针域,分别存储左右孩子的存储位置*/ 
}BitTree; 
BitTree *Creat(ElemType in[],ElemType post[],int l1,int h1,int l2,int h2) 
/*in 和post 存放中序序列和后序序列,l1,h1,l2,h2 分别是两个序列首尾结点的下标*/

第5 章　树和二叉树　1 13 
{ BitTree *t; 
int i; 
t=(BitTree *)malloc(sizeof(BitTree)); /*申请结点*/ 
t->data=post[h2]; /*后序遍历序列的最后一个元素是根结点数据*/ 
for(i=l1;i<=h1;i++) 
if(in[i]==post[h2]) break; /*在中序序列中查找根结点*/ 
if(i==l1) t->lchild=NULL; /*处理左子树*/ 
else t->lchild=Creat(in,post,l1,i-1,l2,l2+i-l1-1); 
if(i==h1) t->rchild=NULL; /*处理右子树*/ 
else t->rchild=Creat(in,post,i+1,h1,l2+i-l1,h2-1); 
return(t); 
}
中序遍历序列为CEIFGBADH、后序遍历序列为EICBGAHDF的二叉树的生成过
程如图5.2所示。
图5.2 二叉树的生成过程
【例5.14】 有n个结点的完全二叉树存放在一维数组A[1..n]中,试据此建立该二
叉树的二叉链表。
解析:完全二叉树按层次存储在一维数组A 中,编号从1到n。在数组A 中从下标
为1的单元开始依次取元素值,同时建立新结点,若结点的孩子存在,则递归建立该结点
的子树,否则子树为空。 
BitTree *Creat(ElemType A[],int n,int i) 
/*n 是结点数,i 是数组A 的下标,调用时i=1*/ 
{ BitTree *T; /*BitTree 的定义见例5.13*/ 
if(i<=n) 
{ T=(BitTree *)malloc(sizeof(BitTree)); /*建立新结点*/ 
T->data=A[i]; /*新结点的数据域值*/ 
if(2*i>n) T->lchild=NULL; /*左子树为空*/ 
else T->lchild=Creat(A,n,2*i); /*左子树不为空,递归建立左子树*/ 
if(2*i+1>n) T->rchild=NULL; /*右子树为空*/ 
else T->rchild=Creat(A,n,2*i+1); /*右子树不为空,递归建立右子树*/ 
}

1 14 　数据结构学习与实验指导（C 语言版）（第4 版） 
return T; 
}
【例5.15】 已知二叉树按二叉链表形式存储,编写算法,判断给定的二叉树是否为完
全二叉树。
解析:深度为k、具有n个结点的完全二叉树的每个结点都与深度为k的满二叉树中
编号从1至n的结点一一对应。从根结点开始,按层次扫描二叉树,若当前结点的左子树
不为空且前面已扫描结点的左右子树都不为空,或当前结点及前面已扫描的结点的左右
子树都不为空,则继续扫描下一个结点;否则不是完全二叉树,结束扫描。 
#define MAXSIZE 20 /*最多结点数*/ 
int Judge(BitTree *bt) /*BitTree 的定义见例5.13*/ 
{ int tag=0,front=0,rear=0; 
BitTree *p=bt, *Q[MAXSIZE]; /*Q 是队列,元素是二叉树结点指针*/ 
if(p==NULL) return 1; 
Q[rear++]=p; /*根结点指针入队*/ 
while(front!=rear) 
{ p=Q[front++]; /*出队*/ 
if(p->lchild&&! tag) Q[rear++]=p->lchild; /*左孩子入队*/ 
else if(p->lchild) return 0; /*前边已有结点为空,本结点不为空*/ 
else tag=1; / * 首次出现结点为空*/ 
if(p->rchild&&! tag) Q[rear++]=p->rchild; /*右孩子入队*/ 
else if(p->rchild) return 0; 
else tag=1; 
} 
return 1; 
}
【例5.16】 设T是一棵满二叉树,按顺序存储方式存储,编写将T 的先序遍历序列
转换为后序遍历序列的递归算法。
解析:先序序列的第一个元素是后序序列的最后一个元素,剩余元素的前一半在左
子树上,后一半在右子树上。用递归的方法将左子树的先序序列转换为后序序列,将右子
树的先序序列转换为后序序列。对一般二叉树,仅根据一个先序、中序或后序遍历序列不
能确定另一个遍历序列。但对于满二叉树,任一结点的左右子树均含有数量相等的结点, 
根据此性质,可将任一遍历序列转换为另一遍历序列,即任一遍历序列均可确定一棵二
叉树。 
typedef char ElemType; /*数据元素类型*/ 
void PreToPost(ElemType pre[],ElemType post[],int l1,int h1,int l2,int h2) 
/*l1,h1,l2,h2 分别是序列初始结点和最后结点的下标*/ 
{ int half; 
if(h1>=l1) 
{ post[h2]=pre[l1]; /*根结点*/ 
half=(h1-l1)/2; /*左子树或右子树的结点数*/

第5 章　树和二叉树　1 15 
PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1); 
/*将左子树先序序列转换为后序序列*/ 
PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1); 
/*将右子树先序序列转换为后序序列*/ 
} 
}
【例5.17】 已知二叉树按二叉链表方式存储,设计一个算法,把二叉树的叶子结点按
从左到右的顺序连接成一个单链表,表头指针为head。连接时用叶子结点的右指针域存
放单链表指针。
解析:采用中序递归遍历的方法查找叶子结点,设置前驱结点指针pre,初始为空。
第一个叶子结点由指针head指向,当遍历到叶子结点时,其前驱的rchild指针指向它,最
后叶子结点的rchild为空。 
BitTree *head,*pre=NULL; /*head 为头指针,pre 为尾指针*/ 
LinkLeaf(BitTree *bt) /*BitTree 的定义见例5.13*/ 
{ if(bt) 
{ LinkLeaf(bt->lchild); /*中序遍历左子树*/ 
if(bt->lchild==NULL&&bt->rchild==NULL) /*叶子结点*/ 
if(pre==NULL) { head=bt; pre=bt;} /*处理第一个叶子结点*/ 
else { pre->rchild=bt; pre=bt; } /*将叶子结点链入链表*/ 
LinkLeaf(bt->rchild); /*中序遍历右子树*/ 
pre->rchild=NULL; /*设置链表尾*/ 
} 
}
【例5.18】 已知二叉树采用二叉链表存储,编写非递归算法,交换二叉树的左右
子树。解
析:设置一个栈stack存放还没有交换过的结点,它的栈顶指针为top。交换左右
子树的算法如下。
(1)把根结点放入栈。
(2)当栈不为空时,取出栈顶元素,交换它的左右子树,并把它的左右子树的根结点
分别入栈。
(3)重复操作(2),直到栈为空为止。 
#define MAXSIZE 20 /*最多结点数*/ 
void Exchange(BitTree *t) /*BitTree 的定义见例5.13*/ 
{ BitTree *r,*p,*stack[MAXSIZE]; 
int top=0; 
stack[top++]=t; /*根结点入栈*/ 
while(top>0) /*栈不为空*/ 
{ p=stack[--top]; /*出栈*/ 
if(p) 
{ r=p->lchild; /*交换*/

1 16 　数据结构学习与实验指导（C 语言版）（第4 版） 
p->lchild=p->rchild; 
p->rchild=r; 
stack[top++]=p->lchild; /*左子树根结点入栈*/ 
stack[top++]=p->rchild; /*右子树根结点入栈*/ 
} 
} 
}
【例5.19】 假设一棵完全二叉树使用顺序存储结构存储在数组bt[1..n]中,写出进
行非递归先序遍历的算法。
解析:完全二叉树按顺序存储结构存储时,双亲与孩子结点的下标之间有确定关系。
对顺序存储结构的完全二叉树进行遍历与二叉链表类似。在顺序存储结构下,通过结点
下标是否大于n判断完全二叉树是否为空。 
typedef char ElemType; /*数据元素类型*/ 
#define MAXSIZE 20 /*最多结点数*/ 
void PreOrder(ElemType bt[],int n) 
{ int top=0,s[MAXSIZE]; /*top 是栈s 的栈顶指针*/ 
int i=1; 
while(i<=n||top>0) 
{ while(i<=n) 
{ printf("%3c",bt[i]); /*访问根结点*/ 
if(2*i+1<=n) s[top++]=2*i+1; /*右孩子的下标进栈*/ 
i=2*i; /*沿左孩子向下*/ 
} 
if(top>0) i=s[--top]; 
} 
}
【例5.20】 已知二叉树T采用二叉链表存储,设计算法,返回二叉树T 的先序序列
的最后一个结点的指针,要求采用非递归形式,且不允许使用栈。
解析:若二叉树有右子树,则二叉树先序序列的最后一个结点是右子树中最右下的
叶子结点;若二叉树无右子树,仅有左子树,则二叉树先序序列的最后一个结点是左子树
最右下的叶子结点;若二叉树无左右子树,则根结点是二叉树先序序列的最后一个结点。 
BitTree *LastNode(BitTree *bt) /*BitTree 的定义见例5.13*/ 
{ BitTree *p=bt; 
if(bt==NULL) return NULL; 
else 
while(p) 
if(p->rchild) p=p->rchild; /*若右子树不为空,则沿右子树向下*/ 
else if(p->lchild) p=p->lchild; /*若右子树为空,左子树不为空,则沿左子树向下*/ 
else return p; /*p 即为所求*/ 
}

第5 章　树和二叉树　1 17 
5.2.3 线索二叉树
线索二叉树分为先序线索二叉树、中序线索二叉树和后序线索二叉树三种。考查的
重点是建立和遍历线索二叉树的算法。考查的方式主要有两种:一是画出给定二叉树的
线索树,二是算法设计,如建立线索二叉树、在线索二叉树中查找给定条件的结点和在线
索二叉树中插入结点等。
【例5.21】 线索二叉树是一种( )结构。
A.逻辑 B.逻辑和存储 C.物理 D.线性
解析:当用二叉链表作为二叉树的存储结构时,因为每个结点中只有指向左右孩子
结点的指针域,所以从任一结点出发只能直接找到该结点的左右孩子,一般情况下无法直
接找到该结点在某种遍历序列中的前驱和后继结点。但是,在n个结点的二叉链表中含
有n+1个空指针域,因此可以利用这些空指针域存放指向结点在某种遍历次序下的前驱
或后继结点的指针。这种附加的指针称为线索,加上线索的二叉链表称为线索链表,相应
的二叉树称为线索二叉树。由此可知,线索二叉树是一种物理结构。
答案:C 
【例5.22】 一棵左子树为空的二叉树在先序线索化后,其空链域的个数为( )。
A.不确定 B.0 C.1 D .2 
解析:一棵左子树为空的二叉树在先序线索化后,因为第一个遍历的结点没有左孩
子且没有前驱,最后一个遍历的结点没有右孩子且没有后继,所以空链域的个数为2。
答案:D 
【例5.23】 若X是二叉中序线索树中的一个有左孩子的结点,且X 不为根结点,则
X的前驱为( )。
A.X的双亲 B.X的右子树中最左的结点
C.X的左子树中最右的结点 D.X的左子树中最右的叶子结点
解析:由中序遍历的过程可知,访问X的左子树的最右结点后访问X,X的左子树的
最右结点的右链域是线索,指向其后继X。由此可知,X 的前驱为X 的左子树中最右的
结点。答
案:C 
【例5.24】 设t是一棵按后序遍历方式构成的线索二叉树的根结点指针,试设计一
个非递归的算法,把一个地址为x的新结点插入t树,已知地址为y的结点右孩子作为结
点x的右孩子,并使插入后的二叉树仍为后序线索二叉树。
解析:在线索二叉树上插入结点,破坏了与被插入结点的线索,因此在插入结点时必
须修复线索。因为是后序线索树,所以在结点y的右侧插入结点x时要区分结点y有无
左子树的情况。 
typedef char ElemType; /*数据元素类型*/ 
typedef struct node 
{ ElemType data; /*数据域*/ 
struct node *lchild; /*左链域*/

1 18 　数据结构学习与实验指导（C 语言版）（第4 版） 
struct node *rchild; /*右链域*/ 
int ltag; /*左链域信息标志*/ 
int rtag; /*右链域信息标志*/ 
}BiThrTree; 
void Insert(BiThrTree *t,BiThrTree *y,BiThrTree *x) 
{ BiThrTree *p; 
if(y->ltag==0) /*y 有左孩子*/ 
{ p=y->lchild; 
if(p->rtag==1) p->rchild=x; /*x 是y 的左孩子的后序后继*/ 
x->ltag=1; x->lchild=p; /*x 的左线索是y 的左孩子*/ 
} 
else /*y 无左孩子*/ 
{ x->ltag=1; x->lchild=y->lchild; /*y 的左线索成为x 的左线索*/ 
if(y->lchild->rtag==1) /*若y 的后序前驱的右标记为1*/ 
y->lchild->rchild=x; /*则将y 的后序前驱的后继改为x*/ 
} 
x->rtag=1; 
x->rchild=y; 
y->rtag=0; 
y->rchild=x; /*x 作为y 的右子树*/ 
}
【例5.25】 编写算法,在中序线索二叉树中查找值为x的结点的后继结点,并返回该
后继结点的指针。
解析:先在带头结点的中序线索二叉树T中查找值为x的结点,然后在中序线索二
叉树T中查找值为x的结点的后继结点。 
BiThrTree *Search(BiThrTree *T,ElemType x) /*BiThrTree 的定义见例5.24*/ 
/*在带头结点的中序线索二叉树T 中查找值为x 的结点*/ 
{ BiThrTree *p; 
p=T->lchild; /*p 指向二叉树的根结点*/ 
while(p!=T) 
{ while(p->ltag==0&&p->data!=x) p=p->lchild; 
if(p->data==x) return p; 
while(p->rtag==1&&p->rchild!=T) 
{ p=p->rchild; if(p->data==x) return p;} 
p=p->rchild; 
} 
}B
iThrTree *AfterNode(BiThrTree *T,ElemType x) 
/*在中序线索二叉树T 中查找值为x 的结点的后继结点*/ 
{ BiThrTree *p,*q; 
p=Search(T,x); /*在T 中查找给定值为x 的结点,由p 指向*/ 
if(p->rtag==1)