基于遍历序列恢复二叉树的新解法及其证明
A New Solution with Proof for Reconstructing a Binary Tree from Its Traversals

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