二叉树的两种表示方法及相互转换.pdf

《二叉树的两种表示方法及相互转换.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、总第306期

2、Ir敏又f‘Tota1．3062015年2月(下)TheScienceEducationArticleConectsFebruary2015(C)二叉树的两种表示方法及相互转换杨芳蔡式东(深圳大学计算机与软件学院广东·深圳518060)中图分类号：G642文献标识码：A文章编号：1672—7894(2015)06—0089—02摘要数据结构是计算机院校学生的专业基础课，该课程整个编程用到的数据类型声明如下：的难点之一就是二叉树。本文探讨了二叉树的两种表示方typedefstructBiTNode／／链表结构中的结点表示法及

3、其相互转换，为学生学>-7基于二叉树的应用程序打好fchardata；／／记录该结点的数据，如图a中了基础。的ABCDED关键词数据结构二叉树表示方法相互转换BiTNode*lchild。*rchild；／／该结点的左孩子、右孩子TwoTypesofMethodstoExpressBinaryTreeandTheir指针MutualTransformation／／YangFang，CaiShidonglBiTNode，BinTree；AbstractDatastructureisaprofessionalfoundationcotn's

4、eforBinTreemot；／／链表结构中的根结点studentsofcomputercollegesandoneofthedifiqcultpointsofthe#defineMaxsize30／／数组的长度courseisbinarytree．Thispaperexplorestwotypesofmethodstochart[Maxsize]；／／顺序结构使用的数组expressbinarytreeandtheirmutualtransformation，aimingtolayintlen=O；／／二叉树的元素总数afoundat

5、ionforapplicationsbasedonbinarytree．Keywordsdatastructure；binarytree；expressionmethods；mutual1顺序结构transfonnation对于给定结构的二叉树，如图a所示，当我们想用顺序结构保存时，要先转换成如图b所示的完全二叉树(补充的数据结构是计算机专业的专业基础课，也是本专业公结点值定义为’0’)后，才能进行保存。认的最难的一门课程。该课程的重点难点之一就是树。二叉树是研究树的入门切人点。对于基于二叉树的各种应用而言，如何在计算机中输入二叉树是首

6、要考虑的问题。本文研究二叉树的两种基本表示方法，并且讨论了两种结构如何相互转换。二叉树有两种表示方式：一种是顺序结构(用数组表示)，一种是链表结构(用链表表示)，下面我们以实例来介绍这两种表示方法及其相互转化的相关程序代码。图b由图a转换的完全二叉树此时用户的输人数据为：6ABC0DE(6为结点个数)，程序的主要代码为：voidCreateArray0{／／构建顺序表inti；charch；InitArray0；／／数组初始化，将数组t的内容清空为’0’，图a原始二叉树具体代码略；作者简介：杨芳(1975一)，女，湖南益阳人，讲师；蔡式

7、东(1959__)，女，通讯作者，副教授，E—mail：caisd@SZU．edu．cn。89教改教法f／／构造二叉树Tif(i<=n&&s[i】!=一0){T=newBiTNode；T->data=s【iJ；T一>lchild=NULL；T一>rchild=NULL；／／创建结点TCreateBiTreeFromArray(T一>lchild，n，2"i，s)；，／构造左子树CreateBiTreeFromArray(r->rchild，n，2"i+1，s)；／／构造右子树”／／CreateBiTree图c由图a转换的二叉树。将左右孩

8、子为null的结点补充完整4链表结构转换成顺序结构cin>>len；链表结构转换成顺序结构也要解决两个问题：1)如何f0r(i=1；i<=len；i++)得知数据的总数(由最后一个结点在数组中的位置决定)；{cin>>ch；2)当前访问的结点要放到对应的顺序结构的哪个位置。程t[i]=ch；序的主要代码为：ljvoidCre~e(BinTree＆T，inti,char*s)／／链表结构转换成2链表结构顺序结构对于给定结构的二叉树，如图a所示，当我们想用链表(结构保存时，要先转换成如图c所示的二叉树后(将左右孩if(T){子为空的结点补充

9、完整，结点数据值定义为’0’)，然后利用sIil=T一>data；len=i；／／最后输出的结点下标i，就是真实对图c中的二叉树做先序遍历得到的序列建二叉树。的数据长度此时用户的输入数据为：11AB0D00