我正在使用数组进行二叉搜索树实现。我需要为具有特定高度的 BST 创建一个数组。我如何计算这个尺寸？
最佳答案
我想，您是在谈论像二进制堆中那样的索引实现。
存储在数组中的所有顶点。此数组的第一个元素 - 根。如果 BST 的某个顶点是数组的第 i 个元素，则其左子存储在索引为 2*i 的单元格中，右子存储在索引为 2*i+1 的单元格中。这种在内存中的表示方案如下所示:
您正在询问某个给定高度的树大小。高度 - 是树中的多个级别。换句话说，高度是从根到任何叶子的路径长度。在上图中，BST 的高度 = 2。
如何计算用于存储具有固定高度的树的数组大小？它只是几何级数的总和。高度为 0 的层有 1 个元素，高度为 1 的下一层有 2 个元素，下一层有 4 个元素，依此类推。高度 = H 的级别有 2^H 个元素。
用于存储高度为 H 的树的数组大小 大小足以存储从 0 到 H 的所有级别:
2^0//高度为 0 的单元格
+
2^1//高度为 1 的单元格
+...+2^H = 2^(H+1)-1 ;
重要说明 - 许多编程语言都有从零开始的数组索引。所以，当你像 int tree[2^(H+1)-1] 这样声明数组时这意味着元素从 0 到 2^(H+1)-2 编号，而您希望它们从 1 到 2^(H+1)-1 编号。索引为 0 的元素不方便——它违反了“父 i，左子 2*i”规则，因为 0=2*0。换句话说，当我说数组中的第一个元素是根时，我的意思是树 [1]，而不是树 [0]。只需忽略树 [0]。
最后，高度为 H 的 BST 的 required_array_size =calculated_size + zero_ignoring_shift = 2^(H+1)-1 +1 = 2^(H+1)
关于arrays - 如何计算具有一定高度的二叉搜索树的数组大小？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16952779/