构建树 [英] Construct a Tree

问题描述

如何构造一个给定其树的顺序和预订遍历的树？
我只是寻找一个有效的算法。

How can I construct a tree given its inorder and preorder traversal? I am just looking for an efficient algorithm.

推荐答案

从 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 code> ... i_n

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.

删除元素 p_n （和元素 i_k == p_n ）。在 p_1中找到最右边的元素 p_j ， p_2 ... 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 。现在你有两个子序列代表原始
树的两个子树的后序和顺序遍历。

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.

作者： a href =http://forums.sun.com/profile.jspa?userID=431408 =nofollow noreferrer> JosAH 。

Author: JosAH.

我已经按照Jos的说明执行了算法，它的工作完美！

I've implemented the algorithm once following Jos' instructions, and it worked perfectly!

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