删除 BST 中的节点 Python
Deleting node in BST Python
这是在Python中为BST实现添加和删除功能的可能方法。它有点类似于我对 C++ 中 BST 的想法。从用于删除的代码可以看出，我想删除一个节点，由于 Python 中缺少按引用传递，我不能这样做，因为它存在于 C++ 中。除了 del currNode 之外，删除节点的另一种好方法是什么（这不起作用）。我还有一个问题要澄清我关于在 Python 中通过引用传递的想法，当一个节点正在使用 add 函数添加时，它仍然“附加”到根节点，当添加被调用时递归地。然而，当一个节点被删除时，它并没有从根节点“分离”。为什么会这样？
class node(object):
def __init__(self, data = None):
self.data = data
self.left = None
self.right = None
class bst(object):
def __init__(self):
self.root = None
def add(self, value):
def _add(self, currNode, value):
if value < currNode.data:
if currNode.left == None:
currNode.left = node(value)
else:
_add(self, currNode.left, value)
elif value > currNode.data:
if currNode.right == None:
currNode.right = node(value)
else:
_add(self, currNode.right, value)
else:
print("Duplicate found")
if self.root == None:
self.root = node(value)
else:
_add(self, self.root, value)
def printBST(self):
def _printBST(self, currNode):
if currNode!= None:
_printBST(self, currNode.left)
print(currNode.data, end = " ")
_printBST(self, currNode.right)
if self.root != None:
_printBST(self,self.root)
def minBST(self,currNode):
def _minBST(self, currNode):
if currNode.left == None:
return currNode.data
else: return _minBST(self, currNode.left)
if currNode != None:
return _minBST(self, currNode)
else:
return -10000
def deleteValue(self, val):
def deleteNode(self, currNode, value):
if currNode == None:
return
elif value > currNode.data:
return deleteNode(self, currNode.right, value)
elif value < currNode.data:
return deleteNode(self, currNode.left, value)
else:
if currNode.left == None and currNode.right == None:
#del currNode
currNode.data = None
elif currNode.right == None:
currNode.data = None
#The address of currNode does not change
#as it happens in C++
#currNode = currNode.left
elif currNode.left == None:
currNode.data = None
#The address of currNode does not change
#currNode = currNode.right
else:
minV = self.minBST(currNode.right)
currNode.data = minV
return deleteNode(self, currNode.right, minV)
deleteNode(self, self.root, val)
if __name__ == '__main__':
b = bst()
b.add(50)
b.add(60)
b.add(40)
b.add(30)
b.add(45)
b.add(55)
b.add(100)
b.printBST()
b.deleteValue(100)
print("")
b.printBST()
您可以重新分配父节点并让垃圾收集器收集子节点，而不是使用 del 删除节点。
在deleteNode return中新建子节点而不是删除节点。将 returned 值分配给父级。
def deleteNode(self, currNode, value):
if not currNode:
return currNode
elif value < currNode.data:
return deleteNode(self, currNode.left, value)
elif value > currNode.data:
return deleteNode(self, currNode.right, value)
else:
if not currNode.right:
return currNode.left
if not currNode.left:
return currNode.right
temp_val = currNode.right
mini_val = temp_val.val
while temp_val.left:
temp_val = temp_val.left
mini_val = temp_val.val
currNode.right = deleteNode(currNode.right,currNode.val)
return currNode
节点结构和插入
我们从一个简单的node结构开始，但是注意left和right属性可以在构造时设置-
# btree.py
class node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
递归是一种函数式继承，因此将它与函数式风格结合使用会产生最佳效果。这意味着要避免诸如突变、变量重新分配和其他副作用之类的事情。注意 add 如何总是构造一个 new 节点而不是改变旧节点。这就是我们设计 node 在构建时接受所有属性的原因 -
# btree.py (continued)
def add(t, q):
if not t:
return node(q)
elif q < t.data:
return node(t.data, add(t.left, q), t.right)
elif q > t.data:
return node(t.data, t.left, add(t.right, q))
else:
return node(q, t.left, t.right)
中序遍历和字符串转换
在我们 add 一些节点之后，我们需要一种可视化树的方法。下面我们写一个inorder遍历和一个to_str函数-
# btree.py (continued)
def inorder(t):
if not t: return
yield from inorder(t.left)
yield t.data
yield from inorder(t.right)
def to_str(t):
return "->".join(map(str,inorder(t)))
btree对象接口
请注意，我们并没有将上面的普通函数与 class 纠缠在一起，从而使它们过于复杂。我们现在可以定义一个 btree 面向对象的接口，它简单地包装了普通函数 -
# btree.py (continued)
class btree:
def __init__(self, t=None): self.t = t
def __str__(self): return to_str(self.t)
def add(self, q): return btree(add(self.t, q))
def inorder(self): return inorder(self.t)
注意我们也写了 btree.py 作为它自己的模块。这定义了抽象的障碍，并允许我们扩展、修改和重用功能，而不会将它们与程序的其他区域纠缠在一起。让我们看看我们的树到目前为止是如何工作的 -
# main.py
from btree import btree
t = btree().add(50).add(60).add(40).add(30).add(45).add(55).add(100)
print(str(t))
# 30->40->45->50->55->60->100
最小和最大
我们将继续这样工作，定义直接作用于 node 对象的普通函数。接下来，minimum 和 maximum -
# btree.py (continued)
from math import inf
def minimum(t, r=inf):
if not t:
return r
elif t.data < r:
return min(minimum(t.left, t.data), minimum(t.right, t.data))
else:
return min(minimum(t.left, r), minimum(t.right, r))
def maximum(t, r=-inf):
if not t:
return r
elif t.data > r:
return max(maximum(t.left, t.data), maximum(t.right, t.data))
else:
return max(maximum(t.left, r), maximum(t.right, r))
btree 接口只提供了普通函数的包装器 -
# btree.py (continued)
class btree:
def __init__(): # ...
def __str__(): # ...
def add(): # ...
def inorder(): # ...
def maximum(self): return maximum(self.t)
def minimum(self): return minimum(self.t)
我们现在可以测试 minimum 和 maximum -
# main.py
from btree import btree
t = btree().add(50).add(60).add(40).add(30).add(45).add(55).add(100)
print(str(t))
# 30->40->45->50->55->60->100
print(t.minimum(), t.maximum()) # <-
# 30 100
从迭代中插入
链接 .add().add().add() 有点冗长。提供一个 add_iter 函数允许我们从另一个可迭代对象中插入任意数量的值。我们现在介绍它是因为我们即将在即将推出的 remove 功能中重用它 -
def add_iter(t, it):
for q in it:
t = add(t, q)
return t
#main.py
from btree import btree
t = btree().add_iter([50, 60, 40, 30, 45, 55, 100]) # <-
print(str(t))
# 30->40->45->50->55->60->100
print(t.minimum(), t.maximum())
# 30 100
节点移除和前序遍历
我们现在转到 remove 函数。它的工作原理类似于 add 函数，执行 t.data 与要删除的值 q 的比较。您会注意到我们在这里使用 add_iter 来组合要删除的节点的 left 和 right 分支。我们 可以 在这里为我们的树重用 inorder 迭代器，但是 preorder 会使树更加平衡。那是完全不同的话题，所以我们现在不谈这个话题 -
# btree.py (continued)
def remove(t, q):
if not t:
return t
elif q < t.data:
return node(t.data, remove(t.left, q), t.right)
elif q > t.data:
return node(t.data, t.left, remove(t.right, q))
else:
return add_iter(t.left, preorder(t.right))
def preorder(t):
if not t: return
yield t.data
yield from preorder(t.left)
yield from preorder(t.right)
别忘了扩展 btree 接口 -
# btree.py (continued)
class btree:
def __init__(): # ...
def __str__(): # ...
def add(): # ...
def inorder(): # ...
def maximum(): # ...
def minimum(): # ...
def add_iter(self, it): return btree(add_iter(self.t, it))
def remove(self, q): return btree(remove(self.t, q))
def preorder(self): return preorder(self.t)
让我们看看 remove 的实际效果 -
# main.py
from btree import btree
t = btree().add_iter([50, 60, 40, 30, 45, 55, 100])
print(str(t))
# 30->40->45->50->55->60->100
print(t.minimum(), t.maximum())
# 30 100
t = t.remove(30).remove(50).remove(100) # <-
print(str(t))
# 40->45->55->60
print(t.minimum(), t.maximum())
# 40 60
完成 btree 模块
这是我们在此答案过程中构建的完整模块 -
from math import inf
class node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def add(t, q):
if not t:
return node(q)
elif q < t.data:
return node(t.data, add(t.left, q), t.right)
elif q > t.data:
return node(t.data, t.left, add(t.right, q))
else:
return node(q, t.left, t.right)
def add_iter(t, it):
for q in it:
t = add(t, q)
return t
def maximum(t, r=-inf):
if not t:
return r
elif t.data > r:
return max(maximum(t.left, t.data), maximum(t.right, t.data))
else:
return max(maximum(t.left, r), maximum(t.right, r))
def minimum(t, r=inf):
if not t:
return r
elif t.data < r:
return min(minimum(t.left, t.data), minimum(t.right, t.data))
else:
return min(minimum(t.left, r), minimum(t.right, r))
def inorder(t):
if not t: return
yield from inorder(t.left)
yield t.data
yield from inorder(t.right)
def preorder(t):
if not t: return
yield t.data
yield from preorder(t.left)
yield from preorder(t.right)
def remove(t, q):
if not t:
return t
elif q < t.data:
return node(t.data, remove(t.left, q), t.right)
elif q > t.data:
return node(t.data, t.left, remove(t.right, q))
else:
return add_iter(t.left, preorder(t.right))
def to_str(t):
return "->".join(map(str,inorder(t)))
class btree:
def __init__(self, t=None): self.t = t
def __str__(self): return to_str(self.t)
def add(self, q): return btree(add(self.t, q))
def add_iter(self, it): return btree(add_iter(self.t, it))
def maximum(self): return maximum(self.t)
def minimum(self): return minimum(self.t)
def inorder(self): return inorder(self.t)
def preorder(self): return preorder(self.t)
def remove(self, q): return btree(remove(self.t, q))
吃蛋糕也吃
上述方法的一个低估的优点是我们的 btree 模块有一个 双 接口。我们可以像演示的那样以传统的面向对象的方式使用它，或我们可以使用更函数式的方法使用它-
# main.py
from btree import add_iter, remove, to_str, minimum, maximum
t = add_iter(None, [50, 60, 40, 30, 45, 55, 100])
print(to_str(t))
# 30->40->45->50->55->60->100
print(minimum(t), maximum(t))
# 30 100
t = remove(remove(remove(t, 30), 50), 100)
print(to_str(t))
# 40->45->55->60
print(minimum(t), maximum(t))
# 40 60
补充阅读
我已经详细介绍了此答案中使用的技术。按照链接查看它们在其他情况下的使用情况，并提供额外的解释 -
I want to reverse the stack but i dont know how to use recursion for reversing this… How can i reverse the stack without using Recursion
Finding all maze solutions with Python
Return middle node of linked list with recursion
这是在Python中为BST实现添加和删除功能的可能方法。它有点类似于我对 C++ 中 BST 的想法。从用于删除的代码可以看出，我想删除一个节点，由于 Python 中缺少按引用传递，我不能这样做，因为它存在于 C++ 中。除了 del currNode 之外，删除节点的另一种好方法是什么（这不起作用）。我还有一个问题要澄清我关于在 Python 中通过引用传递的想法，当一个节点正在使用 add 函数添加时，它仍然“附加”到根节点，当添加被调用时递归地。然而，当一个节点被删除时，它并没有从根节点“分离”。为什么会这样？
class node(object):
def __init__(self, data = None):
self.data = data
self.left = None
self.right = None
class bst(object):
def __init__(self):
self.root = None
def add(self, value):
def _add(self, currNode, value):
if value < currNode.data:
if currNode.left == None:
currNode.left = node(value)
else:
_add(self, currNode.left, value)
elif value > currNode.data:
if currNode.right == None:
currNode.right = node(value)
else:
_add(self, currNode.right, value)
else:
print("Duplicate found")
if self.root == None:
self.root = node(value)
else:
_add(self, self.root, value)
def printBST(self):
def _printBST(self, currNode):
if currNode!= None:
_printBST(self, currNode.left)
print(currNode.data, end = " ")
_printBST(self, currNode.right)
if self.root != None:
_printBST(self,self.root)
def minBST(self,currNode):
def _minBST(self, currNode):
if currNode.left == None:
return currNode.data
else: return _minBST(self, currNode.left)
if currNode != None:
return _minBST(self, currNode)
else:
return -10000
def deleteValue(self, val):
def deleteNode(self, currNode, value):
if currNode == None:
return
elif value > currNode.data:
return deleteNode(self, currNode.right, value)
elif value < currNode.data:
return deleteNode(self, currNode.left, value)
else:
if currNode.left == None and currNode.right == None:
#del currNode
currNode.data = None
elif currNode.right == None:
currNode.data = None
#The address of currNode does not change
#as it happens in C++
#currNode = currNode.left
elif currNode.left == None:
currNode.data = None
#The address of currNode does not change
#currNode = currNode.right
else:
minV = self.minBST(currNode.right)
currNode.data = minV
return deleteNode(self, currNode.right, minV)
deleteNode(self, self.root, val)
if __name__ == '__main__':
b = bst()
b.add(50)
b.add(60)
b.add(40)
b.add(30)
b.add(45)
b.add(55)
b.add(100)
b.printBST()
b.deleteValue(100)
print("")
b.printBST()
您可以重新分配父节点并让垃圾收集器收集子节点，而不是使用 del 删除节点。
在deleteNode return中新建子节点而不是删除节点。将 returned 值分配给父级。
def deleteNode(self, currNode, value):
if not currNode:
return currNode
elif value < currNode.data:
return deleteNode(self, currNode.left, value)
elif value > currNode.data:
return deleteNode(self, currNode.right, value)
else:
if not currNode.right:
return currNode.left
if not currNode.left:
return currNode.right
temp_val = currNode.right
mini_val = temp_val.val
while temp_val.left:
temp_val = temp_val.left
mini_val = temp_val.val
currNode.right = deleteNode(currNode.right,currNode.val)
return currNode
节点结构和插入
我们从一个简单的node结构开始，但是注意left和right属性可以在构造时设置-
# btree.py
class node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
递归是一种函数式继承，因此将它与函数式风格结合使用会产生最佳效果。这意味着要避免诸如突变、变量重新分配和其他副作用之类的事情。注意 add 如何总是构造一个 new 节点而不是改变旧节点。这就是我们设计 node 在构建时接受所有属性的原因 -
# btree.py (continued)
def add(t, q):
if not t:
return node(q)
elif q < t.data:
return node(t.data, add(t.left, q), t.right)
elif q > t.data:
return node(t.data, t.left, add(t.right, q))
else:
return node(q, t.left, t.right)
中序遍历和字符串转换
在我们 add 一些节点之后，我们需要一种可视化树的方法。下面我们写一个inorder遍历和一个to_str函数-
# btree.py (continued)
def inorder(t):
if not t: return
yield from inorder(t.left)
yield t.data
yield from inorder(t.right)
def to_str(t):
return "->".join(map(str,inorder(t)))
btree对象接口
请注意，我们并没有将上面的普通函数与 class 纠缠在一起，从而使它们过于复杂。我们现在可以定义一个 btree 面向对象的接口，它简单地包装了普通函数 -
# btree.py (continued)
class btree:
def __init__(self, t=None): self.t = t
def __str__(self): return to_str(self.t)
def add(self, q): return btree(add(self.t, q))
def inorder(self): return inorder(self.t)
注意我们也写了 btree.py 作为它自己的模块。这定义了抽象的障碍，并允许我们扩展、修改和重用功能，而不会将它们与程序的其他区域纠缠在一起。让我们看看我们的树到目前为止是如何工作的 -
# main.py
from btree import btree
t = btree().add(50).add(60).add(40).add(30).add(45).add(55).add(100)
print(str(t))
# 30->40->45->50->55->60->100
最小和最大
我们将继续这样工作，定义直接作用于 node 对象的普通函数。接下来，minimum 和 maximum -
# btree.py (continued)
from math import inf
def minimum(t, r=inf):
if not t:
return r
elif t.data < r:
return min(minimum(t.left, t.data), minimum(t.right, t.data))
else:
return min(minimum(t.left, r), minimum(t.right, r))
def maximum(t, r=-inf):
if not t:
return r
elif t.data > r:
return max(maximum(t.left, t.data), maximum(t.right, t.data))
else:
return max(maximum(t.left, r), maximum(t.right, r))
btree 接口只提供了普通函数的包装器 -
# btree.py (continued)
class btree:
def __init__(): # ...
def __str__(): # ...
def add(): # ...
def inorder(): # ...
def maximum(self): return maximum(self.t)
def minimum(self): return minimum(self.t)
我们现在可以测试 minimum 和 maximum -
# main.py
from btree import btree
t = btree().add(50).add(60).add(40).add(30).add(45).add(55).add(100)
print(str(t))
# 30->40->45->50->55->60->100
print(t.minimum(), t.maximum()) # <-
# 30 100
从迭代中插入
链接 .add().add().add() 有点冗长。提供一个 add_iter 函数允许我们从另一个可迭代对象中插入任意数量的值。我们现在介绍它是因为我们即将在即将推出的 remove 功能中重用它 -
def add_iter(t, it):
for q in it:
t = add(t, q)
return t
#main.py
from btree import btree
t = btree().add_iter([50, 60, 40, 30, 45, 55, 100]) # <-
print(str(t))
# 30->40->45->50->55->60->100
print(t.minimum(), t.maximum())
# 30 100
节点移除和前序遍历
我们现在转到 remove 函数。它的工作原理类似于 add 函数，执行 t.data 与要删除的值 q 的比较。您会注意到我们在这里使用 add_iter 来组合要删除的节点的 left 和 right 分支。我们 可以 在这里为我们的树重用 inorder 迭代器，但是 preorder 会使树更加平衡。那是完全不同的话题，所以我们现在不谈这个话题 -
# btree.py (continued)
def remove(t, q):
if not t:
return t
elif q < t.data:
return node(t.data, remove(t.left, q), t.right)
elif q > t.data:
return node(t.data, t.left, remove(t.right, q))
else:
return add_iter(t.left, preorder(t.right))
def preorder(t):
if not t: return
yield t.data
yield from preorder(t.left)
yield from preorder(t.right)
别忘了扩展 btree 接口 -
# btree.py (continued)
class btree:
def __init__(): # ...
def __str__(): # ...
def add(): # ...
def inorder(): # ...
def maximum(): # ...
def minimum(): # ...
def add_iter(self, it): return btree(add_iter(self.t, it))
def remove(self, q): return btree(remove(self.t, q))
def preorder(self): return preorder(self.t)
让我们看看 remove 的实际效果 -
# main.py
from btree import btree
t = btree().add_iter([50, 60, 40, 30, 45, 55, 100])
print(str(t))
# 30->40->45->50->55->60->100
print(t.minimum(), t.maximum())
# 30 100
t = t.remove(30).remove(50).remove(100) # <-
print(str(t))
# 40->45->55->60
print(t.minimum(), t.maximum())
# 40 60
完成 btree 模块
这是我们在此答案过程中构建的完整模块 -
from math import inf
class node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def add(t, q):
if not t:
return node(q)
elif q < t.data:
return node(t.data, add(t.left, q), t.right)
elif q > t.data:
return node(t.data, t.left, add(t.right, q))
else:
return node(q, t.left, t.right)
def add_iter(t, it):
for q in it:
t = add(t, q)
return t
def maximum(t, r=-inf):
if not t:
return r
elif t.data > r:
return max(maximum(t.left, t.data), maximum(t.right, t.data))
else:
return max(maximum(t.left, r), maximum(t.right, r))
def minimum(t, r=inf):
if not t:
return r
elif t.data < r:
return min(minimum(t.left, t.data), minimum(t.right, t.data))
else:
return min(minimum(t.left, r), minimum(t.right, r))
def inorder(t):
if not t: return
yield from inorder(t.left)
yield t.data
yield from inorder(t.right)
def preorder(t):
if not t: return
yield t.data
yield from preorder(t.left)
yield from preorder(t.right)
def remove(t, q):
if not t:
return t
elif q < t.data:
return node(t.data, remove(t.left, q), t.right)
elif q > t.data:
return node(t.data, t.left, remove(t.right, q))
else:
return add_iter(t.left, preorder(t.right))
def to_str(t):
return "->".join(map(str,inorder(t)))
class btree:
def __init__(self, t=None): self.t = t
def __str__(self): return to_str(self.t)
def add(self, q): return btree(add(self.t, q))
def add_iter(self, it): return btree(add_iter(self.t, it))
def maximum(self): return maximum(self.t)
def minimum(self): return minimum(self.t)
def inorder(self): return inorder(self.t)
def preorder(self): return preorder(self.t)
def remove(self, q): return btree(remove(self.t, q))
吃蛋糕也吃
上述方法的一个低估的优点是我们的 btree 模块有一个 双 接口。我们可以像演示的那样以传统的面向对象的方式使用它，或我们可以使用更函数式的方法使用它-
# main.py
from btree import add_iter, remove, to_str, minimum, maximum
t = add_iter(None, [50, 60, 40, 30, 45, 55, 100])
print(to_str(t))
# 30->40->45->50->55->60->100
print(minimum(t), maximum(t))
# 30 100
t = remove(remove(remove(t, 30), 50), 100)
print(to_str(t))
# 40->45->55->60
print(minimum(t), maximum(t))
# 40 60
补充阅读
我已经详细介绍了此答案中使用的技术。按照链接查看它们在其他情况下的使用情况，并提供额外的解释 -
I want to reverse the stack but i dont know how to use recursion for reversing this… How can i reverse the stack without using Recursion
Finding all maze solutions with Python
Return middle node of linked list with recursion