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

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)。