《数据结构之树型结构(pdf 61页)》由会员分享，可在线阅读，更多相关《数据结构之树型结构(pdf 61页)（62页珍藏版）》请在金锄头文库上搜索。
1、高等学校精品课程（第2版）李云清杨庆红揭安全人民邮电出版社江西省高等学校精品课程揭安全E_mail: 江西师范大学计算机信息工程学院5递归与递归程序设计在一个函数的定义中出现了对自己本身的调 用，称之为直接递归；或者一个函数p的定义中包含了对函数q的调用，而q的实现过程又调用了p，即函数调用形成了一个环状调用链, 这种方式称之为间接递归。递归技术在算法和程序设计中是一种十分有用的技术，许多高级程序设计语言均提供了支持递归定义的机制和手段。退出试编写一个函数，在第一行打印输出1个1，在第二行打印输出2个2， 在第n行打印输出n个n。例如，当n=5时，调用该函数的输出结果为：12233344445
2、5555该问题的算法为: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
3、”,4)printf(“n”);for(i=1;i=5;i+) printf(“%d”,5)printf(“n”);结束结论n 根据所求解问题的性质，将原问题分解成若干子问题，这些子问题的结构与原问题的结构相同，但规模较原问题小。n 子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合成原问题的解。递归调用时， 参数的修改最终必须保证递归出口得以满足。退出第6章树型结构 树的基本概念 树类的定义 树的存储结构 树的遍历 树的线性表示6.1 树的基本概念树是由n (n0)个结点构成的有限集合，n=0 的树称为空树；当n0时，树中的结点应该满足以下两个条件：(1) 有
4、且仅有一个特定的结点称之为根；(2) 其余结点分成m(m0)个互不相交的有限集合T1,T2,Tm，其中每一个集合又都是一棵树，称T1, T2,Tm为根结点的子树。ABCDEFGHI图6.1JK123456789101112131411121314110有向树 ：） 有确定的根；324） 树根和子树根之间为有向关系65789和线性结构的比较线性结构树结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继) 其它数据元素树中其它结点(一个前驱、一个后继)(一个前驱、多个后继)基本术语结点:数据元素 + 若干指向子树的分支结点的度:分支的个数树的度:树中所有结点的
5、度的最大值叶子结点:度为零的结点（终点结点）分支结点:度大于零的结点（非终端结点） 从根到结点的路径：孩子结点、双亲结点、兄弟结点、祖先、子孙结点的层次:假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1退出退出树A的高为4，度为3根D的度为3第1层第2层ABCD第4层EFGHIJKL叶子的度为0叶子M树形表示法(a) 子树树的深度：树中叶子结点所在的最大层次 森林：是m（m0）棵互不相交的树的集合任何一棵非空树是一个二元组Tree = （root，F）其中：root被称为根结点，F被称为子树森林退出有序树和无序树的区别在于：子树之间是否存在次序关系？ABCDEFADCBEF图6.3
6、 有序树和无序树的比较退出树型结构的其他表示方法：A(B(E,F),C,D(G,H(J,K),I)(a) 图6.1的括号表示法ACB EFD GIHKJ(b) 图6.1的嵌套集合表示法退出A BE F CDGHJKI(C)图6.1的凹入表示法退出6.2 树类的定义ADT tree 数据对象D:具有相同性质的数据元素构成的有限集合;数据关系R:如果D为空或D仅含一个元素,则R为空;否则,D中存在一个特殊的结点root,称之为根结点,其无前驱;其他结点被分成互不相交的m(m0) 个集合,分别构成root的m棵子树;若这些子树非空, 则它们的根结点rooti均称为整棵树根结点root的后继结点;而每
7、棵子树也是一棵树,因而它们中数据元素间的关系也同样满足数据关系R。树的基本操作如下:退出6.2树类的定义（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的双亲;退出6.2树类的定义（7） degree(T,a)返回树T中结点a的度数;（8） depth(T)返回树T的高度（深度）;（9）
8、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中的树为子树;退出6.2 树类的定义（13） equaltree(T1,T2) 判断两棵树T1和T2是否相等,若相等,返回1;否则返回0;（14） numofnode(T)返回树T中所含结点的个数;（15） preorder(T)输出树T前序遍历的结果;（16） postorder(
9、T)输出树T后序遍历的结果;（17） levelorder(T)输出树T层次遍历的结果;（18） destroytree(T)销毁一棵已存在的树T。 ADT Tree退出6.3 树的存储结构根据数据元素之间关系的不同表示方式，常用的树存储结构主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法。6.3.1 双亲表示法在树中，除根结点没有双亲外，其他每个结点的 双亲是唯一确定的。因此，根据树的这种性质，存储树中结点时，可以包含两个信息：结点的值data和体现结点之间相互关系的属性该结点的双亲parent。借助于每个结点的这两个信息便可唯一地表示任何一棵树。这种表示方法称为双亲表示法。退出#defi
10、ne MAXSIZE 100typedef char datatype;/*结点值的类型*/ typedef struct node/*结点的类型*/datatype data;intparent;/*结点双亲的下标*/ node;typedef struct treenodetreelistMAXSIZE;/*存放结点的数组*/ intlength, root ;/* 树中实际所含结点的个数及根结点的位置*/ tree;退出ABCDEFGHIJK(a) 一棵树图6 .40dataparentA-1B0C0D0E1F1G3H3I6J6K612345678910(b) (a)图的双亲表示法roo
11、t6.3.2 孩子表示法采用孩子表示法表示一棵树时，树中每个结点除了存储其自身的值之外，还必须指出其所有子女的位置，即整棵树中所有结点的相互关系是通过指明结点子女的位置来体现的，称这种表示法为孩子表示法。根据子女位置的实现方法不同，孩子表示法分为三种：指针方式的孩子表示法 、数组方式的孩子表示法、链表方式的孩子表示法 。退出1、指针方式的孩子表示法指针方式的孩子表示法中每个结点通常包含两个域：一个是元素的值域data，另一个为指针数组，数组中的每个元素均为一个指向该结点子女的指针；一棵m度的树，其指针数组的大小即为m。退出#define m 3/*树的度数*/ typedef char datatype;/*结点值的类型*/ typedef struct node/*结点的类型*/ datatype data;struct node *childm; /*指向子女的指针数组*/ node *tree; treeroot;其中root表示指向树根结点的指针。ADrootdatach
