二叉排序树后序确定中序序列

二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，它的左子树中所有节点的关键字小于根节点的关键字，并且右子树中所有节点的关键字大于根节点的关键字。二叉排序树能够提高数据的访问效率，因为查找、插入、删除等操作的时间复杂度都为O(logn)。在二叉排序树中，节点的关键字一般是唯一的。但如果有多个节点的关键字相同，则可以根据需要对这些节点进行处理。例如，可以在节点上保存一个计数值，表示该节点的关键字在树中出现的次数。

在实际应用中，我们经常需要对二叉排序树进行遍历。有前序遍历、中序遍历和后序遍历三种方法。前序遍历是先访问根节点，再访问左子树，最后访问右子树；中序遍历是先访问左子树，再访问根节点，最后访问右子树；后序遍历是先访问左子树，再访问右子树，最后访问根节点。对于有n个节点的二叉树，每个节点都遍历一次，所以时间复杂度为O(n)。

如果我们已知二叉排序树的后序遍历序列，那么是否能够确定它的中序遍历序列呢？答案是肯定的。这是因为在二叉排序树中，每个节点只能有一个父节点，所以在后序遍历序列中，最后一个节点一定是根节点。根据根节点的值，我们可以把中序遍历序列分成左子树和右子树两部分。由于二叉排序树的左子树中所有节点的关键字都小于根节点的关键字，右子树中所有节点的关键字都大于根节点的关键字，所以可以通过递归地进行处理，最终得到整个二叉排序树的中序遍历序列。这个过程可以用以下代码来实现：

```

vector in_order_from_post_order(vector post_order) {

if (post_order.empty()) return {};

int root = post_order.back();

vector left, right;

for (int i = 0; i < post_order.size() - 1; i++) {

if (post_order[i] < root) {

left.push_back(post_order[i]);

} else {

right.push_back(post_order[i]);

}

}

vector inorder = in_order_from_post_order(left);

inorder.push_back(root);

vector right_inorder = in_order_from_post_order(right);

inorder.insert(inorder.end(), right_inorder.begin(), right_inorder.end());

return inorder;

}

```

除了代码实现外，从其他角度也可以证明“二叉排序树后序确定中序序列”这一结论的正确性。下面从多个角度进行分析。

一、 递归定义

在二叉排序树中，每个节点都有左右子树，且左子树中所有节点的关键字小于这个节点的关键字，右子树中所有节点的关键字大于这个节点的关键字。根据这个定义，可以证明“二叉排序树后序确定中序序列”的正确性。具体来说，我们可以假设一棵二叉排序树的后序遍历序列为L1L2…Ln-1Rn，其中Li表示左子树的后序遍历序列，Ri表示右子树的后序遍历序列，而Rn则表示根节点的值。由于二叉排序树的定义，可以将各个节点按照它们在中序遍历中出现的顺序排列，即左子树中较小的节点排在根节点的左侧，右子树中较大的节点排在根节点的右侧。因此，L1L2…Ln-1就是这棵二叉排序树左子树的后序遍历序列，而Rn后面的所有节点都是它的右子树。接下来，我们可以递归地对左子树和右子树进行相同的处理过程，最终得到整棵二叉排序树的中序遍历序列。因此，递归定义可以证明“二叉排序树后序确定中序序列”的正确性。

二、 假设反证法

为了证明“二叉排序树后序确定中序序列”的正确性，还可以运用假设反证法。具体来说，我们可以假设有两棵不同的二叉排序树它们的后序遍历序列相同，但是它们的中序遍历序列不同。根据定义，这两棵二叉树的中序遍历序列应该是不同的，但是它们的后序遍历序列却是相同的。由于后序遍历序列的最后一个元素就是根节点的值，这两棵二叉树的根节点的值必须相同。因此，这两棵二叉树的根节点就是相同的。接下来，我们可以将这两棵二叉树划分为左子树、右子树以及根节点。对于左子树和右子树，它们的后序遍历序列也是相同的，因为它们的中序遍历序列不同，所以它们的结构也必须不同。由于二叉排序树的定义，左子树中的所有节点都小于根节点，右子树中的所有节点都大于根节点。因此，这两棵二叉树的左子树和右子树必须分别包含相同的节点，否则它们的中序遍历序列就会不同。但是根据假设，这两棵二叉树是不同的，这与它们的结构是相同的矛盾。因此，我们可以证明“二叉排序树后序确定中序序列”的正确性。

三、 根据逆运算得到

从另一个角度来看，“二叉排序树后序确定中序序列”的正确性也可以根据逆运算得到。具体来说，我们可以根据二叉排序树的定义和中序遍历序列，确定它的后序遍历序列。因为二叉排序树的左子树中所有节点的关键字小于根节点的关键字，右子树中所有节点的关键字大于根节点的关键字，所以中序遍历序列中的第一个节点是左子树的最右边的节点，而最后一个节点是右子树的最左边的节点。这些节点可以分别利用递归的方法找出。接着，我们可以把找到的根节点、左子树、右子树的后序遍历序列拼接在一起，就得到了原始的后序遍历序列。因此，如果我们确定了二叉排序树的中序遍历序列，就能够根据逆运算得到它的后序遍历序列。

四、 示例分析

假设有一棵二叉排序树如下所示：

```

8

/ \

3 10

/ \ \

1 6 14

/ \ /

4 7 13

```

它的中序遍历序列为1 3 4 6 7 8 10 13 14，后序遍历序列为1 4 7 6 3 13 14 10 8。我们可以利用代码实现，根据后序遍历序列生成中序遍历序列。

```

vector post_order{1, 4, 7, 6, 3, 13, 14, 10, 8};

vector in_order = in_order_from_post_order(post_order);

for (auto x : in_order) cout << x << " ";

```

输出结果为：1 3 4 6 7 8 10 13 14。

因此，我们可以验证“二叉排序树后序确定中序序列”这一结论的正确性。