高等学校精品课程
（第2版）
李云清 杨庆红 揭安全
人民邮电出版社人民邮电出版社
江西省高等学校精品课程
揭安全
E_mail:E_mail: jieanquan@@
江西师范大学计算机信息工程学院
mailto:jieanquan@
退出
5 递归与递归程序设计
在一个函数的定义中出现了对自己本身的调 用
，称之为直接递归；或者一个函数p的定义中包含了
对函数q的调用，而q的实现过程又调用了p，即函数
调用形成了一个环状调用链, 这种方式称之为间接递
归。递归技术在算法和程序设计中是一种十分有用
的技术，许多高级程序设计语言均提供了支持递归
定义的机制和手段。
退出
试编写一个函数，在第一行打印输出1个1，在第二
行打印输出2个2， ……在第n行打印输出n个n。例
如，当n=5时，调用该函数的输出结果为：
1
2 2
3 3 3
4 4 4 4
5 5 5 5 5
该问题的算法为:
print ( int n )
{ int i;
if (n!=0)
{ print(n-1);
for(i=1;i<=n;i++)
printf("%d",n);
printf("\n");
}
}
退出
分析
print(2)
print(1)
print(0)
for(i=1;i<=1;i++
printf(“%d”,1)
5!=0
递归
print(4)
print(3)
for(i=1;i<=2;i++)
printf(“%d”,2)
Printf(“\n”);
for(i=1;i<=3;i++)
printf(“%d”,3)
Printf(“\n”);
Printf(“\n”);
Print(5)
for(i=1;i<=4;i++) printf(“%d”,4)
printf(“\n”);
for(i=1;i<=5;i++)
printf(“%d”,5)
printf(“\n”);
结束
退出
结论
根据所求解问题的性质，将原问题分解成
若干子问题，这些子问题的结构与原问题
的结构相同，但规模较原问题小。
子问题的求解通过以一定的方式修改参数
进行函数自身调用加以实现，然后将子问
题的解组合成原问题的解。递归调用时，
参数的修改最终必须保证递归出口得以满
足。
退出
第6章 树型结构
树的基本概念
树类的定义
树的存储结构
树的遍历
树的线性表示
退出
树的基本概念
树是由n (n≥0)个结点构成的有限集合，n=0 的
树称为空树；当n≠0时，树中的结点应该满足以下
两个条件：
(1) 有且仅有一个特定的结点称之为根；
(2) 其余结点分成m(m≥0)个互不相交的有限集合
T1,T2,……Tm，其中每一个集合又都是一棵树，称
T1, T2,……Tm为根结点的子树。
退出
11 12 13 14
1
10
有向树 ：
１） 有确定的根； 3 2 4
２） 树根和子树根之间为有向关系 6 5 7 8 9
A
B C D
E F G H I
图 J K
1
2 3 4
5 6 7 8 9 10
11 12 13 14
退出
和线性结构的比较
线性结构 树结构
第一个数据元素(无前驱) 根结点(无前驱)
最后一个数据元素(无后继) 多个叶子结点(无后继)
其它数据元素 树中其它结点
(一个前驱、一个后继) (一个前驱、多个后继
)
退出
基本术语
结点:数据元素 + 若干指向子树的分支
结点的度:分支的个数
树的度:树中所有结点的度的最大值叶
子结点:度为零的结点（终点结点）
分支结点:度大于零的结点（非终端结点）
从根到结点的路径：
孩子结点、双亲结点、兄弟结点、祖先、子孙
结点的层次:假设根结点的层次为1,
第l层的结点的子树根结点的层次为l+1
退出
树形表示法
树A的高为4，度为3
根
D的度为3
第1层
第2层
A
B C D
第4层 E F G H I J
K L
叶子的度为0
叶子
M
(a)
子树
退出
树的深度：：树中叶子结点所在的最大层次 森
林：：是m（m≥0）棵互不相交的树的集合
任何一棵非空树是一个二元组
Tree = （root，F）
其中：root被称为根结点，F被称为子树森林
有序树和无序树的区别在于：
退出
A
B C D
E F
A
D C B
E F
子树之间是否存在次序关系？
图 有序树和无序树的比较
树型结构的其他表示方法：
退出
A C
B
E F
D
G
I
H
K
J
A(B(E,F),C,D(G,H(J,K),I))
(a) 图的括号表示法
(b) 图的嵌套集合表示法
退出
A
B
E
F
C
D
G
H
J
K
I
(C)图的凹入表示法
退出
树类的定义
ADT tree {
数据对象D:具有相同性质的数据元素构成的有
限集合;
数据关系R:如果D为空或D仅含一个元素,则R为
空;否则,D中存在一个特殊的结点root,称之为根结点,
其无前驱;其他结点被分成互不相交的m(m≥0) 个集
合,分别构成root的m棵子树;若这些子树非空, 则它
们的根结点rooti均称为整棵树根结点root的后继结
点;而每棵子树也是一棵树,因而它们中数据元素间的
关系也同样满足数据关系R。
树的基本操作如下:
退出
树类的定义
（1） inittree(T) 初始化一棵树T;
（2） cleartree(T) 若树T已存在,则
将它置空,使之成为一棵空树;
（3） emptytree(T) 判断一棵已存在
的树T是否是空树,若是返回1;否则返回0;
（4） root(T) 返回树T的根结
点;
（5） child(T,a,i) 返回树T中结点
a的第i个子女;
（6） parent(T,a) 返回树T中结点
a的双亲;
退出
树类的定义
（7） degree(T,a) 返回树T中结点
a的度数;
（8） depth(T) 返回树T的高度
（深度）;
（9） choose(T,C) 返回树T中满足
条件C的某一个结点;
（10） addchild(T,a,i,t1) 表示在树T中将
树t1作为结点a的第i棵子树插入;
（11） delchild(T,a,i) 若树T中结点a
的第i棵子树存在,则删除它;
（12） createtree(a,F) 构造一棵新树,
该树以a为根结点、以森林F中的树为子树;
退出
树类的定义
（13） equaltree(T1,T2) 判断两棵树T1和T2是否
相等,若相等,返回1;否则返回0;
（14） numofnode(T) 返回树T中所含结点的
个数;
（15） preorder(T) 输出树T前序遍历的结
果;
（16） postorder(T) 输出树T后序遍历的结
果;
（17） levelorder(T) 输出树T层次遍历的结
果;
（18） destroytree(T) 销毁一棵已存在的树T。
} ADT Tree
退出
树的存储结构
根据数据元素之间关系的不同表示方式，常用的
树存储结构主要有三种：双亲表示法、孩子表示法和
孩子兄弟表示法。
双亲表示法
在树中，除根结点没有双亲外，其他每个结点的
双亲是唯一确定的。因此，根据树的这种性质，存储
树中结点时，可以包含两个信息：结点的值data和
体现结点之间相互关系的属性 该结点的双亲
parent。借助于每个结点的这两个信息便可唯一地
表示任何一棵树。这种表示方法称为双亲表示法。
退出
#define MAXSIZE 100
typedef char datatype; /*结点值的类型*/
typedef struct node /*结点的类型*/
{
datatype data;
int parent; /*结点双亲的下标*/
} node;
typedef struct tree
{
nodetreelist[MAXSIZE]; /*存放结点的数组*/ int
length, root ; /* 树中实际所含结点的
个数及根结点的位置*/
} tree;
退出
(a) 一棵树
图6 .4
0
1
2
3
4
5
6
7
8
9
10
(b) (a)图的双亲表示法
root
A
B C D
E F G H
I J K
data parent
A -1
B 0
C 0
D 0
E 1
F 1
G 3
H 3
I 6
J 6
K 6
退出
孩子表示法
采用孩子表示法表示一棵树时，树中每个结点除
了存储其自身的值之外，还必须指出其所有子女的位
置，即整棵树中所有结点的相互关系是通过指明结
点子女的位置来体现的，称这种表示法为孩子表示法。
根据子女位置的实现方法不同，孩子表示法分
为三种：指针方式的孩子表示法 、数组方式的孩子
表示法、链表方式的孩子表示法 。
1、指针方式的孩子表示法
退出
指针方式的孩子表示法中每个结点通常包含两个
域：一个是元素的值域data，另一个为指针数组，数
组中的每个元素均为一个指向该结点子女的指针；一
棵m度的树，其指针数组的大小即为m。
1、指针方式的孩子表示法
退出
#define m 3 /*树的度数*/
typedef char datatype; /*结点值的类型*/
typedef struct node
{ /*结点的类型*/
datatype data;
struct node *child[m]; /*指向子女的指针数组*/
} node *tree;
tree root;
其中root表示指向树根结点的指针。
退出
A
∧DC ∧ ∧ ∧∧B
root data child[0] child[1] child[2]
图中(a)图的指针方式的孩子表示法
E ∧ ∧ ∧ F ∧ ∧ ∧ ∧∧∧HG
I ∧ ∧ ∧ J ∧ ∧ ∧ K ∧ ∧ ∧
退出
为了查找方便，可以将树中的所有结点存储在
一个一维数组中，这样每个结点子女的位置便可以
通过数组的下标来体现，称这种孩子表示法为数组
方式的孩子表示法。
#define m 3
#define MAXSIZE 20 typedef
char datatype; typedef struct
node {
datatype data;
int child[m];
} treenode;
treenode tree[MAXSIZE]; int
root ; int length;
2、数组方式的孩子表示法
退出
A
B C D
E F G H
I J K
(a) 一棵树
root 0
1
2
3
4
5
6
7
8
9
10
图中(a)图的数组方式的孩子表示法
data child[0] child[1] child[2]
A 1 2 3
B 4 5 -1
C -1 -1 -1
D 6 7 -1
E -1 -1 -1
F -1 -1 -1
G 8 9 10
H -1 -1 -1
I -1 -1 -1
J -1 -1 -1
K -1 -1 -1
退出
3、链表方式的孩子表示法
树的链表方式的孩子表示法中，把每个结点的子
女排列起来形成一个单链表，这样n个结点就形成n个
单链表；而n个单链表的头指针又组成一个线性表，为
了查找方便，使用数组加以存储。
# define MAXSIZE 50
typedef char datatype;
typedef struct chnode { /*孩子结点的类型*/
int child;
struct chnode *next;
} chnode
typedef chnode * chpoint;
退出
typedef struct { /* 树中每个结点的类型 */
datatype data;
chnode *firstchild; /*指向第一个子女的指针*/
} node;
typedef struct { /*树的类型*/
node treelist [MAXSIZE];
int length, root；
} tree;
退出
A
B
C
D
E
F
G
H
I
J
K
∧
∧
∧
∧
∧
∧
∧
98
∧76
∧54
1
∧1
0
root
data firstchild
0
1
2
3
4
5
6
7
8
9
10
treelist
childnext
图中(a)图的链表方式的孩子表示法
2 ∧3
退出
孩子兄弟表示法
所谓孩子兄弟表示法，即在存储树中每个结点
时，除了包含该结点值域外，还设置两个指针域
firstchild和rightsibling，分别指向该结点的第一
个子女和其右兄弟，即以二叉链表方式加以存储，
因此该方法也常被称为二叉树表示法。
typedef char datatype; /*树中结点值的类型*/
typedef struct node { /*树中每个结点的类型*/
datatype data;
struct node * firstchild, *rightsibling;
} node, * pnode;
pnode root; /*指向树根结点的指针*/
退出
F ∧ ∧ H ∧ ∧∧E G
root
data firstchildrightsibling
图中(a)图的孩子兄弟表示法
B ∧C ∧D
∧I ∧J K ∧ ∧
∧A
退出
树的遍历
所谓树的遍历，指按某种规定的顺序访问树中
的每一个结点一次，且每个结点仅被访问一次。树
的遍历方式分为以下三种：
（1）树的前序遍历：首先访问根结点，再依次按前
退出
序遍历的方式访问根结点的每一棵子树。
（2）树的后序遍历：首先按后序遍历的方式访问
退出
根结点的每一棵子树，然后再访问根结点。
退出
（3）树的层次遍历：首先访问第一层上的根结点，
然后从左到右依次访问第二层上的所有结点，再以同
样的方式访问第三层上的所有结点，……，最后访问
树中最低一层的所有结点。
退出
前序遍历的结果：
ABCEFHIGD
后序遍历的结果：
BEHIFGCDA
层次遍历的结果：
ABCDEFGHI
A
B C D
E F G
H I
退出
以下以指针方式的孩子表示法作为树的存储结
构，分别实现树的各种遍历算法。
1、树的前序遍历的递归实现
void preorder(tree p) /*p为指向树根结点的指针*/
{
int i;
if (p!=NULL) /*树不为空*/
{ printf(“%c”,p->data); for
(i=0;i<m;++i)
preorder(p->child[i]); //递归对各子树进行遍历
}
}
退出
2、树的后序遍历的递归实现
void postorder(tree p)
/*p为指向树根结点的指针*/
{ int i;
if (p!=NULL) /*树不为空*/
{
for (i=0;i<m;++i)
postorder(p->child[i]);
printf("%c",p->data);
}
}
退出
3、按前序遍历顺序建立一棵3度树的递归算法
void createtree (tree *p )
{ int i; char ch;
if ((ch=getchar())= =‘ ’) *p=NULL;
else
{ *p=(tree) ma llloc (sizeof(node));
/*产生树的根结点*/
(*p)->data=ch; for
(i=0;i<m;++i)
/*按前序遍历顺序依次产生每棵子树*/
createtree(&(*p)->child[i]);
}
}
4、树的层次遍历算法
退出
在树的层次遍历过程中，对于某一层上的每个
结点被访问后，应立即将其所有子女结点按从左到
右的顺序依次保存起来，该层上所有结点的这些子
女结点正好构成下一层的所有结点，接下来应该被
访问的就是它们。显然，这里用于保存子女结点的
数据结构选择队列最合适，队列中的每个元素均为
在排队等待访问的结点。
4、树的层次遍历算法
退出
由于树的层次遍历首先访问的是根结点，因此
初始时队列中仅包含根结点。只要队列不为空，就
意味着还有结点未被访问，遍历就必须继续进行；
每次需访问一个结点时均取队头元素，访问完成 后
，若其子女非空，则将其所有子女按顺序依次进队
；不断重复以上过程，直到队列为空。
退出
void levelorder(tree t)
{tree queue[20]; /*存放等待访问的结点队列*/ int
f,r,i; /*f、r分别为队头、队尾指针*/ tree
p;
f=0; r=0; queue[0]=t;
while (f<=r) /*队列不为空*/
{ p=queue[f]; f++; printf("%c",p->data); for
(i=0;i<m;++i)
if (p->child[i])
{ ++r; queue[r]=p->child[i];
}
}
}
退出
树的线性表示
树的括号表示
1、树的括号表示的规则为：
（1） 若树T为空树，则其括号表示为空；
（2） 若树T只包含一个结点，则其括号表示即为该
结点本身；
（3） 如果树T由根结点A和它的m棵子树TT11，，TT22，，…T…Tmm
构成，则其括号表示为：
A(T1的括号表示，T2的括号表示，……Tm的括号表示)
其中子树的括号表示同样应该遵循以上规则。
退出
该树的括号表示为：
AA (( B,B, CC (( FF ,, GG ,H,H )) ,, DD ,, EE (( JJ ,, II )) ))
图图66 .
2、树的括号表示具有以下特点：
（1） “（”前面的元素一定为某棵树或子树的根结点，
而其所有子树中的结点一定位于该“（”和与之对应的
“）”之间；
（2） 任何“（”和与之配对的“）”之间的括号表示序
列同样满足(1)中的性质。
A
B C D E
F G H J I
退出
3、树的括号表示到树的孩子表示的转换算法
（1） 从左到右扫描树的括号表示；
（2） 每当遇到左括号时，其前一个结点进栈，并读
下一个符号；
（3） 每当遇到右括号时，栈顶元素出栈。说明以栈
顶元素为根的子树构造完毕，此时若栈为空，
算法结束，否则读下一个符号；
（4） 每当遇见结点，则它一定为栈顶元素的子女，
将其挂到栈顶元素的某子女位置上，并读下一
个符号；
（5） 每当遇到“，”，则滑过该符号，并读下一个符
号。
退出
#define m 3 /* 树的度数*/
#define MAXSIZE 20 /* 树的孩子表示法对应的数组大小*/ #define
BMAXSIZE 50 /*树的括号表示对应的数组大小*/
typedef char datatype; /* 树中结点值的类型*/
typedef struct node { /*树的孩子表示法中结点的类型*/
datatype data;
int child[m];
} treenode;
treenode tree[MAXSIZE]; /*树孩子表示法的存储数组*/ int
root ; /*根结点的下标*/
int length; /*树中实际所含结点的个数*/
char p[BMAXSIZE]; /*存放树括号表示的数组*/
退出
void bracktotree(char p[],int *root, int *length,treenode tree[])
{ /*将树的括号表示法转换成树的孩子表示法*/
int stack[MAXSIZE]; int top; int i,j,k,l,done;
k=0; j=0; *root=0; top=-1; done=1; tree[j].data=p[k];
++k;
for (i=0;i<m;++i) tree[j].child[i]=-1;
while (done)
{ if (p[k]=='(')
{ ++top; stack[top]=j; ++k; }
else if (p[k]==')')
{--top; if (top==-1) done=0; else ++k;}
else if (p[k]==',') ++k;
else { ++j;
tree[j].data=p[k];
退出
for (i=0;i<m;++i)
tree[j].child[i]=-1;
l=stack[top]; i=0;
while (tree[l].child[i]!=-1)
++i;
tree[l].child[i]=j; ++k;
}
}
*length=j;
}
退出
树的层号表示
设j为树中的一个结点，若为j赋予的一个整数值
lev(j)满足以下两个条件：
（1） 如果结点i为j的后件, 则lev(i)>lev(j)；
（2） 如果结点i与j为同一结点的后件，则
lev(i)=lev(j)。
称满足以上条件的整数值lev(j)为结点j的层号。
树的层号表示为：首先根据层号的定义为树中的 每
个结点规定一个层号，然后按前序遍历的顺序写出 树中
所有的结点，并在每个结点之前加上其层号即可。
退出
以下是上图中树的两种层号表示：
∧ 10A,20B,20C,30F,30G,30H,20D,20E,40J,40I
∧ 1A，2B，2C，5F，5G，5H，2D，2E，3J，3I
A
B C D E
F G H J I
退出
树的层号表示到树的扩充孩子表示转换算法：
（1） 从前往后扫描树的层号表示；
（2） 若结点i的层号比其前一个结点j的层号大，说
明结点i位于结点j的下一层,且正好为j的第一个
子女；
（3） 若结点i的层号与结点j的层号相等，说明两结
点位于同一层，它们拥有共同的双亲；
（4） 若结点i的层号比结点j的层号小，说明结点i
与结点j的某个祖先结点互为兄弟，于是应该
沿着j的双亲向树根方向寻找i的兄弟，从而找
到它们共同的双亲。
退出
#define m 3
#define MAXSIZE 20
typedef char datatype;
typedef struct node {
datatype data;
int child[m];
int parent;
} treenode;
typedef struct { /*层号表示法中结点的类型*/
datatype data;
int lev; /*存储结点的层号*/
} levelnode;
退出
treenode tree[MAXSIZE]; int
root ;
int length;
levelnode ltree[MAXSIZE];
退出
void leveltotree(int length,levelnode ltree[], int *root, treenode
tree[])
{ /*将树的层号表示法转换成树的扩充孩子表示法*/ int
i,j,k;
for (i=0;i<length;++i) for
(j=0;j<m;++j)
tree[i].child[j]=-1;
*root=0; tree[0].data=ltree[0].data;
tree[0].parent=-1;
for (i=1;i<length;++i)
{ tree[i].data=ltree[i].data; j=i-
1;
if (ltree[i].lev>ltree[j].lev)
{ tree[i].parent=j; tree[j].child[0]=i; }
退出
else {
}
}
while (ltree[i].lev<ltree[j].lev)
j=tree[j].parent;
tree[i].parent=tree[j].parent;
j=tree[j].parent;
k=0; /*将结点i挂到双亲结点上*/
while (tree[j].child[k]!=-1)
++k;
tree[j].child[k]=i;
}
退出
习题6
树最适合用来表示具有（ ）性和（ ）性的数据。
在选择存储结构时，既要考虑数据值本身的存储，还需
要考虑（ ）的存储。
对于一棵具有n个结点的树，该树中所有结点的度数之和
为（ ）。
已知一棵树如图所示，试回答以下问题：
图 一棵树
退出
（1） 树中哪个结点为根结点？哪些结点为叶子结点？
（2） 结点B的双亲为哪个结点？其子女为哪些结点？
（3） 哪些结点为结点I的祖先？哪些结点为结点B的子孙？
（4） 哪些结点为结点D的兄弟？哪些结点为结点K的兄弟？
（5） 结点J的层次为多少？树的高度为多少？
（6） 结点A、C的度分别为多少？树的度为多少？
（7） 以结点B为根的子树的高度为多少？
（8） 试给出该树的括号表示及层号表示形式。
退出
试写出图所示树的前序遍历、后序遍历和层次遍历
的结果。
试给出图所示树的双亲表示法和数组方式孩子表示
法的表示。
已知一棵度为m的树中有n1个度为1的结点，n2个度为2
的结点，……，nm个度为m的结点，问该树中有多少个叶子
结点？
假设树采用指针方式的孩子表示法表示，试编写一个非
递归函数，实现树的前序遍历算法。
假设树采用指针方式的孩子表示法表示，试编写一个非
递归函数，实现树的后序遍历算法。
假设树采用指针方式的孩子表示法表示，试编写一个
函数，判断两棵给定的树是否等价（两棵树等价当且仅当其
根结点的值相等且其对应的子树均相互等价）。
