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

Question

所以我需要帮助提出一个表达式,它总是会给我一个二进制树中子节点的父节点的位置.以下是我的老师将参加考试的问题示例:

"考虑一个包含10,000个节点的完整二叉树,使用从索引0开始的数组实现.通过从左到右一次从树中提取元素,按顺序填充数组.假设节点存储了其值在位置4999.该节点的父节点存储的值在哪里？"

我的老师没告诉我们如何解决这样的问题.她只是说"画一棵二叉树,找到一个模式." 我做到了这一点,但我无法想出任何东西!请帮忙.谢谢.

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

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

Answer 2

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

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

因此，下限为 903 / 2，然后将其添加到 2048，得到 2499。

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

只需做一点工作，您就可以将该算法用数学表达式表示。

希望能帮助到你！