pre-为后序遍历 [英] Pre-order to post-order traversal

问题描述

如果二叉搜索树的pre序遍历是6，2，1，4，3，7，10，9，11，如何让后序遍历？

If the pre-order traversal of a binary search tree is 6, 2, 1, 4, 3, 7, 10, 9, 11, how to get the post-order traversal?

推荐答案

您给出的树，这是做构建了pre序遍历：输出，遍历左，遍历右

You are given the pre-order traversal of the tree, which is constructed by doing: output, traverse left, traverse right.

由于后序遍历来自BST，你可以推断出在序遍历（遍历左，输出，遍历右）从后序遍历通过排序的数字。在您的例子中，在序遍历是1，2，3，4，6，7，9，10，11

As the post-order traversal comes from a BST, you can deduce the in-order traversal (traverse left, output, traverse right) from the post-order traversal by sorting the numbers. In your example, the in-order traversal is 1, 2, 3, 4, 6, 7, 9, 10, 11.

从这两块遍历我们就可以构造原始的树。让我们用一个简单的例子是：

From two traversals we can then construct the original tree. Let's use a simpler example for this:

• pre-顺序：2，1，4，3
• 在顺序：1，2，3，4

的$ P $对 - 序遍历给我们的树的根为2.在序遍历告诉我们1落入左子树和3,4落入右子树。左子树的结构是微不足道的，因为它包含一个元素。右子树的pre序遍历推导从原来的pre序遍历服用元素的顺序在该子树：4，3，由此我们知道的权根子树是4，并从在序遍历（3,4），我们知道，3落入左子树。我们最终的树看起来是这样的：

The pre-order traversal gives us the root of the tree as 2. The in-order traversal tells us 1 falls into the left sub-tree and 3, 4 falls into the right sub-tree. The structure of the left sub-tree is trivial as it contains a single element. The right sub-tree's pre-order traversal is deduced by taking the order of the elements in this sub-tree from the original pre-order traversal: 4, 3. From this we know the root of the right sub-tree is 4 and from the in-order traversal (3, 4) we know that 3 falls into the left sub-tree. Our final tree looks like this:

  2
 / \
1   4
   /
  3

通过树状结构，我们可以通过遍历树得到后序遍历：遍历左，右遍历，输出。对于这个例子，在后序遍历是1，3，4，2

With the tree structure, we can get the post-order traversal by walking the tree: traverse left, traverse right, output. For this example, the post-order traversal is 1, 3, 4, 2.

要概括算法：

1. 在pre序遍历的第一个元素是树的根。元素小于根形成左子树。比根元素越大形成右子树。
2. 找到使用步骤1用$ P $对 - 序遍历，由我们计算出的元素是在该子树放置在它们出现在原始顺序的左和右子树的结构pre序遍历。
3. 遍历结果树，以便后期得到给定的pre序遍历相关联的后序遍历。

使用上述的算法，以在有关的$ P $对 - 序遍历相关联的后序遍历的是：1，3，4，2，9，11，10，如图7所示，6入门有左作为一个练习。

Using the above algorithm, the post-order traversal associated with the pre-order traversal in the question is: 1, 3, 4, 2, 9, 11, 10, 7, 6. Getting there is left as an exercise.

这篇关于pre-为后序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！