我是Python的初学者，曾尝试创建一个函数来删除二进制搜索树中的节点。
我尝试在节点上调用.delete。该节点是一个没有子节点的叶节点，因此应将其删除。但是，在我调用.delete之后，节点仍然存在。
这是代码：
class Node:
def __init__(self,key):
self.left = None
self.right = None
self.val = key
#some functions for insert etc.
def delete(self, key):
"""DELETE"""
try:
if self is None:
print("Tree is empty.")
return None
else:
if key < self.val:
self.left.delete(key)
elif key > self.val:
self.right.delete(key)
else:
#this seems to be the problem
if self.left is None :
temp = self.right
#print(self, self.val, self.right)
self = temp
return
elif self.right is None :
temp = self.left
self = temp
return
temp = minValue(self.right)
self.val = temp.val
self.right.delete(temp.val)
except(AttributeError):
print("There's no such number in a tree.")
def inorder(root):
if root is not None:
inorder(root.left)
print(root.val, end=" ")
inorder(root.right)
def minValue(node):
current = node
while(current.left is not None):
current = current.left
return current
r = Node(50)
在插入数字30 20 40 70 60 80到r并调用inorder(r)之后，我得到：20 30 40 50 60 70 80，它对应于树
50
/
30 70
/ /
20 40 60 80
但在r.delete(30)之后，我得到：20 40 40 50 60 70 80，即：
50
/
40 70
/ /
20 40 60 80
将正确替换要删除的值，但应删除已使用的没有子节点的节点(40(。
出现这种问题的原因可能是什么？
简单地说，您不能为self分配任何内容。在Python中，self是对您调用方法的对象的引用。它不会是None(因此您不需要if self is None检查(，也不能为它分配其他值。
但是，从树中删除节点时，可能会删除当前节点(您在其中调用delete的节点(。我们可以使delete返回一个节点对象，而不是为self赋值。如果当前节点没有被删除，只需返回自身；否则，返回将取代它的节点(如果整个子树都不存在，则返回None(。
以下是修改后的实现，以及insert方法和测试用例：
class Node:
def __init__(self, key):
self.left = self.right = None
self.val = key
def delete(self, key):
"""Delete a node with value `key`."""
if key < self.val:
# Find and delete the value in the left subtree.
if self.left is None:
# There's no left subtree; the value does not exist.
raise ValueError("Value not found in tree")
self.left = self.left.delete(key)
return self # current node not deleted, just return
elif key > self.val:
# Find and delete the value in the right subtree.
if self.right is None:
# There's no right subtree; the value does not exist.
raise ValueError("Value not found in tree")
self.right = self.right.delete(key)
return self # current node not deleted, just return
else:
# The current node should be deleted.
if self.left is None and self.right is None:
# The node has no children -- it is a leaf node. Just delete.
return None
# If the node has only one children, simply return that child.
if self.left is None:
return self.right
if self.right is None:
return self.left
# The node has both left and right subtrees, and they should be merged.
# Following your implementation, we find the rightmost node in the
# left subtree and replace the current node with it.
parent, node = self, self.left
while node.right is not None:
parent, node = node, node.right
# Now, `node` is the rightmost node in the left subtree, and
# `parent` its parent node. Instead of replacing `self`, we change
# its attributes to match the value of `node`.
if parent.left is node:
# This check is necessary, because if the left subtree has only
# node, `node` would be `self.left`.
parent.left = None
else:
parent.right = None
self.val = node.val
return self
def insert(self, key):
if key < self.val:
if self.left is None:
self.left = Node(key)
else:
self.left.insert(key)
else:
if self.right is None:
self.right = Node(key)
else:
self.right.insert(key)
def inorder_traverse(node):
if node is None:
return []
ret = []
if node.left is not None:
ret += inorder_traverse(node.left)
ret.append(node.val)
if node.right is not None:
ret += inorder_traverse(node.right)
return ret
values = [5, 1, 2, 7, 3, 6, 4]
root = Node(values[0])
for x in values[1:]:
root.insert(x)
print(inorder_traverse(root))
for x in values:
root = root.delete(x)
print(inorder_traverse(root))
输出如预期：
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 6, 7]
[2, 3, 4, 6, 7]
[3, 4, 6, 7]
[3, 4, 6]
[4, 6]
[4]
[]