如何使用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吗 德尔的使用不好吗？

复杂性是可以的。