[1]化志章.基于遍历序列恢复二叉树的新解法及其证明[J].江西师范大学学报(自然科学版),2013,(03):268-272.
　HUA Zhi-zhang.A New Solution with Proof for Reconstructing a Binary Tree from Its Traversals[J].Journal of Jiangxi Normal University:Natural Science Edition,2013,(03):268-272.
点击复制

基于遍历序列恢复二叉树的新解法及其证明()
分享到：

《江西师范大学学报》（自然科学版）[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2013年03期
页码:
268-272
栏目:
出版日期:
2013-05-01

文章信息/Info

Title:
A New Solution with Proof for Reconstructing a Binary Tree from Its Traversals
作者:
化志章
江西师范大学计算机信息工程学院,江西南昌,330022
Author(s):
HUA Zhi-zhang
关键词:
状态变迁; 二叉树遍历; 恢复二叉树; 循环不变式
Keywords:
state transformation; binary tree traversal; reconstructing tree; loop invariant
分类号:
TP311.1
文献标志码:
A
摘要:
提出了一种基于前序和中序遍历序列恢复二叉树的解法,算法以数学公式形式呈现,反映了建树过程中相关数据变化的一般规律,具备数学上的引用透明性,由此能机械获得非递归程序和循环不变式,并进行了正确性证明.通过简单变换,获得了后序+中序、前序+后序恢复二叉树的可信算法.实验效果表明了该解法的有效性.
Abstract:
A new solution for reconstructing a binary tree based on the pre-order and in-order traversal is proposed.Its algorithm is mathematical formula,which reflecting the data change rule about the reconstructing binary tree process,and with referential transparency on the mathematical.Then,non-recursive abstract program and its loop invariant are obtained mechanically according to the formula,and their correctness are proved formally.And through a simple transformation,the trusted algorithms using post-order + in-order traversal,and pre-order + post-order traversal,are obtained.Experimental results show the effectiveness of this solution.

参考文献/References:

[1] Knuth D E.The art of computerprogramming volume 1:fundamental algorithms [M].3rd Edition.New York:Addison Wesley,1997.
[2] Mu S C,Bird R S.Rebuilding a tree from its traversals:a case study of program inversion [EB/OL].
[2012-10-11].http:∥citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.1166.
[3] Burgdorff H A,Jojodia S,Springsteel F N,et al.Alternative methods for the reconstruction of tree from their traversals [J].BIT,1987,27(2):134-140.
[4] Gen-Huey Chen,Yu M S,Liu L T.Two algorithms for constructing a binary tree From its traversals [J].Information Processing Letters,1988,28(6):297-299.
[5] Andersson A,Carlsson S.Construction of a tree from its traversals in optimal time and space [J].Information Processing Letters,1990,34(1):21-25.
[6] Mäkinen E.Constructing a binary tree efficiently from its traversals [J].International Journal of Computer Mathematics,2000(1):75.
[7] 唐自立.基于遍历序列的唯一确定树或二叉树的方法 [J].小型微型计算机系统,2001,22(8):985-988.
[8] 唐自立.基于遍历序列的构造严格二叉树的算法 [J].苏州大学学报:自然科学版,2010,26(3):40-43.
[9] Arora N,Tamta V K,Kumar S.Modified non-recursive algorithm for reconstructing a binary tree [J].International Journal of Computer Applications,2012,43(10):25-28.
[10] 化志章,揭安全,杨庆红.树非递归遍历统一的新解法及其形式证明 [J].江西师范大学学报:自然科学版,2010,34(2):123-127.
[11] Gries D.The science of programming [M].New York:Springer-Verlag,1981.
[12] Dijkstra E W,Scholten C S.Predicate calculus and program semantics [M].New York:Springer-Verlag,1990.

备注/Memo

备注/Memo:
江西省教育厅科技课题(GJJ09142)
更新日期/Last Update: 1900-01-01