创建二进制搜索树

Question

如果我构造一个二进制搜索树,按顺序添加以下值:

 10, 7, 16, 12, 5, 11, 2, 20, 1, 14

我得到一个高度为5的树.是否有一个方法(除了试验和错误)我可以用来确定一个整数的排序,它将创建一个高度为4的树？

Answer 1

是的,您可以首先构建一个完美平衡的树,然后您可以以在子节点之前打印父节点的方式输出节点.

要创建一个完美平衡的树,只需对数字进行排序,然后使用递归二进制除法来构建树.

例如,在您的情况下,我们会对数字进行排序

 1 2 5 7 10 11 12 14 16 20

然后从它们构建一个平衡的树(以中间数字作为根并递归重复此过程)

            11
     5            14
 1     7       12    16
   2     10             20

我们现在可以使用preorder遍历或广度优先遍历来按照您想要的顺序打印节点(只要我们在子节点之前输出父节点就可以了).

11 5 14 1 7 12 16 2 10 20

Answer 2

我没有完全想到这一点,但是获取特定深度的树的一种方法是在插入元素之前对它们进行排序:即排序然后将N元素插入到二叉搜索树中将产生深度树N.

你或许可以:

1. 对元素进行排序
2. 插入其中的特定K=4内容以生成深度树K
3. 插入其余元素,使树不会更深.

(当然,选择K开始的元素和插入剩余元素的策略是棘手的部分 - 但也许这将是一个开始？)

编辑:我认为一般解决方案是可能的,假设K足够大.这个怎么样:

1. 特定 10, 7, 16, 12, 5, 11, 2, 20, 1, 14
2. 对元素进行排序: 1, 2, 5, 7, 10, 11, 12, 14, 16, 20
3. 插入最后的K = 4个元素,然后插入最后一个K-1,然后插入K-2,依此类推,直到1.

例如,在排序并插入最后4个之后:

12
  \
   14
     \
      16
        \
         20

...然后插入最后3:

  12
 /  \
7    14
 \     \
  10    16
    \     \
     11    20

...然后在最后2:

    12
   /  \
  7    14
 / \     \
2   10    16
 \    \     \
  5    11    20

...最后,插入最后一个元素后:

      12
     /  \
    7    14
   / \     \
  2   10    16
 / \    \     \
1   5    11    20

...你的BST高度为K = 4.

请注意,这种方法只有在K足够大时才会起作用- 特别是在何时K(K+1)/2 >= N.