给定它的中序和前序遍历,我如何构造一棵树?我只是在寻找一种高效的算法.
解决方案来自 Sun 的(我猜现在是 Oracle)论坛:
问题: 谁能帮助我从中序和后序遍历构造二叉树,我只想知道算法以便我可以应用它.
答案:让 p_1, p_2 ... p_n 成为后序遍历,让 i_1, i_2 ... i_n 为中序遍历.从后序遍历我们知道树的根是p_n.在中序遍历中找到这个元素,比如i_1, i_2 ... i_k-1 p_n i_k+1 ... i_n.从中序遍历中我们找到左子树中的所有元素,即i_1, i_2 ... i_k-1 和在右子树中,即 i_k+1 ... i_n 分别.
删除元素 p_n(和元素 i_k == p_n).在p_1、p_2 ... p_j 中找到最右边的元素p_j>... p_n-1 其中 p_j 是 i_1、i_2 ... i_k-1.这是原始树的左子树的根.拆分 p_1、p_2 ... p_j 和 p_j+1 ...p_n-1 和 i_1、i_2 ... i_k-1 和 i_k+1 ... i_n.现在你有两个子序列表示原始的两个子树的后序和中序遍历树.
作者:JosAH.
我已经按照 Jos 的指示实现了该算法,并且效果很好!
How can I construct a tree given its inorder and preorder traversal? I am just looking for an efficient algorithm.
解决方案A blatant copy and paste from Sun's (Oracle now, I guess...) forum:
Question: Can anybody help me on how to construct Binary tree from inorder and postorder traversals,i just want to know the algorithm so that i can apply it.
Answer: Let p_1, p_2 ... p_n be the postorder traversal and let i_1, i_2 ... i_n be the inorder traversal. From the postorder traversal we know that the root of the tree is p_n. Find this element in the inorder traversal, say i_1, i_2 ... i_k-1 p_n i_k+1 ... i_n. From the inorder traversal we find all the elements in the left subtree, i.e. i_1, i_2 ... i_k-1 and in the right subtree, i.e. i_k+1 ... i_n respectively.
Remove element p_n (and element i_k == p_n). Find the rightmost element p_j in p_1, p_2 ... p_j ... p_n-1 where p_j is an element in i_1, i_2 ... i_k-1. This is the root of the left subtree of the original tree. Split p_1, p_2 ... p_j and p_j+1 ... p_n-1 and i_1, i_2 ... i_k-1 and i_k+1 ... i_n. Now you have two subsequences representing the postorder and inorder traversal of the two subtrees of the original tree.
Author: JosAH.
I've implemented the algorithm once following Jos' instructions, and it worked perfectly!
更多推荐
建造一棵树
发布评论