计算机软件基础：13第四章数据结构树.doc

《计算机软件基础》多媒体教程
第十三讲
第四章 数据结构
4.4 树
4.4.1 树的基本概念
⊙ 定义
设B=(K,R)是数据结构，K中有n个结点，R中只有一种关系r。定义B是一棵树，必须满足两个条件：
(1) K中有且仅有一个始结点，称为根结点。
(2) K中除了根结点以外的所有结点，可分成m个互不相交的集合{T1, T2, …, Tm}，每个集合Ti中的结点又都是一棵树，即以Ti为根结点的子树。
例： T = k1+{T1 + T2 + T3} T1 = k5+{k3, k10}
T2 = k6+{k8, k9, k4} T3 = k2
⊙ 树的图形表示
前件在上，后件在下，省略箭头。

⊙ 树的特性及命名
※ 除了根以外，其他结点有且仅有一个前件。
※ 前件称为父结点，父结点及其以上的所有结点称为父辈结点。
※ 后件称为子结点，子结点及其以下的所有结点称为子辈结点。
※ 没有子树(后件)的结点为叶结点，即终结点。
※ 非根非叶的结点称为内结点。

※ n次树
若某树中结点的最大后件数为n，则称该树为n次树。
例如：T1为四次树。
※ n次完全树
若某树中所有结点的后件数要么等于0，要么等于n，称为n次完全树(根和内结点的后件数为n，叶的后件数为0)。
例如：T2为二次完全树。
※ 有序树
如果对每个结点的各个子树确定次序，使其分别为第1棵子树，第2棵子树，…，则称该树为有序树。
※ 层号
规定根的层号为1，其子结点的层号为2，以此类推。
例如：T3的结点共分5层

⊙ 树的括号表示
※ 括号－－表示根和子结点
括号左边为根，括号内为子结点
※ 逗号－－表示同辈结点
同辈结点之间用逗号分隔
※ 例如，图示树的括号表示为：
k1 (k5 (k8, k3, k7), k6, k2 (k4))

4.4.2 树的基本操作
⊙ 查找 查找某结点或其父辈结点，或其子辈结点。
⊙ 遍历 按某种方式找遍全部结点或具有某种特征的结点。
⊙ 添加 添加结点或添加子树。
⊙ 删除 删除结点或删除子树。
⊙ 构造 按一定要求生成树。
⊙ 排序 按某种顺序排列结点。
4.4.3 树的存储形式
⊙ 存储方式
假定一棵m次有序树，各结点只有一个数据场分量，并且为整数。按照指针场的不同设置，可有三种存储方式：
※ 标准形式
设置m个指针场分量(p1k, p2k, …, pmk)，令pjk指向结点k的第j个子结点，则三次树中结点k的存储单元为：
k = {ak, dk, pk1, pk2, pk3}
例如图示树的标准形式存储如表所示。

ak
dk
p1k
p2k
p3k
10
k1
50
60
20
20
k2
40
Φ
Φ
30
k3
Φ
Φ
Φ
40
k4
Φ
Φ
Φ
50
k5
100
30
70
60
k6
Φ
Φ
Φ
70
k7
Φ
Φ
Φ
100
k8
Φ
Φ
Φ
※ 逆形式
设置一个指针场分量p0k，令p0k指向结点k的父结点，则树中结点k的存储单元为： k = {ak, dk, pk0}
例如，图示树的逆形式存储如表所示。
※ 扩充标准形式
将标准形式和逆形式结合在一起，设置m+1个指针场分量(p0k, p1k , p2k, …, pmk)，即p0k指向父结点，p1k到pmk指向子结点。
例如，图示树的扩充标准形式存储如表所示。
树的逆形式存储

树的扩充标准形式存储
ak
dk
p0k

ak
dk
p0k
p1k
p2k
p3k
10
k1
Φ

10
k1
Φ
50
60
20
20
k2
10

20
k2
10
40
Φ
Φ
30
k3
50

30
k3
50
Φ
Φ
Φ
40
k4
20

40
k4
20
Φ
Φ
Φ
50
k5
10

50
k5
10
100
30
70
60
k6
10

60
k6
10
Φ
Φ
Φ
70
k7
50

70
k7
50
Φ
Φ
Φ
100
k8
50

100
k8
50
Φ
Φ
Φ
⊙ 存储单元的数据定义
以n个结点的三次树的扩充标准存储形式为例，n个结点和最多4个(m+1)指针场的存储方式可以分别采用一维数组、二维数组、动态数组、多个指针或者链表实现。
(1) 结点存储： 一维数组
指针场存储： m+1个一维数组
#define M 100
short num[M]; /* M>=n */
short p0[M], p1[M], p2[M], p3[M];
(2) 结点存储： 一维数组
指针场存储：二维数组
#define M 100
short num[M];
short p[M][4];

