建造一棵树 [英] Construct a Tree

问题描述

给定它的中序和前序遍历，我如何构造一棵树?我只是在寻找一种高效的算法.

解决方案

来自 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!

这篇关于建造一棵树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！