生成给出的顺序和前序遍历

Question

我看到代码在这里贴出后序遍历： How do I output the preorder traversal of a tree given the inorder and postorder tranversal?

我不太懂其中的逻辑虽然，特别是递归的右部的树：

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

任何帮助，将不胜感激。

Answer 1

承担binary expression tree以及如何序，序和后序遍历行事就可以了：

1. inorder：左子树，当前根，右子树
2. preorder：当前根，左子树，右子树
3. postorder：左子树，右子树，当前根

现在的当前代码，第一鉴定者通知左右子树。因为我们知道前序数组的第一个元素是我们的根，我们可以在inorder数组中找到相应的根。因为我们知道root之前的所有元素都是子树的元素，并且它之后的所有元素都是正确的子树的元素。

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

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

1. 预启动+ 1：因为左子树的根就在序遍历当前根后
2. i-inostart：因为i是我们在根中的索引ar射线所以I-inostart将左子树的大小

然后右子树：

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

1. 预起动+ I-inostart + 1：如我告诉上述i-inostart是左子树的大小，我们也知道在前序数组中，右子树的根将在当前根和整个子树之后，所以它的索引将是预起动+ I-inostart + 1
2. I + 1：因为在序阵列根指数为我，之后的元素应该是右子树的序阵列开始
3. 长度-I + inostart-1：因为右子树的大小将是长度减去左子树的大小和减1（根）

，然后输出我们的当前根：

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

这样递归会导致树的后序遍历。