※ 获得结点动态数组的程序语句
tree = (TREE *)malloc(n*sizeof(TREE));
※ 获得指针场动态数组的程序语句
tree[i].p=(short *)malloc((m+1)*sizeof(short));

结点存储采用一维数组
结点存储采用动态数组
指针场存储
采用
一维数组
(3) #define M 100
#define TREE struct tree
TREE
{ short num, p[4]; };
TREE tree[M];
(5) #define M 100
#define TREE struct tree
TREE
{ short num, p[4]; };
TREE *tree;
指针场存储
采用
动态数组
(4) #define M 100
#define TREE struct tree
TREE
{ short num, *p; };
TREE tree[M];
(6) #define M 100
#define TREE struct tree
TREE
{ short num, *p; };
TREE *tree;

(7) 结点存储采用链表勾链，指针场存储采用多个指针
#define TREE struct tree
TREE
{
short num;
TREE *father;
TREE *child1;
TREE *child2;
TREE *child3;
}；
TREE *root;
由指针root指向根结点，各结点间用指针形成链表勾链。

(8) 结点和指针场都采用链表勾链
TREE
{ short num；
TREE *father; /* 指向父结点 */
TREE *next; /* 指向同层结点 */
TREE *child; /* 指向子结点 */
};
TREE *root;

⊙ 空指针场分量的讨论
在大多数的情况下，非空指针场少于指针场容量。根据指针场的存储形式，可以采取某种方式处理指针场为空的情况。
※ 指针场的存储
(1) m+1个一维数组
short p0[M], p1[M];
short p2[M], p3[M];
(2) 二维数组 short p[M][4];
(3) (5) 一维结构数组
short p[4];
(4) (6) 动态数组
short *p;
(7) 多个指针
TREE *father, *child1;
TREE *child2, *child3;
(8) 链表勾链
TREE *father, *next, *child;
※ 处理方法
1. 指针场空置，不作处理。
例如，(1)和(2)。
2. 采用动态申请，设置可变长度的指针场。例如，将(3)和(5) 改为(4)或者(6)。
3. 采用二次树存储，可以节省指针场(将在5.5.1节讲授)。
4. 将空闲的指针场改为他用，如用于穿线树的存储方式(将在5.5.4节讲授)。

4.4.4 树的遍历
⊙ 树的遍历方式
树的遍历是指按照某种规律，逐个访问树中的全部或者部分结点。树的遍历包括以下各种方式：
※ 前序遍历
※ 后序遍历
※ 层次遍历
※ 结果遍历

⊙ 前序遍历
前序遍历(Preorder Search)，又称为深度优先搜索(DFS: Depth First Search)。前序遍历算法可描述为：
先访问根；
然后按前序遍历访问根的各棵子树。
例如，图示树的遍历结果为：
A B C E F H I J K D G
图中带箭头的实线表示遍历的顺序，同时也表示了各结点在遍历中的前后件关系。

⊙ 后序遍历
后序遍历(Postorder Search)算法可描述为：
先按后序遍历根的各棵子树；
再访问根。
例如，图示树的遍历结果为：
B E H I J K F C G D A
图中带箭头的虚线仅仅表示遍历的过程，而带箭头的实线则表示遍历的顺序，同时也表示了各结点在后序遍历中的前后件关系。

⊙ 层次遍历
层次遍历(Level Search) ，又称为广度优先搜索(BFS: Breadth First Search)。层次遍历算法可描述为：
从根开始，按层次顺序访问。
例如，图示树的遍历结果为：
A B C D E F G H I J K

⊙ 结果遍历
结果遍历(Yield Search)算法可描述为：
从根开始；
若树中只有一个结点，则根为树的结果；
否则各子树的结果为树的结果。
例如，图示树的遍历结果为：
B E H I J K G

实际上，在前序遍历或者后序遍历中跳过非叶结点，也同样可以获得结果遍历。例如，在以下前序或后序遍历中用下划线划出的的结点顺序与结果遍历的顺序相同。
前序：A B C E F H I J K D G
后序：B E H I J K F C G D A
4.4.5 树的遍历编程示例
【例4-4.1】编程实现一棵五次树的遍历。
假定采用链接存储方式，按标准形式存储一棵五次树，数据定义为：
#define NODE struct node
#define N 5
NODE
{
short num;
NODE *sub[N];
};
NODE *Root;

