问题描述
下面的代码是我的二进制搜索树的实现,并且我想实现delete方法以删除该节点.以下是我的实现,但是当我执行
The code below is my implement for my binary search tree, and I want to implement delete method to remove the node. Below is my implementation, but when I perform
bst = BSTRee()
bst.insert(5)
bst.insert(11)
bst.insert(3)
bst.insert(4)
bst.insert(12)
bst.insert(2)
bst.delete(3)
当我调用delete方法时,它什么也没做.有人可以帮我修复它.下面的链接是我在github上的代码.非常感谢你的帮助. https://github.com/hly189/sort/blob/master/tree/BST.py
when I call delete method, it did nothing. Can someone help me to fix it. The link below is my code on github. Thank you so much for your help.https://github.com/hly189/sort/blob/master/tree/BST.py
class BSTreeNode
def ____init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(self,key):
if self.value == key:
print ("the node already exists")
return False
elif self.value > key:
if self.left is not None:
return self.left.insert(key)
else:
self.left = BSTreeNode(key)
return True
else:
if self.right is not None:
return self.right.insert(key)
else:
self.right = BSTreeNode(key)
return False
def delete(self, node, k):
if node == None:
return None
elif node.value == k:
if node.left is None and node.right is None:
return None
elif node.left is None:
return node.right
elif node.right is None:
return node.left
else:
node.value = get_min(node.right)
node.right.delete(node.right,node.value)
elif k < node.value:
node.left.delete(node.left,k)
else:
node.right.delete(node.right,k)
return node
class BSTree:
def __init__(self):
self.root = None
def delete(self,key):
self.root.delete(self.root,key)
def insert(self,data):
if self.root:
self.root.insert(data)
else:
self.root = BSTreeNode(data)
return True
def find_min(self,node):
current_node = node
while current_node.left:
current_node = current_node.left
return current_node
def get_min(node):
current_node = node
while current_node.left:
current_node = current_node.left
return str(current_node.value)
def print_helper(root, indent):
if root is not None:
print_helper(root.right, indent + " ")
print (indent + str(root.value))
print_helper(root.left, indent + " ")
def print_tree(root):
print_helper(root, "")
推荐答案
def delete(self, key):
""" delete the node with the given key and return the
root node of the tree """
if self.key == key:
# found the node we need to delete
if self.right and self.left:
# get the successor node and its parent
[psucc, succ] = self.right._findMin(self)
# splice out the successor
# (we need the parent to do this)
if psucc.left == succ:
psucc.left = succ.right
else:
psucc.right = succ.right
# reset the left and right children of the successor
succ.left = self.left
succ.right = self.right
return succ
else:
# "easier" case
if self.left:
return self.left # promote the left subtree
else:
return self.right # promote the right subtree
else:
if self.key > key: # key should be in the left subtree
if self.left:
self.left = self.left.delete(key)
# else the key is not in the tree
else: # key should be in the right subtree
if self.right:
self.right = self.right.delete(key)
return self
def _findMin(self, parent):
""" return the minimum node in the current tree and its parent """
# we use an ugly trick: the parent node is passed in as an argument
# so that eventually when the leftmost child is reached, the
# call can return both the parent to the successor and the successor
if self.left:
return self.left._findMin(self)
else:
return [parent, self]
这可能会有所帮助.有关完整的代码和更好的理解,请访问对于代码 Python中的二进制搜索树
This might help. For complete code and better understanding go toFor codeBinary search Tree in Python
说明关于Python中BST的注意事项据我所知,它工作正常.
For explanationNotes on BST in PythonAs per my knowledge its working fine.
这篇关于删除二进制搜索树python中的节点的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!