假如一颗二叉排序树的关键字为整数，其后序遍历序列为4，9，8，5，13，12，15，10 （1）画出该二叉排序树

二叉排序树的后序遍历序列的最后一个元素为根节点，因此该二叉排序树的根节点为10。根据二叉排序树的性质，比根节点小的元素都在左子树中，比根节点大的元素都在右子树中。因此，可以将序列分为两部分：左子树序列（4，9，8，5）和右子树序列（13，12，15），然后分别对左右子树递归地进行构建。

具体过程如下：

1. 根据后序遍历序列，确定根节点为10。
2. 在左子树序列中找到最后一个小于10的元素，即5，将5作为10的左孩子。
3. 将左子树序列（4，9，8，5）分为两部分：左子树序列（4）和右子树序列（9，8）。
4. 对左子树序列（4）递归进行构建，得到根节点为4的左子树。
5. 在右子树序列（9，8）中找到最后一个小于10的元素，即8，将8作为10的右孩子。
6. 将右子树序列（13，12，15）分为两部分：左子树序列（12）和右子树序列（13，15）。
7. 对右子树序列（13，15）递归进行构建，得到根节点为13的右子树。
8. 对左子树序列（12）递归进行构建，得到根节点为12的左子树。
9. 对右子树序列（13，15）递归进行构建，得到根节点为15的右子树。

最终构建出的二叉排序树如下所示：

    10
   /  \
  5    13
 / \   / \
4   8 12  15
     \
      9

相关问题

用顺序表做二叉排序树的存储结构：读入一个整数序列（要求从磁盘文件读取），生成一棵二叉排序树，对二叉排序树作中序遍历，输出结果。计算二叉排序树T查找成功的平均查找长度。输出结果。输入元素x,查找二叉排序树，若存在，则删除该节点，并输出中序遍历结果

好的，您的问题是如何用顺序表做二叉排序树的存储结构，并对其进行操作。以下是详细解答：

二叉排序树（Binary Search Tree）是一种特殊的二叉树，它的左子树中所有节点的值都小于根节点的值，右子树中所有节点的值都大于根节点的值。二叉排序树的中序遍历结果是一个有序的序列。

顺序表是一种线性存储结构，可以利用数组来实现。在实现二叉排序树时，可以用一维数组来表示。设二叉排序树的根节点在数组中的下标为0，则该节点的左子节点在数组中的下标为1，右子节点在数组中的下标为2。同理，对于任意一个节点i，其左子节点的下标为2i+1，右子节点的下标为2i+2。

现在我们来看一下如何用顺序表实现二叉排序树。首先，我们需要读入一个整数序列，然后按照顺序插入到二叉排序树中。插入的过程可以用递归来实现。在插入一个节点时，如果该节点为空，则将新节点插入到该位置；如果该节点不为空，则将新节点插入到该节点的左子树或右子树中，具体是左子树还是右子树，取决于该节点的值与新节点的值的大小关系。

接下来，我们对二叉排序树进行中序遍历，并输出结果。中序遍历可以用递归来实现，遍历的过程是先遍历左子树，然后遍历根节点，最后遍历右子树。

最后，我们需要计算二叉排序树查找成功的平均查找长度。平均查找长度是指在二叉排序树中查找一个元素时，需要遍历的节点数的平均值。具体计算方法是将每个节点的深度乘以该节点被查找的概率，然后将所有节点的结果相加，得到的结果就是平均查找长度。

如果需要删除一个节点，可以先在二叉排序树中查找该节点，如果存在，则删除该节点。删除节点时，需要考虑三种情况：该节点没有子节点；该节点只有一个子节点；该节点有两个子节点。删除节点后，需要重新调整二叉排序树的结构，使之仍然满足二叉排序树的定义。

最后，输出删除节点后的中序遍历结果。

以上就是用顺序表实现二叉排序树的详细步骤。

输入第一行给出一个正整数n（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

### 回答1：
题目描述：

给定一棵二叉树的后序遍历和中序遍历，求该二叉树的层序遍历。

输入格式：

第一行给出一个正整数n（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

输出该二叉树的层序遍历序列，数字间以空格分隔，行末不能有多余空格。

输入样例：

9
1 3 2 5 7 6 4 9 8
1 2 3 4 5 6 7 8 9

输出样例：

4 2 8 1 6 9 3 5 7

思路分析：

根据后序遍历和中序遍历可以确定一棵二叉树，然后对该二叉树进行层序遍历即可。

具体实现：

1. 首先根据后序遍历和中序遍历构建二叉树。

2. 然后对该二叉树进行层序遍历，输出结果。

代码实现：

### 回答2：
这道题要求我们根据二叉树的中序遍历和后序遍历序列构造出一棵二叉树，并输出其层序遍历序列。对于这种题目，我们可以使用递归的方法来构造出整棵二叉树。

首先，我们知道后序遍历序列的最后一个元素一定是二叉树的根节点，而中序遍历序列中，根节点的左边是其左子树的节点，右边是其右子树的节点。因此，我们可以在中序遍历序列中找到根节点，将其左边的序列作为左子树的中序遍历序列，将其右边的序列作为右子树的中序遍历序列。此时，在后序遍历序列中，左子树的序列和右子树的序列就分别对应了左子树和右子树的后序遍历序列。接下来，我们可以对左子树和右子树进行递归处理，构造出左右子树。最后，在构造出整棵二叉树后，我们可以使用队列进行层序遍历，输出对应的值即可。

需要注意的是，当中序遍历序列只有一个元素时，我们就已经找到了叶子节点，这时候直接返回一个叶子节点即可。

下面是具体的代码实现：

### 回答3：
题目描述：

此题需要根据二叉树的先序遍历和后序遍历，通过重构还原出二叉树。其中，先序遍历只需从左到右先序输出所有节点，而后序遍历则先从左到右遍历所有节点的左孩子，接着从左到右遍历所有节点的右孩子，然后最后输出整个二叉树的根节点。

分析思路：

此题可采用递归方法进行实现。由于后序遍历遍历的顺序是从左到右，所以最后一个值一定是根节点，而在中序遍历中，根节点分割了左右两棵子树，左边为左子树，右边为右子树。因此可通过递归的方法，先通过后序遍历确定当前二叉树的根节点，再在中序遍历中找到根节点的位置，从而分别确定左子树和右子树。依次递归实现即可。

代码实现：

#此为树节点类，包含左子树、右子树和节点值
class treeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None

#通过后序遍历和中序遍历重建二叉树
def rebuildTree(post, inorder):
if post:
root = treeNode(post[-1])#通过后序遍历确定根节点
index = inorder.index(root.val)#在中序遍历中找到根节点位置，从而分别确定左右子树
root.left = rebuildTree(post[:index], inorder[:index])
root.right = rebuildTree(post[index:-1], inorder[index + 1:])
return root

#输出先序遍历
def preOrder(root):
if not root:
return
print(root.val, end = ' ')
preOrder(root.left)
preOrder(root.right)

#输入测试用例
n = int(input())
postOrder = list(map(int, input().split()))
inOrder = list(map(int, input().split()))

#输出结果
root = rebuildTree(postOrder, inOrder)
preOrder(root)

参考文献：

python数据结构与算法之美