首页 文章

在二叉搜索树中查找父级？

提问于
浏览 次
1

我希望找到BST中具有特定值的节点的父节点 . 我的节点类有左边和右边的属性项（即值/键） .

找到父母的想法是这样的：
1）如果值（键）不存在，则返回None，None
2）如果root等于值（key），则返回None，root
3）否则找到值（键）并返回（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 为无时，如何处理该问题？

python python-3.x

1 回答

  • 3

    由于您的代码目前有效，您不可能转向左或右孩子 . 这是因为您的代码以

    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
    回复于

相关问题