摘要
二叉树的构造有多种方法,给出一棵二叉树的中序序列和后序序列,可以构造出这棵二叉树,但一般采用递归算法.尽管递归算法具有结构简炼、清晰、可读性强等优点,但递归算法在执行过程会耗费太多的时间和空间,为了追求算法的时空效率,必须将递归算法转化为非递化算法,问题才能得到有效解决,本文设计了一个非递归算法,输入一棵二叉树的中序遍历和后序遍历的结点序列,构造出该二叉树,该算法对于一棵有n个结点的二叉树,具有O(n)时间复杂度,是解决该问题的最优算法.
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-reeursive algorithm is given, which inputs the node sequences of a binary tree for inorder traversal and postorder traversal and constructs the binary tree. The algorithm is optimal for the problem with time complexity O（n）,where ＂n＂ is the number of the nodes of the tree.
出处
《衡水学院学报》
2009年第4期37-39,43,共4页
Journal of Hengshui University
关键词
中序遍历
后序遍历
二叉树
inorder traversal
postorder traversal
binary tree
