c++ - 在二叉树中查找父节点的位置

Question

所以我需要帮助想出一个表达式，它总是会给我一个孩子的父节点在二叉树中的位置。这是我的老师将在我们的考试中提出的问题示例：

“考虑一棵完整的二叉树，它正好有 10,000 个节点，使用从索引 0 开始的数组来实现。通过从左到右一次从树中提取一个级别的元素来按顺序填充数组。假设一个节点存储了它的值在位置 4999。该节点的父节点的值存储在哪里？

我的老师没有告诉我们如何解决这样的问题。她只是说“画一棵二叉树并找到一个模式”。我就是这么做的，但我什么也想不出来！请帮忙。谢谢。

score 14 · Accepted Answer

以下完全使用整数除法。即小数余数被丢弃。对于任何给定的节点 index N，该节点的子节点将始终位于同一数组中的2N+1位置。2(N+1)

因此，此类数组中任何大于 0 的节点的父节点将始终位于 index 处。N(N-1)/2

父母对孩子的例子：

Parent 0: children 1,2
Parent 1: children 3,4
Parent 2: children 5,6
Parent 3: children 7,8
etc...

孩子到父母的例子：

Child 8 : Parent = (8-1)/2 = 7/2 = 3
Child 7 : Parent = (7-1)/2 = 6/2 = 3
Child 6 : Parent = (6-1)/2 = 5/2 = 2
Child 5 : Parent = (5-1)/2 = 4/2 = 2

所以对于你的问题：

(4999-1)/2 = 4998/2 = 2499

注意：记住这一点，因为当您开始编写基于数组的堆排序算法时，您将广泛使用它。

score 3 · Accepted Answer

感谢您的所有帮助。我找到了我的问题的答案！

查找父节点位置的一般算法是：

[i + (root - 1)] / 2 其中 i 是给定节点的位置，root 是根的位置。所以在上面的给定问题中，根从位置 0 开始。所以找到任何节点的父节点的方程是 [i + (0 - 1)] / 2 = (i - 1) / 2

现在假设根从位置 3 开始，那么等式将是 [i + (3 - 1)] / 2 = (i + 2) / 2 ！！！这是我需要的算法。你们中的大多数人帮助我解决了我提供的一个问题，但我实际上需要一个二叉树的通用解决方案，它的根可以从任何位置开始；不只是零

score 2 · Accepted Answer

似乎这就是数组元素如何根据数组索引映射回树

     0
  1     2
3   4 5   6

如果是这样，则索引的父级n位于floor( (n - 1) / 2 )(for n != 0)

score 0 · Accepted Answer

如果您对请求的数字 (4999) 进行 log2 并取整数部分，它将为您提供最接近数字 (12) 的二的幂。它是 2^12 = 4096。

4096 和 2^13 - 1 之间的节点的父节点是 2^11 和 2^12 - 1 之间的节点。对于第一个范围内的每对节点，您在第二个范围内都有其父节点。因此，您可以将它们映射为差值一半的整数部分（4999 - 4096）并将其添加到父范围开始（2048）。

所以你将有 903 / 2 的楼层，并将其添加到 2048，得到 2499。

请注意，我没有进行精确计算，采取答案的策略而不是结果。

你可以把这个算法放在一个数学表达式中，只需要一点工作。

希望能帮助到你！

score -1 · Accepted Answer

如果 n 为偶数，则父节点位于 n/2。如果 n 为奇数，则为 (n-1)/2。所以你可以记住它为math.ceil((n-1)/2)

5 回答 5