由遍历序列构造二叉树的非递归算法实现

二叉树的构造有多种方法,给出一棵二叉树的中序序列和后序序列,可以构造出这棵二又树,但一般采用递归算法.尽管递归算法具有结构简炼、清晰、可读性强等优点,但递归算法在执行过程会耗费太多的时间和空间,为了追求算法的时空效率,必须将递归算法转化为非递化算法,问题才能得到有效解决,本文设计了一个非递归算法,输入一棵二又树的中序遍历和后序遍历的结点序列,构造出该二又树,该算法对于一棵有n个结点的二又树,具有O(n)时间复杂度,是解决该问题的最优算法.

Non-recursive Algorithm Which Constructs The Binary Tree With Traversal Sequence

There are many methods to construct a binary tree.Provide the node sequences of a inorder traversal and postorder traversal,then a binary tree can be constructed.Recursive algorithm is usually used.A recursive algorithm structure is simple,clear and readable.But a recursive algorithm will cost too much time and space during the process.We should transform the recursive algorithm into a non-recursive algorithm for time and space efficiency.A non-recursive algorithm is given,which inputs the node sequences of...