数据结构之树型结构

高等学校精品课程（第2版）李云清 杨庆红 揭安全人民邮电出版社江西省高等学校精品课程揭安全E_mail:jieanquan@163.com江西师范大学计算机信息工程学院退出退出5 递归与递归程序设计在一个函数的定义中出现了对自己本身的调用，称之为直接递归；或者一个函数的定义中包含了对函数的调用，而的实现过程又调用了数调用形成了一个环状调用链,这种方式称之为间接递归。递归技术在算法和程序设计中是一种十分有用的技术，许多高级程序设计语言均提供了支持递归定义的机制和手段。试编写一个函数，在第一行打印输出1个1，在第二行打印输出2个2，……在第n行打印输出n个n。例如，当n=5时，调用该函数的输出结果为：12 23 3 34 4 4 45 5 5 5

该问题的算法为:print(intn){ inti;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)

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”);结束退出退出结论的结构相同，但规模较原问题小。足。第章 树型结构树的基本概念树类的定义树的存储结构树的遍历树的线性表示树的基本概念树是由n(n≥0)个结点构成的有限集合，n=0的树称为空树；当n≠0时，树中的结点应该满足以下两个条件：有且仅有一个特定的结点称之为根；其余结点分成个互不相交的有限集合T1,T2,……Tm，其中每一个集合又都是一棵树，称T1,T2,……Tm为根结点的子树。ABCABCDEFGHI图6.1JK1234567 89 1011 12 13 1411 12 13 14110有向树：11 12 13 14110１）有确定的根；324２）树根和子树根之间为有向关系65789和线性结构的比较线性结构 树结构第一个数据元素无前驱) 根结点无前驱)最后一个数据元素无后继) 多个叶子结点无后继其它数据元素 树中其它结点一个前驱、一个后继) 一个前驱、多个后继)退出退出基本术语结点结点的度分支的个数树的度:树中所有结点的度的最大值叶子结点:度为零的结点（终点结点）分支结点:度大于零的结点（非终端结点）从根到结点的路径：孩子结点、双亲结点、兄弟结点、祖先、子孙结点的层次:假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1退出退出树A的高为4，度为3根

D的度为3第层第层

AB C D第层 E

G H I JK 叶子的度为0

叶子 M树形表示法子树树形表示法退出退出树的深度：树中叶子结点所在的最大层次森林：是任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林有序树和无序树的区别在于：有序树和无序树的区别在于：退出退出子树之间是否存在次序关系？ABABCDEFADCBEF图6.3有序树和无序树的比较树型结构的其他表示方法：树型结构的其他表示方法：退出退出A(B(E,F),C,D(G,H(J,K),I))图的括号表示法AACBEFDGIHKJ图的嵌套集合表示法退出退出A BEFCDGHJKI(C)图6.1的凹入表示法退出退出树类的定义ADTtree{数据对象D:具有相同性质的数据元素构成的有限集合;数据关系R:如果D为空或D仅含一个元素,则R为空;否则,D中存在一个特殊的结点root,称之为根结点,其无前驱;其他结点被分成互不相交的m(m≥0)个集合,分别构成root的m棵子树;若这些子树非空,则它们的根结点rooti均称为整棵树根结点root的后继结点;而每棵子树也是一棵树,因而它们中数据元素间的关系也同样满足数据关系R。树的基本操作如下:退出退出6.2 树类的定义inittree(T) 初始化一棵树T;cleartree(T) 若树已存在将它置空使之成为一棵空树;emptytree(T) 的树是否是空树若是返回否则返回0;root(T) 返回树的根结点;child(T,a,i) 返回树中结点a的第i个子女;parent(T,a) 返回树中结点a的双亲;退出退出6.2 树类的定义degree(T,a) 返回树中结点a的度数;depth(T) 返回树的高度（深度）;choose(T,C) 返回树条件的某一个结点;addchild(T,a,i,t1) 表示在树树作为结点的第棵子树插入;delchild(T,a,i) 若树中结点的第棵子树存在则删除它;createtree(a,F) 构造一棵新树该树以为根结点、以森林中的树为子树;退出退出树类的定义equaltree(T1,T2)判断两棵树和是否相等若相等返回否则返回0;numofnode(T) 返回树个数;preorder(T) 输出树前序遍历的结果;postorder(T) 输出树后序遍历的结果;levelorder(T) 输出树层次遍历的结果;destroytree(T) 销毁一棵已存在的树。}ADTTree退出退出树的存储结构根据数据元素之间关系的不同表示方式，常用的树存储结构主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法。双亲表示法在树中，除根结点没有双亲外，其他每个结点的树中结点时，可以包含两个信息：结点的值和体现结点之间相互关系的属性 该结点的双亲。借助于每个结点的这两个信息便可唯一地表示任何一棵树。这种表示方法称为双亲表示法。#defineMAXSIZE100typedefchardatatype; 结点值的类型typedefstructnode 结点的类型*/{datatypedata;int parent; 结点双亲的下标*/}node;typedefstructtree{node treelist[MAXSIZE]; 存放结点的数组*/int length,root; /*树中实际所含结点个数及根结点的位置*/}tree;退出退出ABABCDEFGHIJK

