我有从 1 到 31 的数字,我需要用这些数字创建一个深度最小的二叉搜索树。我正在考虑除以 31/2 并将 16 作为我的根。之后除以 16/2 然后插入 8,但这似乎不起作用。是否有一种算法可以知道以什么顺序插入数字,以便树的深度尽可能小?
最佳答案
如果你有数字 1–31,31 个数字,你想要根号左边的 15 个数字和右边的 15 个数字。
所以根是 16(不是 31/2,而是 31/2 + 1)。
重复相同的过程,左子树有 15 个元素,因此您需要在该子树的每一侧有 7 个数字。
所以左子树的根是 8(即 15/2 + 1;这里有规律)。
类似的计算给出右子树的根。
等等。
关于c++ - 创建具有最小深度的二叉搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36207013/