查找二进制堆中的最后一个节点

Question

此堆由 BinaryNode 类提供支持，该类存储指向父级、左子级和右子级的指针。未使用任何阵列。

我试图找到最深最右的节点。我以为我下面的代码会起作用，但它只会检查正确的子树，因为我从右边开始。例如，在下面的两个堆中，如果最后一个节点位于 5、6 或 5 和 6 插槽中，则此方法有效。如果这两个为空，它将返回插槽 2 中的节点而不是插槽 4。

0                     0
/                    /   
/                    /   
1     2               1     2
/    /              /     
3   4 5   6           3   4 
# ---------- Find the last element ----------
def _find_last(self, node):           # PARAMETER node: the root of the tree
# Start by going right
if self._has_right(node):         # _has_right takes a node and returns True if there is a node
node = self._find_last(node.get_right())

# Go left if there is not a right
elif self._has_left(node):         # _has_left takes a node and returns True if there is a node
node = self._find_last(node.get_left())

return node                        # return the last node in the tree

Answer 1

二进制堆必须遵循形状约束：

1. 除可能的最低层外，所有级别都已完全填满。
2. 如果未填充，则底部级别为左填充。

如果您知道堆中有多少个节点，则可以使用该信息快速访问最低、最右侧的节点。例如，假设您有一个包含五个节点的堆：

1
2     3
4   5

堆中的节点数为 5，或二进制中的"101"。您可以使用二进制表示形式将您带到最后一个节点：

在根部，你去掉第一个数字，留下"01"。然后，如果数字为 0，则规则变为采用左分支，如果数字为 1，则采用右分支。

我们在根节点，下一个二进制数字是 0。因此，选择左分支，您将位于堆中的节点2。掀开0，只剩下"1"。

从2节点开始，您遵循正确的分支(因为您的二进制数字是"1"(，将您留在标记为5的节点。

这适用于任何大小的堆，并且具有复杂性 O(log n(。