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

Question

我需要帮助设计一个表达式，它能始终给出二叉树中子节点的父节点位置。以下是我的老师在考试中会出的问题示例：“考虑一个完整的二叉树，有10000个节点，用从索引0开始的数组实现。该数组按顺序从左到右从每个层级上抽取元素来填充树。假设一个节点的值存储在位置4999。那么这个节点的父节点存储在哪里？” 我的老师并没有告诉我们如何解决这样的问题。她只说“画一个二叉树并找到一种模式。”我已经这样做了，但是仍然无法得出任何结论！请帮帮我，谢谢！

- user2188910

---

你应该把你尝试过的内容详细地写出来。也许只是简单的错误而已。 - Austin Mullins

按照规定，这个问题是不可能的。你一定误解或者记错了。我可以立即想到4998和5000都是答案的方法。 - Mooing Duck

没有。能够给我任何子节点的父节点位置的表达式将会形如“2^(n+1) - 1”或类似于此。然后，您可以输入子节点的位置（在本例中为4999），该表达式应该会给出父节点的位置。 - user2188910

^ 呃？？？你能否请尝试回答我的问题。 - user2188910

@OliCharlesworth：哦，我完全忽略了“一次一个级别”。从左到右会非常模糊。我的错。无论如何，除非“缺失”的节点也放入数组中，否则这仍然是不可解的。如果它们被放入数组中，那么这个问题的答案就非常简单了。 - Mooing Duck

Answer 1

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

因此，在这样的数组中，任何节点 N > 0 的父节点始终位于索引 (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

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

- WhozCraig

Answer 2

感谢大家的帮助。我已经找到了我的问题的答案！

查找父节点位置的通用算法为：

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

现在假设根节点从位置3开始，则方程式为[i + (3 - 1)] / 2 = (i + 2) / 2！！！这就是我需要的算法。你们中的大多数人都帮助我解决了一个问题，但实际上我需要的是二叉树的通用解决方案，其根可以从任何位置开始，而不仅仅是从零开始。

- user2188910

Answer 3

看起来这就是数组元素如何根据数组索引映射回树的方式。

     0
  1     2
3   4 5   6

如果是这样的话，那么索引为n的父节点位于floor((n-1)/2)（对于n != 0）。

- Arun

Answer 4

如果您对请求的数字（4999）进行log2，并取整数部分，则会得到最接近该数字的二次幂（12）。它是2^12 = 4096。

4096和2^13-1之间的节点的父节点是在2^11和2^12-1之间的节点。对于第一个范围中的每对节点，您都可以在第二个范围中找到其父节点。因此，您可以通过取一半差异（4999-4096）的整数部分并将其添加到父范围的起始位置（2048）来映射它们。

因此，您将获得903/2的floor，并将其加到2048，从而得到2499。

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

您可以将此算法放入数学表达式中，并进行一些工作。

希望能有所帮助！

- nico

---

好的。你回答正确，所以你知道我在这里问什么。现在我只需要仔细阅读你说的话并尝试理解你的策略哈哈。感谢回复。 - user2188910

@nico 尽管你的答案是100％正确（策略，我没有检查边缘情况），但有一个非常简单的方程式应该会得出相同的答案。 - Mooing Duck

Answer 5

如果n是偶数，则父节点在n/2处。 如果n是奇数，则在(n-1)/2处。 因此，您可以记为math.ceil((n-1)/2)。

- Amogh Godbole