尝试获取二叉树中的最后一个节点

Question

树由 BinaryNode 支持，它存储指向父节点、左子节点和右子节点的指针。我相信我很接近，但我无法获得最后一个节点。我使用的测试树是：

      0
     / \
    /   \
   1     2
  / \   / 
 3   4 5 

# ---------- 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 = node.get_right()       # get_right takes a node that will then return the right child

        self._find_last(node)

    # 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 = node.get_left()         # get_left takes a node that will then return the left child

        self._find_last(node)       

    return node                        # return the last node in the tree

我应该得到有 5 的节点，但我最终得到了有 2 的节点。在测试期间，函数确实到达了有 5 的节点，但仍然 returns 有 2 的节点。

Answer 1

我认为您应该将 node 设置为 self.find_last 调用的 return 值。现在，您正在 return 树中最后一个节点的父节点的值，因为您没有 return self.find_last 调用的值。

您可以重组代码以使其更简洁：

def _find_last(self, node):     
    if self._has_right(node):        
        return self._find_last(node.get_right())
    elif self._has_left(node):        
        return self._find_last(node.get_left())       
    return node

尝试获取二叉树中的最后一个节点

Attempting to get the last node in a Binary Tree

binary-tree

python-3.x