c - 给定中序和前序遍历生成后序遍历

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(preorder, prestart+1, inorder, inostart, i-inostart);

1. prestart+1: 因为前序遍历左子树的根刚好在当前根之后
2. i-inostart: 因为 i 是中序数组中根的索引，所以 i-inostart 就是大小左子树

然后是右子树:

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

1. prestart+i-inostart+1: 正如我上面所说的，i-inostart 是左子树的大小，而且我们知道在前序数组中右子树的根将在当前根和整个子树之后，因此其索引将是 prestart+i-inostart+1
2. i+1: 因为在中序数组中，根的索引是i，之后的元素应该是中序数组中右子树的开始
3. length-i+inostart-1: 因为右子树的大小将是length减去左子树的大小再减去 1(根)

然后输出我们当前的根:

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

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