-1

我想为从 1 到 20 的数字绘制一个平衡的二叉搜索树。

             _______10_______
            /                \
        ___5___                15
       /       \             /    \
      3         8          13      18
     / \       / \        /  \     /  \
    2   4     7   9     12    14  17    19
   /          /          /        /     
   1         6          11       16

上面的树是否正确且平衡？

4

1 回答 1

1

在回答您关于是否需要首先计算高度的原始问题时，不，您不需要。您只需要了解平衡树是最高节点和最短节点之间的高度差为零或一的树，实现这一点的最简单方法是确保在填充时始终选择可能列表的中点子树中的顶部节点。

您的样本树是平衡的，因为所有叶节点都位于底部或次底部级别，因此任何两个叶节点之间的高度差最多为 1。

要从数字 1 到 20（包括数字）创建平衡树，您只需将根条目设为 10 或 11（这些数字的中点为 10.5），以便任一子树中的数字数量相等。

然后对每个子树递归地执行此操作。的下侧10是5中点：

           10
          /  \
         5    11-thru-19 sub-tree
        / \
1-thru-4   6-thru-9
sub-tree   sub-tree

只需扩展它，你最终会得到类似的东西：

         _______10_______
        /                \
    ___5___               15
   /       \             /  \
  2         7          13    17
 / \       / \        /     /  \
1   3     6   8     11    16    18    <- depth of highest leaf node
     \         \      \           \
      4         9      12          19 <- depth of lowest leaf node
                                                     ^
                                                     |
                                               Difference is 1

中点可以在高于和低于该数字的数量之差为 1 或 0 的数字处找到。对于从 1 到 20 的整个数字列表，有 9 个小于 10 和 10 个大于 10（或者，如果您选择 11 作为中点，数量是 10 和 9）。

您的样本和我的样本之间的差异可能与我更喜欢通过四舍五入来选择中点的事实有关（这意味着我的右子树往往“更重”）。因为你的左子树更重，你似乎已经四舍五入了。

选择 10 作为初始中点后，左侧子树没有余地，您必须选择 5，因为它的上方和下方有 4 个。任何其他中点将导致两半之间的差异至少为 2（例如，选择 4 作为中点将具有大小为 3 和 5 的两半）。这仍然可以根据数据为您提供平衡的子树，但选择中点“更安全”。

于 2013-05-27T04:10:06.307 回答