python - 在二叉搜索树中找到父级？

Question

我希望在 BST 中找到具有特定值的节点的父节点。我的节点类具有属性项(即值/键)、左和右。

寻找 parent 的想法是这样的:
1)如果value(key)不存在，则返回None，None
2)如果root等于值(key)则返回None，root
3)否则找到值(key)并返回(par，node)，其中par是父节点和节点

我的函数如下所示:

def findpar(self,key):
    if not self._exists(key):
        return None,None
    elif self.root.item==key:
        return None, self.root
    p=self.root
    found=False
    while not found:
        if p.left.item==key:
            return p, p.left
            found=True
        elif p.right.item==key:
            return p, p.right
            found=True
        elif p.item<key:
            p=p.left
        elif p.item>key:
            p=p.right

当p.left或p.right为None时，如何处理问题？

Answer 1

由于您的代码当前有效，因此您不可能转向 None 左子级或右子级。这是因为您的代码以

开头

if not self._exists(key):
    return None,None

所以key必须存在，如果必须存在，那么它必须存在于搜索路径上。

应该注意的是，您实际上执行了两次搜索，但效率并不高。相反，你可以尝试这样的事情:

def findpar(self,key):
    parent, node = None, self.root
    while True:
        if node is None:
            return (None, None)

        if node.item == key:
            return (parent, node)

        parent, node = node, node.left if key < node.item else node, node.right