二叉搜索树 - 父节点方法输出错误

Question

这个函数的作用是在一个二叉搜索树里查找一个特定的值（我们叫它“键”），并返回这个值的父节点。不过，我在调用这个函数时，得到的结果却一直是None，也就是没有找到。我的测试代码是这样的：

bst =

    22
   /  \
 12    30
/  \  /  \
8  20 25  40

b = bst.parent_r(20)
print(b)




def parent_r(self, key):
        """
        ---------------------------------------------------------
        Returns the value of the parent node in a bst given a key.
        ---------------------------------------------------------
        Parameters:
            key - a key value (?)
        Returns:
            value - a copy of the value in a node that is the parent of the
            key node, None if the key is not found.
        ---------------------------------------------------------
        """
        assert self._root is not None, "Cannot locate a parent in an empty BST"

        parent = self.parent_r_aux(self._root, key)
        return parent

    def parent_r_aux(self, node, key):
        parent = None

        if node is None:
            return None

        lparent = self.parent_r_aux(node._left, key)
        if lparent is None:
            rparent = self.parent_r_aux(node._right, key)
        
        if node._left is not None or node._right is not None:
            if node._left._value == key or node._right._value == key:
                parent = node._value
return parent

根据我的测试，我希望能得到节点的值，12。

Answer 1

你需要检查在递归调用中是否找到了这些值，如果找到了就返回。

def parent_r_aux(self, node, key):
    if node is None:
        return None

    parent = self.parent_r_aux(node._left, key)
    if parent:
        return parent

    parent = self.parent_r_aux(node._right, key)
    if parent:
        return parent

    if node._left and node._left._value == key:
        return node
    if node._right and node._right._value == key:
        return node