图6.4

0dataparentdataparentA-1B0C0D0E1F1G3H3I6J6K62345678910(a)

root退出退出孩子表示法采用孩子表示法表示一棵树时，树中每个结点除了存储其自身的值之外，还必须指出其所有子女的位置，即整棵树中所有结点的相互关系是通过指明结点子女的位置来体现的，称这种表示法为孩子表示法。根据子女位置的实现方法不同，孩子表示法分为三种：指针方式的孩子表示法、数组方式的孩子表示法、链表方式的孩子表示法。1、指针方式的孩子表示法1、指针方式的孩子表示法退出退出指针方式的孩子表示法中每个结点通常包含两个域：一个是元素的值域data，另一个为指针数组，数组中的每个元素均为一个指向该结点子女的指针；一棵m度的树，其指针数组的大小即为m。#definem3 树的度数*/typedefchardatatype; 结点值的类型typedefstructnode{ 结点的类型datatypedata;structnode*child[m];/*指向子女的指针数组*/}nodetree root;其中root表示指向树根结点的指针。退出退出A∧Droot data child[0] child[1] child[2]A∧D∧B∧BC∧∧∧E∧∧∧E∧∧∧F∧∧∧∧∧∧HGI∧∧∧I∧∧∧J∧∧∧K∧∧∧图6.4中(a)图的指针方式的孩子表示法退出退出22、数组方式的孩子表示法为了查找方便，可以将树中的所有结点存储在一个一维数组中，这样每个结点子女的位置便可以通过数组的下标来体现，称这种孩子表示法为数组方式的孩子表示法。#definem3#defineMAXSIZE20typedefchardatatype;typedefstructnode{datatype int child[m];}treenode;treenodetree[MAXSIZE];int root;int length;退出退出(a)一棵树

root 0ABCDEFABCDEFGHIJKdatachild[0]child[1]child[2]A123B45-1C-1-1-1D67-1E-1-1-1F-1-1-1G8910H-1-1-1I-1-1-1J-1-1-1K-1-1-12345678910图6.4中(a)图的数组方式的孩子表示法退出退出、链表方式的孩子表示法树的链表方式的孩子表示法中，把每个结点的子女排列起来形成一个单链表，这样个结点就形成个单链表；而了查找方便，使用数组加以存储。#defineMAXSIZE50typedef char typedef struct chnode{孩子结点的类型intchild;structchnode *next;}chnodetypedefchnode*chpoint;退出退出typedefstruct {/*树中每个结点的类型datatypedata;chnode*firstchild; 指向第一个子女的指针*/}node;typedefstruct{ 树的类型nodetreelist[MAXSIZE];int length,root；}tree;退出退出root

data ABCDEFGHIABCDEFGHIJK∧∧∧∧∧∧∧98∧76∧54112345678910treelist

childnext2∧2∧3∧∧10图6.4中(a)图的链表方式的孩子表示法退出退出孩子兄弟表示法所谓孩子兄弟表示法，即在存储树中每个结点时，除了包含该结点值域外，还设置两个指针域firstchild和rightsibling，分别指向该结点的第一个子女和其右兄弟，即以二叉链表方式加以存储，因此该方法也常被称为二叉树表示法。typedefchardatatype; 树中结点值的类型*/typedefstructnode{ 树中每个结点的类型datatypedata;structnode *firstchild,*rightsibling;}node, *pnode;pnode root; 指向树根结点的指针*/退出退出∧Aroot∧A

