先序和后序序列恢复二叉树的非递归算法

Non-recursive Algorithm of Restoring a Binary Tree by Preorder Traversal and Postorder Traversal

摘要: 针对先序和后序序列不能唯一恢复一棵二叉树的问题,文章提出先序和后序序列在有些情况下是可以唯一恢复一棵二叉树的.即在结点的度只为0或2的二叉树中是可以由先序和后序序列唯一恢复的.对此文中给出了说明,并利用Visual C++ 6.0实现了相应的算法.

Abstract: There has been a conclusion that the preorder traversal sequence and the postorder traversal sequence cannot restore a unique binary tree in the first literature.In the paper it has been pointed out and proved that preorder traversal sequence and the postorder traversal sequence can restore a unique binary tree under certain conditions.That is,the degree of binary tree is zero or two.The viewpoint has been illuminated in this paper.The non-recursive algorithm has been implemented in Visual C++ 6.0.