基于遍历序列恢复二叉树的新解法及其证明  

A New Solution with Proof for Reconstructing a Binary Tree from Its Traversals

作　　者：化志章[1] 

机构地区：[1]江西师范大学计算机信息工程学院,江西南昌330022

出　　处：《江西师范大学学报（自然科学版）》2013年第3期268-272,共5页Journal of Jiangxi Normal University(Natural Science Edition)

基　　金：江西省教育厅科技课题(GJJ09142)资助项目

摘　　要：提出了一种基于前序和中序遍历序列恢复二叉树的解法,算法以数学公式形式呈现,反映了建树过程中相关数据变化的一般规律,具备数学上的引用透明性,由此能机械获得非递归程序和循环不变式,并进行了正确性证明.通过简单变换,获得了后序+中序、前序+后序恢复二叉树的可信算法.实验效果表明了该解法的有效性.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.

关 键 词：状态变迁 二叉树遍历 恢复二叉树 循环不变式 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]