algorithm - 创建二叉搜索树

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

我们现在可以使用前序遍历或广度优先遍历以您想要的顺序打印节点（只要我们在子节点之前输出父节点就可以了）。

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

...你留下一个高度为 K=4 的 BST。

请注意，这种方法仅在K足够大时才有效 - 特别是，当K(K+1)/2 >= N.

Answer 3

public void testMakeBinarySearchTree() {
    List<Integer> array = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        array.add(i+1);
    }


    Collections.shuffle(array);


    Node root = new Node(array.get(5));
    for (int value : array) {
        binarySearchTreeInsertNode(root, value);
    }
}


private void binarySearchTreeInsertNode(Node node, int value) {
    int data = node.getData();
    if ( value > data) {
        Node right = node.getRight();
        if (right != null) {
            binarySearchTreeInsertNode(right, value);
        } else {
            node.setRight(new Node(value));
        }
    } else if (value < data) {
        Node left = node.getLeft();
        if (left != null) {
            binarySearchTreeInsertNode(left, value);
        } else {
            node.setLeft(new Node(value));
        }
    }
}