⊙ 预备程序
假定已经编制了一个C程序MakeTreeL.c(请到网络课堂下载)，按照以上数据的定义，输入括号形式描述的五次树数据时，能够生成一棵五次树。
例如，图示五次树的括号形式描述为：
5(7,12(4,8,19,11),30,2,13(32,40(3,17,23)))
允许出现任意的空字符，例如可以表示为：
5 (7, 12(4, 8, 19, 11) ,30 ,2 ,13(32 ,40(3,17,23) ) )
或者表示为：
5 (7, 12(4, 8, 19, 11) , 30 ,2 , 13(32 ,40(3,17,23) ) )
该文件中提供可以调用的函数为：
void input(void);
void MakeTree(void);
⊙ 用递归函数实现遍历五次树的程序
※ 编写C语言文件OrderTreeL.c如下：
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#define NODE struct node
#define N 5
#define M 1000
NODE
{
short num;
NODE *sub[N];
};
char String[M]; /* 存放输入字符串的数组 */
short Ptr=0; /* 字符数组的指针(下标) */
NODE *Root=NULL;
void input(void);
void MakeTree(void);
※ 用递归函数实现前序遍历
void preOrder(NODE *node)
{
int i;
if(!node)
return;
printf("%d ", node->num);
for(i=0; i<N; i++)
preOrder(node->sub[i]);
printf("\n");
}
※ 用递归函数实现后序遍历
void postOrder(NODE *node)
{
int i;
if(!node)
return;
for(i=0; i<N; i++)
postOrder(node->sub[i]);
printf("%d ", node->num);
printf("\n");
}
※ 实现前序遍历的main函数
void main()
{
input(); /* 输入括号表示 */
MakeTree(); /* 生成树 */
preOrder(Root);
}
※ 实现后序遍历的main函数
void main()
{
input(); /* 输入括号表示 */
MakeTree(); /* 生成树 */
postOrder(Root);
}
【例4-4.2】用非递归函数实现五次树的前序遍历
栈的应用，用非递归函数实现前序遍历的算法：
从根开始，将根入栈。
然后循环操作，只要栈非空：
栈顶结点出栈；
访问(打印)该结点，将它的子结点全部进栈；
直到栈空为止。

图示树的前序遍历结果：1 2 5 6 3 4

【例4-4.3】采用链接栈实现遍历
在makeTreeL.c中，增加链接栈的数据定义为：
#define STACK struct stack
STACK
{
NODE *node;
STACK *next;
};
STACK *Stack=NULL;
增加可调用的函数为：
void push(NODE *);
NODE *pop(void);
※ 非递归函数实现前序遍历
void preOrderL2(NODE *root)
{
NODE *node;
int i ;
if(!root)
return;
push(root);
while(node = pop())
{
printf("%d ", node->num);
for(i=N-1; i>=0; i--)
if(node->sub[i])
push(node->sub[i]);
}
}
※ 实现前序遍历的main函数
main()
{
input(); /* 输入括号表示 */
MakeTree(); /* 生成树 */
Stack = NULL; /* 清空栈 */
preOrderL2(Root);
printf("\n");
}
※ 编程要求
已提供：MakeTreeL.c
需要完成：OrderTreeL.c

【例4-4.4】采用顺序栈实现遍历
※ 有关顺序栈的数据定义
#define M 100
#define EMPTY -1
#define FULL M-1
#define BTM 0
#define N 5
short Node[M]; /* 数据值 */
short P[M][N]; /* 指针场 */
short Stack[M]; /* 栈 */
short Root; /* 根结点地址 */
short Top=EMPTY;
※ 编程要求
参照MakeTreeL.c，
编制程序：MakeTreeS.c
※ 非递归函数实现前序遍历
void preOrderS2(short root)
{
short ptr, i;
if(root == EMPTY)
return;
push(root);
while((ptr=pop()) != EMPTY)
{
printf("%d ", Node[ptr]);
for(i=N-1; i>=0; i-- )
if(P[ptr][i] != EMPTY)
push(p[ptr][i]);
}
}
参照OrderTreeL.c，编制程序：OrderTreeS.c
【例4-4.5】用非递归函数实现五次树的层次遍历
采用逐层进队逐层出队的方法，实现非递归的层次遍历算法：
从根开始，将根进队。
然后循环操作，只要队非空：
首结点出队；
访问(打印)该结点，将它的子结点全部进队；
直到队空为止。

图示树的层次遍历结果：1 2 3 4 5 6

4.4.6 树的括号表示和层号表示
※ 树的括号表示方法
如果树T只有一个结点，此结点就是它的括号表示。
如果树T由根结点A和子树T1, T2, …, TM组成，则树T的括号表示就是A(T1的括号表示, T2的括号表示, …, TM的括号表示)。
⊙ 括号表示方法示例
图示树括号表示的生成过程为：
E的括号表示: E(H)
F的括号表示: F(I, K)
B的括号表示: B(D, E, F)
= B(D, E(H), F(I, K))
G的括号表示: G(J, L)
C的括号表示: C(G) = C(G(J, L))

