PYTHON二进制搜索树-递归删除

Question

我正在开发一个二进制搜索树类，我们必须使用递归实现remove方法。这是给我们的代码。

def remove (self, x):
    def recurse (p):
        # Modify this method.
        if p==None:
            return p
        elif x<p.data:
            return p
        elif x>p.data:
            return p
        elif p.left==None and p.right==None:    # case (1)
            return p
        elif p.right==None:             # case (2)
            return p
        elif p.left==None:              # case (3)
            return p
        else:                   # case (4) 
            return p
    self.root = recurse (self.root)

显然，对于每个条件，应该不仅仅返回p。我非常确定第一个if和两个elif用于"定位"包含x的节点。但是我不确定如何实现这四种情况。任何意见都将不胜感激。

此外，最终目标是使用此方法迭代BST并删除每个节点。

Answer 1

好吧，你的第一步是定位X，记住你是通过递归来完成的，所以你应该在它所定位的子树上递归remove函数。（左如果x<p.data，右如果更高……仅当它们存在时）。接下来，您需要担心一旦找到x（x=p.data）该怎么办。

我建议画一棵树，并将其作为一种算法进行思考。：）

记住BST属性！为了保护财产，这棵树必须修改它的结构，那么……谁是孤独孩子的新父亲？提示：

可能是兄弟姐妹？

记住BST特征

递归！！）

Answer 2

pseudo_code method_recurse需要参数：this_node

1. 如果this_node为None，则返回None Found
2. 如果this_node是目标，则返回this_node
3. 如果this_node是less_than目标，则使用this_node.right返回call self
4. 如果this_node大于target，则使用this_node.left返回call self