python - 如何使用Python删除二叉搜索树中的节点

Question

def delete_a_node(self,data):
    if self.root==None:
        print("Empty BST")
    else:
        parent=None
        node=self.root
        replace_node=None
        while(node!=None and node.data!=data):
            parent=node
            if data>=node.data:
                node=node.rightchild
                flag=1
            else:
                node=node.leftchild
                flag=0

        if node is None:
            print("node not in BST.")
        else:
            if (node.leftchild==None) and (node.rightchild==None):
                if (flag):
                    parent.rightchild=None
                else:
                    parent.leftchild=None
                del node
            elif (node.leftchild==None) or (node.rightchild==None):
                if node.leftchild==None:
                    if(flag):
                        parent.rightchild=node.rightchild
                    else:
                        parent.leftchild=node.rightchild
                else  :
                    if(flag):
                        parent.rightchild==node.leftchild
                    else:
                        parent.leftchild=node.leftchild

                del node


            else:
                 replace_node,parent=self.minimum_element(node.rightchild)
                 node=replace_node
                 if parent==None:
                     node.rightchild=None
                 else:
                     parent.leftchild=None
                  del replace_node





def minimum_element(self,node):
    if self.root==None:
        print("Empty BST")
    else:
        parent=None
        while(node.leftchild!=None):
            parent=node
            node=node.leftchild
        return (node,parent)

大家好，我试图从二叉搜索树中删除一个节点。我尝试从https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/学习它。因为，他们在代码中使用了递归。我无法很好地理解它。

所以，我尝试编写这段代码。这里我在init方法中初始化root，剩下的两个方法就在前面了。

  def __init__(self):
    self.root=None

FLAG变量:我用它来查找父节点和数据节点之间的关系(我们要删除)。

据我们所知，有三种情况

1. 当我们要删除的节点没有子节点时(工作正常)
2. 当我们要删除的节点有一个子节点时(工作正常)
3. 当我们要删除的节点有两个子节点时(问题在这里)

请问谁能帮我解决这个代码吗？

你介意让我看看吗

1. 从 BST 中删除节点的正确方法
2. 我是否应该在Python中使用del node，因为我刚刚读到Python中不需要释放空间。
3. 与https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/相比，我的复杂性是否太多了？代码？

输出:

bst.inorder()25--15--10--4--12--22--18--24--50--35--31--44--70--66--55--90--105- -120--

bst.delete_a_node(15)

bst.inorder()25--15--10--4--12--22--18--24--50--35--31--44--70--66--55--90--105- -120--

提前谢谢您:)

Answer 1

    def delete_a_node(self,data):
    if self.root==None:
        print("Empty BST")
    else:
        parent=None
        node=self.root
        replace_node=None
        while(node!=None and node.data!=data):
            parent=node
            if data>=node.data:
                node=node.rightchild
                flag=1
            else:
                node=node.leftchild
                flag=0


        if node is None:
            print("node not in BST.")

        else:


            if (node.leftchild==None) and (node.rightchild==None):
                if (flag):
                    parent.rightchild=None
                else:
                    parent.leftchild=None
                del node

            elif (node.leftchild==None) or (node.rightchild==None):
                if node.leftchild==None:
                    if(flag):
                        parent.rightchild=node.rightchild
                    else:
                        parent.leftchild=node.rightchild
                else  :
                    if(flag):
                        parent.rightchild==node.leftchild
                    else:
                        parent.leftchild=node.leftchild

                del node


            else:
                 replace_node=self.minimum_element(node.rightchild)
                 temp=replace_node.data
                 self.delete_a_node(replace_node.data)
                 node.data=temp

def minimum_element(self,node):
    if self.root==None:
        print("Empty BST")
    else:
        while(node.leftchild!=None):
            node=node.leftchild
        print(node.data)
        return (node)

所以，请在评论部分提供帮助。我完成了代码。非常感谢，伙计们。

我是否应该使用del Is the use of del bad?

复杂性还可以。