怎样由遍历序列确定二叉树

Determining Binary Tree with Traversal Sequence

在文 [1 ]至文 [4]中都介绍了遍历一棵二叉树的三种方法 :先序遍历、中序遍历和后序遍历 .每棵二叉树的先序遍历序列、中序遍历序列和后序遍历序列都是唯一的 .但是不同的二叉树的先序遍历序列或中序遍历序列或后序遍历序列有可能是相同的 .就如我们已知一个关系要求能求出它的关系矩阵 ,已知一个关系的关系矩阵也能求出关系矩阵所表示的关系一样 ,要求我们不但能从二叉树求它的遍序序列 ,而且能从二叉树的遍历序列求出它们所表示的二叉树 .在文 [1 ]中只指出 :给定结点的先序序列和中序序列可唯一确定一棵二叉树 .但文 [1 ]没有给出证明 .本文指出了由后序遍历序列和中序遍历序列也可唯一确定一棵二叉树 。

Essay to essay all introduce the three ways of traversing binary tree: pre order; in order; post order. The pre order, in order and post order traversal of every binary tree are unique, but those of different binary trees may be identical. Just like if a relation given, the relation matrix can be obtained, and if the matrix given, the relation can be retrieved, it is required that the traversal sequence is obtainable out of the binary tree and the binary tree is also obtainable on the basis of traversal sequence. In essay it is pointed out that a given node pre order and in order traversal sequence uniquely determined a binary tree, but essay gives no proof. It is pointed out and proved post order and in order traversal sequence also determine a unique binary tree, proof demonstration given.