【doc】一种树的存储结构

【doc】一种树的存储结构 一种树的存储结构 第27卷第1期 2000年2月 南太学(自然科学版) JournalofHunanUniversity(NaturalSciencesEdition) VoI.27.No】 Feb.2000 文章编号j1000—2472(2000)01—010904 ,0一f/一种树的存储结构 范年柏,蒋盛益. (1.湖南大学应用数学系,湖南长沙410082;2.衡阳师范学院计算机系湖南衡阳 421000) 摘要:采用静志敷组的方式给出树的一种存储结构,并给出这种存储 结构下的几种常用运算的C语言程序.这种存储结构避开j链式存储结构 中链域个数不定的困难,容易用FoxBASE等关系型数据库来实现相应的 蚪 关键词:树;妻.垂丝童;丝竺兰墨一/L叶j''7(F',矿> 中图分类号:TP31l_12一文献码:A ——— 一 AkindofStorageStructureofTree FANNian—bai.JIANGSheng—yi. (1.DeptofAppliedMathematics,HunanUniv,Changsha410082,China; 2.DeptofComputer,HengyangTeacher'sCo[1ege,Hengyang421000,China) Abstract:Thispaperobtainedakindofstoragestructureoftreebyusingstaticar_ rays,andhasgivenoutsomealgorithmbasedonthisstoragestructurebyClanguage. Thisstoragestructureavoidsthedifficultythatthenumberoflinkedrangeinlinkedlist isindefinite,anditiseasytorealizthealgorithmunderrelationshipdatabasessuchas. FoxBASE,alsothisstoragestructurecanuseunitymethodtodealwithbinarytreeand tree. Keywords:tree;storagestructure;operationoftree 1存储结构 树是一种层次结构,通常采用链式存储结构,但当树的度较大,且各结点的度差异较 大时不适宜.今采用顺序存储结构来存储树,每个结点设置3个域:值域,父结点指针域和 子结点指针域,结构如下: 叵工丑三二] 其中data示值域,用于存储结点的数据元素;parent表示父结点的编号;sons表示用 警鍪是曹誉萎言学基垒资助项目.... 作者筒舟范年柏'】96Z).男,湖南澧县^,湖南大学讲师 11O湖南大学(自然科学版) "/"分黼的子结点的编号串.如 [[工] 表示结点的数据为"B.,,父结点为1号结点.子结点有3, 4,10三个结点.整棵树则利用一维静态数组表示,由于 在这种存储结构中结点之间的逻辑关系是通过编号联接 的,所以各结点在数组中占用的单元可按照任意次序安 排.为方便,结点编号从1开始,树根结点的编号为l,其 父结点编号为0.若按照从上到下,从左往右的次序依次 给各结点分配存储单元.则得到图l所示的树的存储映 像如表1所示,其中指针域为空的结点为叶结点. 衰1围1对应的存储映德 国1一埠深度为5的树 编号parentdatasonsparentdataSODS 10A2/11/86M 21B3/~/1094J 32D1o2F 42E5/6/9/111C12/ 54H1211G13/ 64I7/8/1312K14/ 76L1413N 若采用FoxBASE等关系型数据库处理,则每个结点的信息作为一条,每个记录 包含三个字段,编号即为记录号.下面用C语言描述结点类型及树的运算,定义结构体类 型tree及静态结点数组t. structtree {charparent[4]; chardata{ charsons[3o3; }; struettreetE.o3; 这里n0为结点的最多个数.下面讨论在这种存储结构下,树的生成,遍历,插入,删除 等运算的算法,具体算法作者均用c程序给予了描述,限于篇幅,本文从略. 2树的生成 树的输入方法不同.生成算法也不同,这里介绍两种生成算法 2.1采用广义表的方式输人树 树的广义表书写规则为: ?每棵树的根结点作为由子树构成的表的名字放在表的前面 第1期范年柏等:一种树的存储结构 ?表中各元素放在括号内,并用逗号分隔; ?为处理方便起见,广义表以一个特殊的符号@结尾. 图1中的树用广义表表示为:A(B(D,E(H,I(L,M),J)F),C(G(K(N))))@.采用广 义表表示树时,按广义表输入顺序从左往右给各结点编号,结点中parent域,sons域的值 都自动填入.算法的基本思想为: ?输入广义表中的一个字符; ?若输入的是字母(假设以字母作为结点的值),则表明是结点的值.结点数i增加1. 并将该字符作为结点i的值,结点i的sons域置为空.若i>1,则结点i的父结点为栈顶对 应编号j,将i接到结点j的SOnS域后; ?若遇到的是左括号,则表明是子表的开始,将结点i进栈; ?若遇到的是右括号,则表明子表结束,将栈顶编号弹出; ?重复?,?,直到遇到字符@,虽后将结点1的parent域置为0 2.2采用逐个结点输人结点信息的方式鞴人树 在这种方式中,结点由用户事先编号(为简单起见,编号从1开始,连续编号),逐点输 入各结点的parent域及data域的值,sons域的值自动填入.实际输入时应从上至下逐层 输入,基本步骤是重复如下?,?.直至所有结点信息输入完为止. ?输入结点i的信息:父结点编号j,结点值域x; ?将结点i的data域置为x,sons域置为空; ?将i连接到结点j的soils域后 3树的遍历 3.1树的层次遍历(广度优先遍历) 层次遍历:先访问第一层结点(即树根结点),再从左往右访问第二层结点,依次按层 次访问,直到访问完虽深一层结点为止. ?访问根结点,将其子结点串保存到strl中; ; ?str2一一 ?顺序访问strl中指定的结点,并依次将它们的子结点串链接到str2中; ?将str2作为新的strl; ?重复?,?直到str2为空. 3.2树的先根遍历(深度优先遍历) 先根遍历先访问根结点,然后从左往右依次先根遍历每棵子树 ?i一1,flag=1,top一0} ?访问第i个结点; ?若i结点的sons域非空,则str/=tEi3SO125;若i结点的sons域空而栈非空,则弹 出栈顶元素作为str1.若i结点的sons域空且栈亦空,则置flag为0; ?将i指向strl中第一个编号,余下子结点串域作为strl,若strl非空,则将其压栈; ?重复?,?直到flag为0. 湖南大学(自然科学版)2000蓝 4树的输出 按广义表的形式输出树. ?i一1,top一0,flag=1; ?输出结点i的值域; ?若结点i的sons域为空.则转?,否则i不是叶结点,输出(",并将strl改为 结点i的$oixs域,转?; ?若栈非空.则弹出栈顶元素给str1.若strl为空,则转?,否则说明还有右兄弟,输 出","; ?重复输出")"并弹出栈顶元素给strl,直到strl非空或栈为空,若strl非空,则输 出",,否则输出")"; ?若strl与栈都为空,则置flag=0; ?若strl非空,则将i指向strl中的第一个编号,strl改为指向下一个编号,并将 strl压栈; ?重复?,?直到flag为0. 5树的插人 在树中插入一个结点采用树的第二种生成算法,输入待插入结点的信息(结点号i,父 结点号j,结点值域x). 6树的删除 从树中删除一个结点的基本思想是删除某个结点P时,其子结点全部作为P的父结 点的子结点.基本步骤如下. ?输入待删除结点的编号; ?将结点i的父结点编号记为P,$oixs域记为strl; ?将strl中各编号结点的父结点编号改为P; ?将P的sons域中的P用结点i的sons域的值取代. 参考文献: [1徐孝凯.数据结构简明教程EMJ.北京:清华大学出版社,1995. [2]严蔚敏.数据结构EMJ.北京:清华大学出版社,1992.