A的括号表示: A(B, C) = A(B(D, E(H), F(I, K)), C(G(J, L)))
⊙ 树的括号表示的唯一性
根据树的括号表示，可以唯一地确定一棵树，从而可以实现树的存储。
※ 树的层号表示方法
按某种遍历写出树中全部结点，并在结点之前注明其层号。
对树中的每一个结点k 规定一个正整数Lev(k)，满足：
对于根结点k0， Lev(k0) = 1；
如果k’是k的后件，则 Lev(k’) = Lev(k) + 1；
如果k’与k”是同一结点k的后件，则 Lev(k’)=Lev(k”)。
⊙ 按前序遍历的层号表示
例如，图示三次树的前序遍历为
A, B, D, E, H, I, F, J, C, G, K, L
层号=1：A
层号=2：B, C
层号=3：D, E, F, G
层号=4：H, I , J, K, L
则前序遍历的层号表示为

1A, 2B, 3D, 3E, 4H, 4I, 3F, 4J, 2C, 3G, 4K, 4L
⊙ 按后序遍历的层号表示
图示三次树的后序遍历为
D, H, I, E, J, F, B, K, L, G, C, A
则后序遍历的层号表示为
3D, 4H, 4I, 3E, 4J, 3F, 2B, 4K, 4L, 3G, 2C, 1A
⊙ 树的层号表示的唯一性
无论是前序遍历还是后序遍历的层号表示可以唯一地确定一棵树。
问题是如何根据树的层号表示来生成一棵树？如何编程?
※ 层号表示和括号表示的转换
⊙ 树的括号表示到层号表示的转换
在括号表示中对各个结点加上层号，可以转换为前序遍历的层号表示。
例如，对图示树的括号表示加上层号：

从而可以获得前序遍历的层号表示：
1A, 2B, 3D, 3E, 4H, 4I, 3F, 4J, 2C, 3G, 4K, 4L
⊙ 树的层号表示到括号表示的转换
根据树的前序遍历层号表示，可以转换成树的括号表示。
由于括号表示的结点序列实际上是按前序遍历的次序排列的。因此两者的结点顺序相同，只需要根据结点的层次关系进行转换。
例如，图示树前序遍历的层号表示为：
1A, 2B, 3D, 3E, 4H, 3F, 4I, 4K, 2C, 3G, 4J, 4L
可以转换为括号表示：
A(B(D, E(H), F(I, K)), C(G(J, L)))

【例4-4.6】根据后序遍历的层号表示生成树
⊙ 算法思路
根据后序遍历的性质，一个结点应在其父结点之前输入，根结点应该在最后输入。
采用栈来辅助完成算法，每次输入一个结点，并测试：
(1) 如果栈顶是它的子结点，出栈并生成指向子结点的链接；
(2) 结点进栈，等待输入父结点后出栈；
(3) 如果是根结点，栈内应该只剩层号为2的结点，全部出栈并生成根结点指向各子结点的链接。
⊙ 生成树的算法
令ctop=0 /* ctop为栈顶结点的层号，0表示空栈 */
whiLe(输入结点(c k) != 空) /* c为层号，k为结点值 */
{
whiLe(c == ctop-1) /* k是栈顶结点ktop的父结点 */
栈顶结点(ctop ktop)出栈，生成k指向ktop的链接
if(c > 1)
(c k)进栈，令ctop=c /* 等待父结点 */
eLse /* 必有c==1，k为根 */
全部出栈并生成k指向各子结点的链接，结束
}
⊙ 生成树的算法演示
输入文件为(后序遍历)
2 F 3 D 3 G 2 B 2 C 1 A
(1) 输入(2 F)，(c=2)>(ctop=0)，进栈
栈：(2 F)
(2) 输入(3 D)，(c=3)>(ctop=2)，进栈
栈：(3 D) (2 F)

(3) 输入(3 G)，(c=3)==(ctop=3)，进栈
栈：(3 G) (3 D) (2 F)
(4) 输入(2 B)，(c=2)==(ctop=3)-1，
(3 G)出栈，G连接为B的子结点
(3 D)出栈，D连接为B的子结点
(c=2)==(ctop=2)，进栈
栈：(2 B) (2 F)
(5) 输入(2 C)，(c=2)==(ctop=2)，进栈
栈：(2 C) (2 B) (2 F)
(6) 输入(1 A)，(c=1)==(ctop=2)-1
(2 C) 出栈，C连接为A的子结点
(2 B) 出栈，B连接为A的子结点
(2 F) 出栈，F连接为A的子结点，
结束
⊙ 生成树的图示过程

作 业
⊙ 习题 4-16(选择题), 4-17(树的存储形式), 4-18(树的遍历)
⊙ 上机编程(发给助教)
完成【例4-4.3】的编程exe4-4.3链接栈遍历.c，
完成4-36.5的编程exe4-36.5MakeTree5.c