给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为 ，带权路径长度WPL的值为

首先，我们需要按照权值从小到大的顺序对数据进行排序，得到{2，3，6，7，10，12}。然后，我们可以按照哈夫曼树的构造方法，不断合并权值最小的两个节点，直到只剩下一个根节点为止。

首先，我们合并2和3，得到一个权值为5的节点。然后，我们合并5和6，得到一个权值为11的节点。接着，我们合并7和10，得到一个权值为17的节点。然后，我们合并11和12，得到一个权值为23的节点。最后，我们将17和23合并，得到一个权值为40的根节点。

这样，我们就构造出了一棵哈夫曼树，其树高为3。根据哈夫曼树的性质，每个叶子节点的深度即为其权值，因此每个节点的带权路径长度即为其深度乘以权值。将每个节点的带权路径长度相加，得到WPL的值为：

2×1 + 3×2 + 6×2 + 7×2 + 10×2 + 12×2 = 70

因此，树高为3，WPL的值为70。

相关问题

给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为 ，带权路径长度WPL的值为 。

首先需要根据给定的数据构造哈夫曼树，具体构造过程如下：

1. 将给定的数据按照权值大小从小到大进行排序，得到{2，3，6，7，10，12}。

2. 取出权值最小的两个节点2和3，构造一个新节点，权值为2+3=5，将其作为根节点的左子节点。

3. 将剩余的节点{6，7，10，12}按照权值大小从小到大进行排序，得到{6，7，10，12}。

4. 取出权值最小的两个节点6和7，构造一个新节点，权值为6+7=13，将其作为根节点的右子节点。

5. 将剩余的节点{10，12}按照权值大小从小到大进行排序，得到{10，12}。

6. 取出权值最小的两个节点10和12，构造一个新节点，权值为10+12=22，将其作为根节点的右子节点的右子节点。

7. 将剩余的节点{ }按照权值大小从小到大进行排序，得到{ }。

8. 取出权值最小的两个节点5和13，构造一个新节点，权值为5+13=18，将其作为根节点的右子节点的左子节点。

9. 将剩余的节点{ }按照权值大小从小到大进行排序，得到{ }。

10. 取出权值最小的两个节点18和22，构造一个新节点，权值为18+22=40，将其作为根节点的右子节点的左子节点的右子节点。

11. 将剩余的节点{ }按照权值大小从小到大进行排序，得到{ }。

12. 取出权值最小的两个节点40和5，构造一个新节点，权值为40+5=45，将其作为根节点的右子节点的左子节点的左子节点。

13. 构造完成后，得到以下哈夫曼树：

          98
        /    \
       5      93
            /   |   \
           18   40   22
          / \    |
         5  13  10

树高为4，带权路径长度为：2×5+2×13+3×18+3×22+4×40+4×5=414。

因此，树高为4，带权路径长度WPL的值为414。

设有一组关键字序列为（31,23,17,27,19,11,13,91,61,41)，要求： (1）采用哈希函数： H ( key )= key mod 7。用链地址法解决冲突，试在0~6的散列地址空间对关键字序列构造哈希表。并计算出在等概率情况下查找成功的平均查找长度；(2）以该关键字序列中的各关键字为叶子构造一棵哈夫曼树，并计算出它的带权路径长度 WPL ; (3）按各关键字在该关键字序列中的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

好的，以下是对应的题解：

1. 哈希表构建

采用哈希函数 $H(key) = key \ mod \ 7$，对于每个关键字，计算出其散列地址并插入哈希表中。若发生冲突，则采用链地址法解决，即在对应散列地址的链表中插入该关键字。

关键字序列为（31,23,17,27,19,11,13,91,61,41），哈希表构建的过程如下：

| 地址 | 关键字 |
| --- | --- |
| 0 | 41 |
| 1 | 31，17 |
| 2 | 23，13 |
| 3 | 27，91 |
| 4 | 19 |
| 5 | 11 |
| 6 | 61 |

在等概率情况下查找成功的平均查找长度为：

$$ASL = \frac{1}{n}\sum_{i=1}^nL_i$$

其中 $n$ 为关键字数，$L_i$ 为查找第 $i$ 个关键字时的查找长度。由于采用链地址法解决冲突，所以每个地址上的关键字出现的概率相等，即 $p_i = \frac{1}{n}$。而查找第 $i$ 个关键字时的查找长度与该关键字所在地址上的链表长度 $k_i$ 有关，即 $L_i = k_i + 1$。因此，可以得到：

$$ASL = \frac{1}{n}\sum_{i=1}^n(k_i + 1) = \frac{1}{n}\sum_{i=0}^6(k_i + 1)$$

其中 $k_i$ 表示地址 $i$ 上链表的长度。

2. 哈夫曼树构建

按照哈夫曼树构建的方法，可以得到如下哈夫曼树：

         289
       /     \
     125      164
    /   \    /   \
  53    72  82   82
 / \   /  \
27 26 30  42

其中，每个叶子节点的权值即为对应的关键字，带权路径长度 WPL 为：

$$WPL = 27 \times 1 + 26 \times 2 + 30 \times 2 + 42 \times 2 + 53 \times 3 + 72 \times 3 + 82 \times 3 + 82 \times 3 = 707$$

3. 二叉排序树构建

按照给定的关键字序列，依次插入一棵初始为空的二叉排序树中，可以得到以下二叉排序树：

          31
         /  \
       23   91
      /  \    \
    17   27   41
         /      \
        19      61
           \
           13

在等概率的情况下查找成功的平均查找长度为：

$$ASL = \frac{1}{n}\sum_{i=1}^nL_i$$

其中 $n$ 为关键字数，$L_i$ 为查找第 $i$ 个关键字时的查找长度。由于二叉排序树中各节点的结构与关键字的插入顺序有关，因此 $L_i$ 的值也与插入顺序有关，无法通过概率论的方法进行计算。在一般情况下，二叉排序树的查找成功时间复杂度为 $O(h)$，其中 $h$ 为树的高度。因此，二叉排序树的平均查找长度与树的高度有关，即：

$$ASL = O(h)$$

由于一棵 $n$ 个节点的随机构造的二叉排序树的平均高度为 $O(\log n)$，因此在等概率情况下，该二叉排序树的平均查找长度为 $O(\log n)$。