给定顺序和预订遍历生成后期遍历 [英] Generate the post-order traversal given the in-order and pre-order traversal

问题描述

我看到代码发布在这里：

I see that the code is posted here: How do I output the preorder traversal of a tree given the inorder and postorder tranversal?

我很难理解逻辑，特别是树的正确部分的递归：

I have trouble understanding the logic though, especially, the recursion for the right part of the tree:

postorder(preorder, prestart+i-inostart+1, inorder, i+1, length-i+inostart-1);

任何帮助将不胜感激。

推荐答案

假设二进制表达式树，以及如何排序，预订和postorder遍历操作：

assume the binary expression tree and how the inorder, preorder and postorder traversals act on it:

1. inorder ：left subtree，current root，右子树


2. preorder ：当前根，左子树，右子树


3. postorder ：左子树，右子树，当前根

1. inorder: left subtree, current root, right subtree
2. preorder: current root, left subtree, right subtree
3. postorder: left subtree, right subtree, current root

现在的当前代码，首先标识左右子树。因为我们知道preorder数组的第一个元素是我们的根，我们可以在order数组中找到我们对应的根。因为我们知道root之前的所有元素都是子树的元素，所有的元素都是右子树的元素。

now the current code, first identifies the left and right subtrees. as we know the first element of preorder array is our root and we could find our corresponding root in inorder array. as we know all elements before root are left subtree's elements and all elements after it are right subtree's elements.

我们要生成后序遍历，所以我们递归地继续使用左子树：

we want to produce postorder traversal so we recursively continue with left subtree:

   postorder(preorder, prestart+1, inorder, inostart, i-inostart);

1. prestart + 1： 因为左子树的根刚好在预订遍历之后的当前根目录


2. i-inostart： 因为我是我们在数组中的根的索引，所以 i-inostart 将是左子树的大小

1. prestart+1: because the root of left subtree is just after the current root in preorder traversal
2. i-inostart: because i is the index of our root in inorder array so i-inostart would be the size of left subtree

然后右子树：

   postorder(preorder, prestart+i-inostart+1, inorder, i+1, length-i+inostart-1);

1. prestart + i-inostart + 1： 如上所述， i-inostart 是左子树的大小，我们也知道在预订数组中，右子树的根将来自当前根和整个子树，所以其索引将会是 preart + i-inostart + 1


2. i + 1： root的索引是我，之后的元素应该是排序数组中的右子树的开始


3. length-i + inostart- 1： 因为右子树的大小将是长度减去左子树的大小和减1（根）

1. prestart+i-inostart+1: as I told above i-inostart is the size of left subtree and also we know that in preorder array the root of right subtree would come after the current root and the whole subtree so its index would be prestart+i-inostart+1
2. i+1: because in inorder array the root's index was i and the element after that should be the start of right subtree in inorder array
3. length-i+inostart-1: because the size of right subtree would be length minus the size of left subtree and minus 1 (the root)

然后输出我们当前的根：

and then output our current root:

   cout<<preorder[prestart]<<" ";

递归执行会导致树的后期遍历。

doing so recursively would result in postorder traversal of the tree.

这篇关于给定顺序和预订遍历生成后期遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！