admin 管理员组文章数量: 1086019
2024年9月13日发(作者：关于异步电动机的描述正确的是)
电火理＿Ｔ
２０１０年３月 Ｓｔｕｄｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ ａｔ ＲＴＶＵ． 第１期 总第２４２期
利用遍历序列还原二叉树算法的研究与实现
李丽姝
辽阳职业技术学院（辽阳１ｌ１００４）
摘要二叉树是一种常用的数据结构，根据二又树的遍历规律可以还原出相应二叉树，对还原过
程进行分析并给出Ｃ语言实现程序。
关键词二叉树遍历递归
二叉树是一种常用的数据结构，它在计算机
处理领域有着广泛的应川。二义树最基本的运算
就是遍历。根据访问根结点、左子树、右子树的
１ 由前序和中序遍历序列还原二叉树
顺序，二叉树的遍历有三种，前序遍历、中序遍
用 ；分别表示前序序列的第一个、最后一
历和后序遍历。前序遍历的顺序为：ＤＬＲ，即先
个元素，川ｋ，ｈ分别表示中序序列的第一个、
根结点，然后左子树、右子树，故也称先序遍历；
最后一个元素。
中序遍历顺序为：ＬＤＲ，先左子树，然后根结点、
在前序序列中的第一个结点即为二义树的
右子树；后序遍历顺序为：ＬＲＤ，先左子树，然 根结点，其位置为ｉ。在中序序ｐ－０中找到根结点
后右子树，最后根结点。
位置（ｍ），以确定左右子树上的结点（ｍ左边为
由前序遍历 １中序遍历序列或者由中序遍
左子树结点，右边为右子树结点）。然后再到前
历和后序遍历序列都可以唯一确定一棵二义树，
序序列中去确定左右子树的根：若ｍ为中序序
所以我们可以根据遍历序列还原出对应的二义
列中第一个元素，则根结点左子树为空，否则递
树。根据遍历序列还原一棵二义树的基本过
归还原左子树，左子树结点在前序序列中的位置
为：先还原根结点，再还原左子树和右子树，可 为ｉ＋ｌ－－）ｉ＋ｍ．ｋ，在中序序列中位置为ｋ ｍ．１；
以由前序或后序序列确定根结点，然后再利川中
若ｍ为中序序列的最后一个元素（位置为ｈ），
序序列确定左右子树中的结点。 则右子树为空，否则递归还原右子树，右子树结
下面给出用Ｃ语言描述的算法。假设二二义
点在前序中位置为ｉ＋ｍ．ｋ＋ｌ ｉ，中序序列中位置
树的前序序列、后序序列和中序序列分别存放在 为ｍ＋ｌ ｍ．ｈ。 序实现如 ：
一
维数组ｐｒｅ［］、ｐｏｓｔ［】与ｉｎ［］中，并假设
ＢｔｒｅｅＮｏｄｅ ｐｒｅｉｎｔｏｔｒｅｅ（ｃｈａｒ ｐｒｅ［】，ｃｈａｒ
叉树各结点的数据值均不相同。二义树结点类型
ｉｎ［］，ｉｎｔ ｉ，ｉｎｔ ｊ，ｉｎｔ ｋ，ｉｎｔ ｈ）
定义为：
｛ｉｎｔｍ；
ｓｔｒｕｃｔ ＢｔｒｅｅＮｏｄｅ
ＢｔｒｅｅＮｏｄｅ ｐ；
｛ｃｈａｒ ｄａｔａ；
ｐ：（ＢｔｒｅｅＮｏｄｅ ）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ＢｔｒｅｅＮｏｄｅ））；
ｓｔｒｕｃｔ ｎｏｄｅ＊ｌｃｈｉｌｄ，＊ｒｃｈｉｌｄ；
ｐ一＞ｄａｔａ＝ （ｐｒｅ＋ｉ）；
５４． 电人理＿Ｔ 总第２４２期
ｅｒ＝ｋ；
ｗｈｉｌｅ（ （ｊｎ＋ｍ）！＝ （ｐｒ．ｅ＋ｉ））
ｍ＋＋：
ｉｆ（ｍ＝＝ｋ、
ｐ－＞ｉｃｈｉｌｄ＝ＮＵＬＬ；
ｅｌｓｅ
ｐ－＞ｌｅｈｉｌｄ＝ｐｒｅｉｎｔｏｔｒｅｅ（ｐｒｅ，ｉｎ，ｉ＋ｌ，ｉ＋ｍ－ｋ，ｋ，ｍ一１）
，
ｉｆ（ｍ：＝１）
ｐ－＞ｒｃｈｉｌｄ＝ＮＵＬＬ；
ｅｌｓｅ
ｐ－＞ｒｃｈｉｌｄ＝ｐｒｅｉｎｔｏｔｒｅｅ（ｐｒｅ，ｉｎ，ｉ＋ｍ—ｋ＋ｌ，ｊ，ｍ＋ｌ，Ｊ）
，
ｒｅｔｕｒｎ ｐ；／／还原出来的二：义树，根结点指针
为Ｐ，作为返同值返同。
）
２ 由后序和中序遍历序列还原二叉树
与ｌ过程相似，刚ｉ，ｉ分别表示后序序列的
第一个、最后一个元素，用ｋ，ｈ分别表示中序序
列的第一个、最后一个元素。
在后序序列中的最，『斤一个结点即为二义树
的根结点，其位置为ｉ。在中序序列中找到根结
点位置（ｍ），以确定左右子树上的结点（ｍ左边
为左子树结点，右边为右子树结点）。然后再剑
后序序列中去确定左右子树的根：若ｍ为中序
序列中第一个元素，则根结点左子树为空，否则
递归还原左子树，左子树结点在后序序列中的位
置为ｉ ｉ＋ｍ．ｋ．１，在中序序列中位置为ｋ ｍ一１；
若ｍ为中序序列的最，『ｉ彳一个元素（何置为ｈ），
则右子树为空，否则递！Ｊ１＝还原右子树，右子树结
点在后序中位置为ｉ＋ｍ．ｋ ｉ．１，中序序列中位置
为ｍ＋ｌ ｈ。 序段代码如下：
／ 函数ＢｔｒｅｅＮｏｄｅ ｐｏｓｔｉｎｔｏｔｒｅｅ（ｃｈａｒ ｐｏｓｔ【】，
ｃｈａｒ ｉｎ［］，ｉｎｔ ｉ，ｉｎｔｊ，ｉｎｔ ｋ，ｉｎｔ ｈ）部分代码 ／
ｐ一＞ｄａｔａ （ｐｏｓｔ＋ｊ）；
ｅｒ＝ｋ；
ｗｈｉｌｅ（ （ｉｎ＋ｍ）ｌ＝ （ｐｏｓｔ＋ｊ））
ｍ＋＋：
ｉｆ（ｍ＝＝ｋ
ｐ－＞ｌｃｈｉｌｄ＝ＮＵＬＬ；
ｅｌｓｅ
ｐ－＞ｌｃｈｉｌｄ＝ｐｏｓｔｉｎｔｏｔｒｅｅ（ｐｏｓｔ，ｉｎ，
ｉ，ｉ＋ｍ—ｋ—Ｉ，ｋ，ｍ－Ｉ）；
ｉｆ（ｍ＝＝ｈ）
ｐ－＞ｒｃｈｉｌｄ＝ＮＵＬＬ；
ｅｌｓｅ
ｐ－＞ｒｃｈｉｌｄ＝ｐｏｓｔｉｎｔｏｔｒｅｅ（ｐｏｓｔ，ｉｎ，
ｉ＋ｍ－ｋ，ｊ一１，ｍ＋ｌ，ｈ）；
３总结
二二义树的定义本身就是个递归的定义，所以
二叉树遍历和还原也可采 递归的方式进行，算
法容易理解，若采Ｊ１ｊ非递归的方法虽也可实现，
但是算法会复杂得多，不易理解，算法 写也很
困难。所以二义树相关的运算不妨首先考虑递归
方法。
参考文献
ｆ１］许卓群．数据结构．北京：中央广播电视大学ｆ｛Ｊ社．２００２．
【２】谭浩强，张 温．ｃ，ｃ＋＋语言程序设计教程．北京：高等教
育Ⅲ版礼．２００１．
【３】郝ｌ５ｎ Ｉ５几．二叉树遍历方泫的研究和心用．内江科
技．２００８（４）．
（责任编辑：齐婷婷）
版权声明：本文标题：利用遍历序列还原二叉树算法的研究与实现 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1726230198a929522.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论