在一棵空的二叉树中依次插入的关键字序列为56,78,32,45,40,63,24,80,99,21，请根据你构造出来的二叉排序树和下图，完成所有空格。下图中结点旁为空的编号。

根据插入序列构造的二叉排序树如下所示：

       56
      /  \
    32   78
   / \   / \
  24 45 63 80
   \    /   \
   40  99   (空)
  /
21

对应的二叉树如下所示：

            56(1)
          /      \
        32(2)   78(3)
       /    \      /   \
     24(4) 45(5) 63(6) 80(7)
      \         /        \
      40(8)   99(9)     10(空)
      /
    21(10)

相关问题

设有一组关键字 { 29，01， 13，15，56，20，87，27，69，9，10，74 }，散列函数为 H(key)=key%17，采用平方探测方法解决冲突。试在 0 到 18 的散列地址空间中对该关键字序列构造散列表，则成功查找的平均查找长度为 __

首先，根据散列函数 H(key)=key%17，可以得到散列表的地址空间为 0 到 16，共 17 个位置。

接下来，采用平方探测方法解决冲突，即当关键字 key 在 H(key) 处产生冲突时，依次检查 H(key)+1，H(key)+4，H(key)+9，H(key)+16，...，直到找到一个空位置或者遍历完所有位置。其中，平方探测的步长为 i^2，即第一次探测步长为 1，第二次为 4，第三次为 9，以此类推。

下面是具体的构造过程：

1. 将散列表初始化为空表。
2. 将第一个关键字 29 插入表中，计算出其散列地址为 H(29)=12，将其插入散列表中。
3. 将第二个关键字 01 插入表中，计算出其散列地址为 H(01)=1，将其插入散列表中。
4. 将第三个关键字 13 插入表中，计算出其散列地址为 H(13)=13，将其插入散列表中。
5. 将第四个关键字 15 插入表中，计算出其散列地址为 H(15)=15，将其插入散列表中。
6. 将第五个关键字 56 插入表中，计算出其散列地址为 H(56)=5，将其插入散列表中。
7. 将第六个关键字 20 插入表中，计算出其散列地址为 H(20)=3，将其插入散列表中。
8. 将第七个关键字 87 插入表中，计算出其散列地址为 H(87)=4，将其插入散列表中。
9. 将第八个关键字 27 插入表中，计算出其散列地址为 H(27)=10，将其插入散列表中。
10.将第九个关键字 69 插入表中，计算出其散列地址为 H(69)=4，产生冲突，进行平方探测，依次检查 H(69)+1=5，H(69)+4=8，H(69)+9=13，找到空位置，将其插入散列表中。
11.将第十个关键字 9 插入表中，计算出其散列地址为 H(9)=9，将其插入散列表中。
12.将第十一个关键字 10 插入表中，计算出其散列地址为 H(10)=10，将其插入散列表中。
13.将第十二个关键字 74 插入表中，计算出其散列地址为 H(74)=8，产生冲突，进行平方探测，依次检查 H(74)+1=9，H(74)+4=12，H(74)+9=1，H(74)+16=4，H(74)+25=13，找到空位置，将其插入散列表中。

最终得到的散列表为：

0:
1: 01
2:
3: 20
4: 87 69
5: 56
6:
7: 29
8: 74
9: 9
10:27
11:
12:29
13:13 15
14:
15:
16:

其中，第一列为散列地址，第二列为插入的关键字。

平均查找长度（ASL）是指查找一个关键字时，需要访问的散列表中的位置数的期望值。对于本题，可以通过统计访问每个位置的次数来计算平均查找长度。具体计算方法如下：

1. 对于每个关键字，计算其访问的位置数，累加到总的访问次数中。
2. 将总的访问次数除以关键字的个数，即可得到平均查找长度。

根据上述方法，可以得到各个关键字的访问次数如下：

29: 1
01: 1
13: 1
15: 1
56: 1
20: 1
87: 1
27: 1
69: 3
9: 1
10: 1
74: 5

计算总的访问次数为 16，关键字的个数为 12，因此平均查找长度为 16/12 = 1.33。

因此，成功查找的平均查找长度为 1.33。

设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为：H(key)=key 00000000% 17,采用线性测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表，并计算成功查找的平均查找度。手写过程在0到18的散列地址空间中

首先，根据散列函数H(key)=key 00000000% 17，计算出每个关键字的散列地址：

H(29) = 13
H(01) = 1
H(13) = 13 （冲突，线性探测）
H(15) = 15
H(56) = 4
H(20) = 3
H(87) = 4 （冲突，线性探测）
H(27) = 10
H(69) = 4 （冲突，线性探测）
H(9) = 9
H(10) = 10
H(74) = 8

接下来，使用线性探测法解决冲突。当插入关键字时，如果该地址已经被占用，则往后依次查找，直到找到一个空地址为止。

13: 29, 13
1: 01
15: 15
4: 56, 87, 69
3: 20
10: 27
9: 9
8: 74

最后，计算成功查找的平均查找度。平均查找度是指在查找过程中平均需要查找的次数。如果查找成功，则查找次数为1；如果查找失败，则需要一直向后查找，直到找到空地址或者遍历完整个散列表。因此，平均查找次数等于成功查找的次数除以总共的关键字数。

成功查找的次数为11，总共的关键字数为12，因此平均查找度为11/12=0.92。