后序遍历序列为 ACDBFIJHGE 的二叉树分析

1、画出该二叉树如下：

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

2、等概率查找成功的平均查找长度为：

首先，按字母顺序遍历这棵二叉树，得到的序列为 ABCDEFGH IJ。因此，我们可以将这棵树转化为一棵二叉查找树，其中节点的值为遍历序列中的字母，左子树中的所有节点的值都小于父节点的值，右子树中的所有节点的值都大于父节点的值。

对于一棵二叉查找树，等概率查找成功的平均查找长度为树高加一，即：

平均查找长度 = 树高 + 1

因此，我们只需要求出该二叉查找树的树高即可。通过观察可知，该二叉查找树的树高为 4，因此平均查找长度为 5。

3、等概率查找不成功的平均查找长度为：

设二叉查找树的节点个数为 n，查找不成功的概率为 1/n。对于查找不成功的情况，平均查找长度可以采用以下公式计算：

平均查找长度 = 树中每个节点的深度 × 查找不成功的概率之和

因此，我们需要先计算出树中每个节点的深度以及查找不成功的概率，然后将它们相乘并求和即可。具体计算过程如下：

（1）计算每个节点的深度

从根节点开始，递归地计算每个节点的深度。根节点的深度为 1，其它节点的深度为其父节点的深度加一。计算得到每个节点的深度如下：

         G (depth: 1)
       /   \
      E (depth: 2)     J (depth: 2)
     / \   /
    B (depth: 3)   F (depth: 3)  I (depth: 3)
   / \   /
  A (depth: 4)  D (depth: 4) H (depth: 4)
     /
    C (depth: 5)

（2）计算查找不成功的概率

对于一个节点来说，查找不成功的概率等于其父节点的子树大小除以树的总大小。因此，我们需要先计算出每个节点的子树大小，然后再计算查找不成功的概率。计算得到每个节点的子树大小如下：

         G (size: 11)
       /   \
      E (size: 5)     J (size: 4)
     / \   /
    B (size: 3)   F (size: 2)  I (size: 2)
   / \   /
  A (size: 1)  D (size: 1) H (size: 1)
     /
    C (size: 1)

其中，每个节点的子树大小等于其左子树大小加上右子树大小再加上一（即该节点本身的大小）。

接下来，我们计算查找不成功的概率。根据二叉查找树的性质，左子树中的所有节点的值都小于父节点的值，右子树中的所有节点的值都大于父节点的值。因此，对于任意一个节点来说，如果要查找的值不在其子树中，那么只有两种情况：要查找的值比该节点的值小，但是比其左子树中的所有节点的值都大；要查找的值比该节点的值大，但是比其右子树中的所有节点的值都小。因此，查找不成功的概率等于该节点的左子树大小除以树的总大小加上其右子树大小除以树的总大小。计算得到每个节点的查找不成功的概率如下：

         G (p: 2/11)
       /   \
      E (p: 4/11)     J (p: 3/11)
     / \   /
    B (p: 8/11)   F (p: 10/11)  I (p: 6/11)
   / \   /
  A (p: 11/11)  D (p: 11/11) H (p: 11/11)
     /
    C (p: 11/11)

其中，p 表示查找不成功的概率。

（3）计算平均查找长度

根据上面的公式，我们可以计算出每个节点的平均查找长度，然后将它们相乘并求和即可得到等概率查找不成功的平均查找长度。具体计算过程如下：

平均查找长度 = (1 × 2/11) + (2 × 4/11) + (2 × 3/11) + (3 × 8/11) + (4 × 10/11) + (4 × 6/11) + (5 × 11/11) + (5 × 11/11) + (5 × 11/11) + (6 × 11/11) + (6 × 11/11)
             = 4.545

因此，等概率查找不成功的平均查找长度为 4.545。