我试图从BST中删除最小节点,所以我在树中搜索直到得到最小值(当根.leftnode无)然后设置root.rightnode以继续BST
问题是,当我在执行此操作后检查树时,它不会显示曾经发生过的删除操作。在
有人能给我指点正确的方向吗?如有任何建议,不胜感激。在
class node():
def __init__(self, key, data):
self.data = data
self.key = key
self.leftnode = None
self.rightnode = None
self.count = 1
class binarysearch():
def __init__(self):
self.size = 0
self.rootnode = None
def insert(self, key, data):
if self.rootnode is None:
self.rootnode = node(key, data)
else:
self.insertnode(self.rootnode, key, data)
def getroot(self):
return self.rootnode
def insertnode(self, root, key, data):
if root.key == key:
root.data = data
elif key < root.key:
if root.leftnode is None:
root.leftnode = node(key, data)
else:
self.insertnode(root.leftnode, key, data)
else:
if root.rightnode is None:
root.rightnode = node(key, data)
else:
self.insertnode(root.rightnode, key, data)
root.count = 1 + self.sizenode(root.leftnode) + self.sizenode(root.rightnode)
def inorder(self, root):
if root is not None:
self.inorder(root.leftnode)
print(root.key)
self.inorder(root.rightnode)
def deletemin(self):
if self.rootnode is None:
print("No nodes exist")
else:
self.deleteminnode(self.rootnode.leftnode)
def deleteminnode(self, root):
if root.leftnode is not None:
self.deleteminnode(root.leftnode)
else:
print (root.key, "deleted")
root = root.rightnode
if __name__ == '__main__':
a = binarysearch()
a.insert(7,7)
a.insert(1,1)
a.insert(8,8)
a.insert(3,3)
a.insert(9,9)
a.insert(2,2)
a.insert(4,4)
a.insert(11,11)
a.insert(10,10)
a.deletemin()
a.getnodes()
您可以找到树中的所有节点以及节点的路径,找到结果的最小值,然后遍历生成的路径以删除节点:
创建:
^{pr2}$输出:
问题是
root = root.rightnode
只重新绑定局部变量root
。它不会更改对该节点的其他引用位置(例如树中的父节点)。在要解决这个问题,您需要更改递归函数的工作方式。与其期望它完成最后一次调用中的所有工作,它应该
return
该值应该是其父节点的左节点。然后,这将是节点本身,但对于最小节点,它将是其正确的子节点。在关于名称的最后一点注意:使用
root
作为树中随机节点的名称有点奇怪。通常一棵树只有一个根节点,而其他节点没有被称为root
,因为它们有父节点。不幸的是,最传统的名称node
已经用于您的node类。通常,类应该被赋予CapitalizedNames
,这样lowercase_names
可以独占地引用实例和其他变量。不过,这只是惯例(而像list
这样的内置类型违反了规则)。如果您使用标准的名称样式,其他人可能更容易理解您的代码,但Python不强制执行它们。它将允许你使用任何你想要的名字。即使名称self
也不是必需的,尽管如果没有合理的理由为方法的第一个参数使用不同的名称(一个很好的理由的例子:类方法和元类的方法通常使用cls
作为其第一个参数的名称,因为对象将是一个类)。在相关问题 更多 >
编程相关推荐