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

Question

此堆由 BinaryNode class 支持，该节点存储指向父节点、左子节点和右子节点的指针。没有使用数组。

我正在尝试找到最深最右的节点。我认为下面的代码可以工作，但它只会检查正确的子树，因为我从正确开始。例如，在下面的两个堆中，如果最后一个节点位于 5、6 或 5 和 6 插槽中，则此方法有效。如果这两个为空，它将 return 插槽 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     3
4   5

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

在根部，您去掉了第一个数字，留下“01”。则规则变为如果数字为 0 则走左分支，如果数字为 1 则走右分支。

我们在根节点，下一个二进制数字是0。所以走左边的分支，你在堆中的节点2。砍掉 0 就剩下“1”了。

从 2 节点开始，您沿着正确的分支前进（因为您的二进制数字是“1”），将您留在标记为 5.

的节点处

这适用于任何大小的堆，复杂度为 O(log n)。

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

Find the last node in binary heap

heap

python-3.x