计算机软件基础：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 + T3T1 = k5+k3, k10T2 = k6+k8, k9, k4T3 = 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例如图示树的标准形式存储如表所示。akdkp1kp2kp3k10k150602020k24030k340k450k5100307060k670k7100k8 逆形式设置一个指针场分量p0k，令p0k指向结点k的父结点，则树中结点k的存储单元为：k = ak, dk, pk0例如，图示树的逆形式存储如表所示。 扩充标准形式将标准形式和逆形式结合在一起，设置m+1个指针场分量(p0k, p1k , p2k, , pmk)，即p0k指向父结点，p1k到pmk指向子结点。例如，图示树的扩充标准形式存储如表所示。树的逆形式存储树的扩充标准形式存储akdkp0kakdkp0kp1kp2kp3k10k110k150602020k21020k2104030k35030k35040k42040k42050k51050k510100307060k61060k61070k75070k750100k850100k850 存储单元的数据定义以n个结点的三次树的扩充标准存储形式为例，n个结点和最多4个(m+1)指针场的存储方式可以分别采用一维数组、二维数组、动态数组、多个指针或者链表实现。(1)结点存储： 一维数组指针场存储： m+1个一维数组#define M 100short numM; /* M=n */short p0M, p1M, p2M, p3M;(2)结点存储： 一维数组指针场存储：二维数组#define M 100short numM; short pM4; 获得结点动态数组的程序语句tree = (TREE *)malloc(n*sizeof(TREE); 获得指针场动态数组的程序语句treei.p=(short *)malloc(m+1)*sizeof(short);结点存储采用一维数组结点存储采用动态数组指针场存储采用一维数组(3)#define M 100#define TREE struct treeTREE short num, p4; ;TREE treeM;(5)#define M 100#define TREE struct treeTREE short num, p4; ;TREE *tree;指针场存储采用动态数组(4)#define M 100#define TREE struct treeTREE short num, *p; ;TREE treeM;(6)#define M 100#define TREE struct treeTREE short num, *p; ;TREE *tree;(7) 结点存储采用链表勾链，指针场存储采用多个指针#define TREE struct treeTREEshort num;TREE *father;TREE *child1;TREE *child2;TREE *child3;；TREE *root;由指针root指向根结点，各结点间用指针形成链表勾链。(8) 结点和指针场都采用链表勾链TREEshort num；TREE *father;/* 指向父结点*/TREE *next;/* 指向同层结点*/TREE *child;/* 指向子结点*/;TREE *root; 空指针场分量的讨论在大多数的情况下，非空指针场少于指针场容量。根据指针场的存储形式，可以采取某种方式处理指针场为空的情况。 指针场的存储(1) m+1个一维数组short p0M, p1M;short p2M, p3M;(2) 二维数组short pM4;(3) (5) 一维结构数组short p4;(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 A4.4.5 树的遍历编程示例【例4-4.1】编程实现一棵五次树的遍历。假定采用链接存储方式，按标准形式存储一棵五次树，数据定义为：#define NODE struct node#define N 5NODEshortnum;NODE*subN;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 #include #include #define NODE struct node#define N 5#define M 1000NODEshort num;NODE *subN;char StringM;/* 存放输入字符串的数组 */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; isubi);printf(n); 用递归函数实现后序遍历void postOrder(NODE *node)int i;if(!node)return; for(i=0; isubi);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 stackSTACKNODE *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-subi)push(node-subi); 实现前序遍历的main函数main()input(); /* 输入括号表示*/MakeTree(); /* 生成树 */Stack = NULL; /* 清空栈 */preOrderL2(Root);printf(n); 编程要求已提供：MakeTreeL.c需要完成：OrderTreeL.c【例4-4.4】采用顺序栈实现遍历 有关顺序栈的数据定义#define M100#define EMPTY-1#define FULLM-1#define BTM0#define N5short NodeM;/* 数据值*/short PMN;/* 指针场*/short StackM;/* 栈*/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 , Nodeptr);for(i=N-1; i=0; i- )if(Pptri != EMPTY)push(pptri);参照OrderTreeL.c，编制程序：OrderTreeS.c【例4-4.5】用非递归函数实现五次树的层次遍历采用逐层进队逐层出队的方法，实现非递归的层次遍历算法：从根开始，将根进队。然后循环操作，只要队非空：首结点出队；访问(打印)该结点，将它的子结点全部进队；直到队空为止。图示树的层次遍历结果：1 2 3 4 5 64.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