摘要
提出了一种基于前序和中序遍历序列恢复二叉树的解法,算法以数学公式形式呈现,反映了建树过程中相关数据变化的一般规律,具备数学上的引用透明性,由此能机械获得非递归程序和循环不变式,并进行了正确性证明.通过简单变换,获得了后序+中序、前序+后序恢复二叉树的可信算法.实验效果表明了该解法的有效性.
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.
出处
《江西师范大学学报（自然科学版）》
CAS
北大核心
2013年第3期268-272,共5页
Journal of Jiangxi Normal University(Natural Science Edition)
基金
江西省教育厅科技课题(GJJ09142)资助项目
关键词
状态变迁
二叉树遍历
恢复二叉树
循环不变式
state transformation
binary tree traversal
reconstructing tree
loop invariant