datafirstchildrightsiblingB∧CB∧C∧D∧EF∧∧∧EF∧∧GH∧∧∧I∧J∧I∧JK∧∧图6.4中(a)图的孩子兄弟表示法退出退出树的遍历所谓树的遍历，指按某种规定的顺序访问树中的每一个结点一次，且每个结点仅被访问一次。树的遍历方式分为以下三种：（1（1）树的前序遍历：首先访问根结点，再依次按前退出退出序遍历的方式访问根结点的每一棵子树。（2（2）树的后序遍历：首先按后序遍历的方式访问退出退出根结点的每一棵子树，然后再访问根结点。退出退出（3）树的层次遍历：首先访问第一层上的根结点，然后从左到右依次访问第二层上的所有结点，再以同样的方式访问第三层上的所有结点，……，最后访问树中最低一层的所有结点。退出退出ABABCDEFGHIABCEFHIGD后序遍历的结果：BEHIFGCDA层次遍历的结果：ABCDEFGHI以下以指针方式的孩子表示法作为树的存储结构，分别实现树的各种遍历算法。1、树的前序遍历的递归实现voidpreorder(treep)/*p为指向树根结点的指针*/{inti;if(p!=NULL) 树不为空*/{printf(“%c”,p->data);for(i=0;i<m;++i)preorder(p->child[i]);//递归对各子树进行遍历}}退出退出2、树的后序遍历的递归实现voidpostorder(treep)/*p为指向树根结点的指针*/{ inti;if (p!=NULL) /*树不为空*/{for(i=0;i<m;++i)printf("%c",p->data);}}退出退出3、按前序遍历顺序建立一棵3度树的递归算法voidcreatetree(tree*p){inti;charch;if((ch=getchar())==‘ ’)else{*p=(tree)maloc(sizeof(node));产生树的根结点(*p)->data=ch;for(i=0;i<m;++i)/*按前序遍历顺序依次产生每棵子树*/createtree(&(*p)->child[i]);}}4、树的层次遍历算法4、树的层次遍历算法退出退出在树的层次遍历过程中，对于某一层上的每个结点被访问后，应立即将其所有子女结点按从左到右的顺序依次保存起来，该层上所有结点的这些子女结点正好构成下一层的所有结点，接下来应该被访问的就是它们。显然，这里用于保存子女结点的数据结构选择队列最合适，队列中的每个元素均为在排队等待访问的结点。由于树的层次遍历首先访问的是根结点，因此每次需访问一个结点时均取队头元素，访问完成队；不断重复以上过程，直到队列为空。退出退出voidlevelorder(treet){treequeue[20];存放等待访问的结点队列*/intf,r,i; 、分别为队头、队尾指针*/treep;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、树的括号表示的规则为：若树为空树，则其括号表示为空；若树结点本身；如果树由根结点和它的棵子树T1，T2，…Tm构成，则其括号表示为：A(T1的括号表示，T2的括号表示，……Tm的括号表示)其中子树的括号表示同样应该遵循以上规则。ABABCDEFGHJIA(B,C(F,G,H),D,E(J,I))图6.10、树的括号表示具有以下特点：“（”前面的元素一定为某棵树或子树的根结点，而其所有子树中的结点一定位于该“（”和与之对应的之间；任何和与之配对的之间的括号表示序列同样满足中的性质。退出退出3、树的括号表示到树的孩子表示的转换算法从左到右扫描树的括号表示；下一个符号；每当遇到右括号时，栈顶元素出栈。说明以栈顶元素为根的子树构造完毕，此时若栈为空，算法结束，否则读下一个符号；每当遇见结点，则它一定为栈顶元素的子女，将其挂到栈顶元素的某子女位置上，并读下一个符号；每当遇到号。退出退出#definem3 /*树的度数*/#defineMAXSIZE20/*树的孩子表示法对应的数组大小*/#defineBMAXSIZE50/*树的括号表示对应的数组大小*/typedefchardatatype; /*树中结点值的类型*/typedefstructnode{ 树的孩子表示法中结点的类型datatype data;int child[m];}treenode;treenodetree[MAXSIZE];树孩子表示法的存储数组*/int root; 根结点的下标*/int length; 树中实际所含结点的个数charp[BMAXSIZE]; 存放树括号表示的数组*/退出退出voidbracktotree(charp[],int*root,int*length,treenodetree[]){/*将树的括号表示法转换成树的孩子表示法*/intstack[MAXSIZE]; inttop; intk=0;j=0;*root=0;tree[j].data=p[k]; ++k;for(i=0;i<m;++i) while{if(p[k]=='('){stack[top]=j;++k;elseif(p[k]==')'){--top;ifelseelseif(p[k]==',')++k;else {++j;tree[j].data=p[k];退出退出for(i=0;i<m;++i)l=stack[top]; i=0;while(tree[l].child[i]!=-1)++i;tree[l].child[i]=j; ++k;}}*length=j;}退出退出树的层号表示设j为树中的一个结点，若为j赋予的一个整数值lev(j)满足以下两个条件：如果结点为的后件则lev(i)>lev(j)；如果结点与为同一结点的后件，则lev(i)=lev(j)。称满足以上条件的整数值lev(j)为结点j的层号。树的层号表示为：首先根据层号的定义为树中的每个结点规定一个层号，然后按前序遍历的顺序写出退出退出AABCDEFGHJI以下是上图中树的两种层号表示：①10A,20B,20C,30F,30G,30H,20D,20E,40J,40I②1A，2B，2C，5F，5G，5H，2D，2E，3J，3I树的层号表示到树的扩充孩子表示转换算法：从前往后扫描树的层号表示；若结点的层号比其前一个结点明结点位于结点的下一层且正好为的第一个子女；若结点的层号与结点的层号相等，说明两结点位于同一层，它们拥有共同的双亲；若结点的层号比结点的层号小，说明结点i与结点的某个祖先结点互为兄弟，于是应该沿着的双亲向树根方向寻找到它们共同的双亲。退出退出#definem3#defineMAXSIZE20typedefchardatatype;typedefstructnode{datatype int child[m];intparent;}treenode;typedefstruct{ 层号表示法中结点的类型datatypedata;intlev; 存储结点的层号*/}levelnode;退出退出treenodetree[MAXSIZE];int root;int length;levelnodeltree[MAXSIZE];退出退出voidleveltotree(intlength,levelnodeltree[],int*root,treenodetree[]){/*将树的层号表示法转换成树的扩充孩子表示法*/inti,j,k;for(i=0;