假设一棵二叉排序树的关键字为单个字母，其后序遍历序列为ACDBFIJHGE，回答以下问题： （1）画出该二叉排序树； （2）求在等概率下的查找成功的平均查找长度。 （3）求在等概率下的查找不成功的平均查找长度。

(1) 画出该二叉排序树：

        G
       / \
      E   J
     /   / \
    C   I   H
   / \
  A   D
     /
    B

(2) 在等概率下的查找成功的平均查找长度为：(1+2+3+4+5+6+7)/7=4

(3) 在等概率下的查找不成功的平均查找长度为：(1+2+2+3+3+4+4)/8=2.5

相关问题

假设一棵二叉排序树的关键字为单个字母，其后序遍历序列为ACDBFIJHGE，详细讲解以下问题：（1）画出该二叉排序树。（6分）（2）求在等概率下的查找成功的平均查找长度。（2分）（3）求在等概率下的查找不成功的平均查找长度

### 回答1：
（1） 画出该二叉排序树如下图所示：

          G
         / \
        E   J
       /   / \
      C   H   I
     / \
    A   D
         \
          B

（2）在等概率下的查找成功的平均查找长度为 3.7。

查找成功的概率为每个节点的概率，即 1/9。对于任意一个节点，其深度为从根节点到该节点所经过的边数。因此，查找成功的平均查找长度为：

(1/9) * (1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 5) = 3.7

（3）在等概率下的查找不成功的平均查找长度为 4.44。

由于二叉排序树的特性，当查找不成功时，需要到达最底层的空节点才能确定查找失败。因此，查找不成功的平均查找长度为树的深度加一。树的深度为 4，因此查找不成功的平均查找长度为 4 + 1 = 4.44。

### 回答2：
（1）根据后序遍历序列ACDBFIJHGE，可以得到该二叉排序树的结构如下：

G
/ \
E J
/ \ /
D H I
/ /
C F
/
A

（2）在等概率下的查找成功的平均查找长度可以通过二叉排序树的深度来计算。深度是指从根节点到达某个叶子节点的路径长度。根据二叉排序树的结构，每个节点的深度为从根节点到达该节点的路径长度。

节点A的深度为1，节点C的深度为2，节点D的深度为3，节点E的深度为2，节点F的深度为3，节点G的深度为1，节点H的深度为2，节点I的深度为3，节点J的深度为2。

平均查找长度 = (节点A的深度 + 节点C的深度 + 节点D的深度 + 节点E的深度 + 节点F的深度 + 节点G的深度 + 节点H的深度 + 节点I的深度 + 节点J的深度) / 总节点数

总节点数为9个，所以平均查找长度 = (1 + 2 + 3 + 2 + 3 + 1 + 2 + 3 + 2) / 9 = 20 / 9 ≈ 2.22

（3）在等概率下的查找不成功的平均查找长度仍然可以通过二叉排序树的深度来计算。根据二叉排序树的结构，对于一个叶子节点来说，它的深度等于从根节点到达该节点的路径长度。

所有叶子节点的路径长度之和等于深度乘以每个深度的叶子节点数，再除以总叶子节点数。

叶子节点数为5个，其中A、C、D、F、I是叶子节点，它们的深度分别为1、2、3、3、3。

总叶子节点数为9个，所以平均查找长度 = (1*1 + 2*2 + 3*3 + 3*1 + 3*2) / 9 = (1 + 4 + 9 + 3 + 6) / 9 = 23 / 9 ≈ 2.56。

### 回答3：
（1）根据后序遍历序列以及二叉排序树的特点，可以得到根节点为E，根节点E的右子树为HGE，左子树为ACDBFIJ。继续根据子树的后序遍历序列可以得到二叉排序树的结构如下：
E
/ \
C H
/\ / \
A D G J
\
F
该二叉排序树绘制出来即可。

（2）在等概率下的查找成功的平均查找长度计算公式为：ASL = log2(n+1) - (1/n) * (H(x1) + H(x2) + ... + H(xn))，其中n为节点的个数，H(x1)、H(x2)分别为查找到节点x1、x2时所经过的节点数量。

对于该二叉排序树，节点的个数n为9个，那么查找成功的平均查找长度ASL = log2(9+1) - (1/9) * (0 + 1 + 1 + 1 + 2 + 2 + 2 + 3 + 3) = log2(10) - (1/9) * 15 ≈ 2.356。

（3）在等概率下的查找不成功的平均查找长度计算公式为：ASL = log2(n+1)。

对于该二叉排序树，节点的个数n为9个，那么查找不成功的平均查找长度ASL = log2(9+1) = log2(10) ≈ 3.322。

（注意：上述计算公式中的log2(n)表示以2为底n的对数，H(x)表示节点x所在的深度）

1、 假设一棵二叉排序树的关键字为单个字母，其后序遍历序列为ACDBFIJHGE。 （1）画出该二叉排序树。 （2）求在等概率的情况下的查找成功的平均查找长度。 （3）求在等概率的情况下的查找不

(1) 要画出这棵二叉排序树，我们根据后序遍历的顺序重建树结构。后序遍历先左后右，最后访问根节点。给定的序列ACDBFIJHGE告诉我们：

首先插入A，然后按照后序遍历顺序，A会成为根节点的左孩子，接着插入C，C作为A的左孩子；D作为A的右孩子；接下来F在D的左，I在D的右，依次类推，直到所有节点都插入。所以树的大致结构会是这样的：

        A
       / \
      C   D
     / \ / \
    B  F I J
         \
          H
           \
            G

(2) 对于等概率的查找，平均查找长度（ASL, Average Search Length）取决于树的平衡程度。由于这是一个无序的二叉排序树，最坏的情况下，它会退化成链表，即每个节点只有一个子节点，此时平均查找长度等于节点数。而在这个例子中，有10个节点，所以最坏情况下的ASL为10。

但在等概率情况下，如果树保持较好的平衡状态，如AVL树或红黑树，每次查找都可以将搜索范围减半。理想情况下，对于平衡二叉搜索树（比如AVL），平均查找长度为对数复杂度O(log n)。然而，由于这个特定例子中树的形状未知，无法给出确切的最优ASL，但可以肯定的是，在平均意义下不会是线性的。

(3) 查找不成功（Misses）是指在查找过程中没有找到目标键值。同样，对于完全不平衡的树，最多需要检查所有节点才能确定找不到，即9次查找不成功。而对于平衡二叉搜索树，平均而言查找不成功的次数接近0。但由于数据未提供平衡性信息，无法给出准确的期望值。