构造二叉树的两个改进算法

Two Improved Algorithms for Constructing Binary Tree

在数据结构中,已知一棵二叉树的先序序列和中序序列,可唯一确定此二叉树。本文在分析建立二叉树经典算法的时间复杂度的基础上,给出了两个改进算法:①利用哈希函数,使得改进后的算法在最差情况下,时间复杂度由O(n2)降为O(n);②利用栈和控制输入的结点序列构造二叉树,时间复杂度也由O(n2)降为O(n)。

In the data structure,the binary tree can be uniquely confirmed when the nodes sequences of this binary tree for preorder traversal and inorder traversal are knows. In this thetis, an algorithm of creating binary tree is analyzed. Two improved algorithms are given. The time complexity of the improved algorithm goes down from O（n^2） to O（n）.