摘要
文章针对如何由二叉树的遍历序列来唯一确定二叉树的问题,提出了用两种遍历序列唯一确定一棵二叉树的方法。已知先序遍历和中序遍历或者已知后序遍历和中序遍历可以唯一确定一棵二叉树,但已知后序遍历和先序遍历就不能唯一确定了,只有当要确定的树没有度为一的结点时,所确定的二叉树才是唯一的。对此文中给出了说明,并利用Turbo C实现了相应的算法。.
This paper proposed an approach to confirm a unique binary tree by traversal sequence. The approach is based on confirming. a unique binary tree by two kinds of traversal sequences. The preorder traversal sequence and the inorder traversal sequence or the postorder traversal sequence and the inorder traversal sequence can confirm the only one binary tree. However, the postorder trav- ersal sequence and the preorder traversal sequence cannot confirm the only one binary tree. The preorder traversal sequence and the postorder traversal sequence can confirm a unique binary tree whose degree is zero or two. The approach has been explained in this paper. The corresponding algorithm has been implemented in Turbo C.
出处
《南昌航空大学学报（自然科学版）》
CAS
2010年第1期55-59,共5页
Journal of Nanchang Hangkong University(Natural Sciences)
关键词
先序遍历
中序遍历
后序遍历
二叉树
preorder traversal
inorder traversal
postorder traversal
binary tree
