c++ - 创建具有最小深度的二叉搜索树

Question

我有从 1 到 31 的数字，我需要用这些数字创建一个深度最小的二叉搜索树。我正在考虑除以 31/2 并将 16 作为我的根。之后除以 16/2 然后插入 8，但这似乎不起作用。是否有一种算法可以知道以什么顺序插入数字，以便树的深度尽可能小？

Answer 1

如果你有数字 1–31，31 个数字，你想要根号左边的 15 个数字和右边的 15 个数字。
所以根是 16(不是 31/2，而是 31/2 + 1)。

重复相同的过程，左子树有 15 个元素，因此您需要在该子树的每一侧有 7 个数字。
所以左子树的根是 8(即 15/2 + 1；这里有规律)。
类似的计算给出右子树的根。

等等。