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

摘要

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