一种由遍历序列构造二叉树的改进算法

An improved algorithm for constructing two binary trees by traversing sequences

针对现有构造二叉树的算法无法适用于具有相同元素的遍历序列,提出了一种解决该问题的递归算法。该种算法以现有的递归算法为基础,通过引入遍历序列的标志序列,依据标志序列中元素之间的关系,从理论上证明了三种由遍历序列构造二叉树的算法都具有递归性。根据遍历序列构造二叉树的递归原理,设计了三种不同的由遍历序列构造二叉树的递归算法。通过算例仿真表明,使用笔者设计的算法可为具有相同元素的遍历序列构造二叉树。

In view of the present algorithm can not be applied to construct the binary tree by using the traversal sequence which has the same elements,this paper presents a recursive algorithm to solve the problem. Based on the existing recursive algorithm,this algorithm introduces the symbol sequence of the traversal sequence. According to the relationship among the elements in the symbol sequence,the three algorithms are proved theoretically to be recursive for using the traversal sequences to construct the binary tree. Based on the recursive principle of constructing the two binary tree by the travel sequences,three different recursive algorithms are designed to construct the binary tree. Simulation results show that the algorithm can be used to construct the two binary tree by using the traversal sequences in which there are the same elements.