创建二叉搜索树

Question

如果我按顺序添加以下值来构建二叉搜索树：

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

我得到了一棵高度为5的树。除了试错之外，是否有其他方法可以确定一个整数排序方式，以创建一个高度为4的树？

- Tobi3

---

你需要使用平衡二叉树。 - ie.

可能是平衡二叉树（AVL）的重复问题。 - Flexo

我不是要构建一棵平衡树，而是要确定一个整数的顺序，以使其高度为4。 - Tobi3

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

- hugomg

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

在插入最后三个元素之后：

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

...然后在最后的两个之后：

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

最后，在插入最后一个元素之后：

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

...你将得到一棵高度为K=4的二叉搜索树。

请注意，此方法仅在K足够大时才有效--具体来说，当K(K+1)/2 >= N时。

- Nate Kohl

---

你在二叉树中的哪个位置找到了18？ - Micromega

@Chibox：抱歉，打错字了。现在应该已经修复了。 - Nate Kohl

如果我有7个元素，我不能构建高度为2或3的BST，例如？ - Ofir Attia

@OfirAttia：你肯定可以构建一个高度为3（而不是高度为2）的BST来容纳7个元素，但不能使用这种方法。 - Nate Kohl

@NateKohl，你有相关信息的链接吗？例如，我想按照高度为2、3、4、5、6的顺序订购2、5、6、11、17、18、22号物品，我需要采用什么方法呢？谢谢。 - Ofir Attia

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));
        }
    }
}

- iMobaio