使用递归从二进制搜索树中删除节点 [英] deleting a node from a binary search tree using recursion
问题描述
所以我试图通过使用类中的这两个函数从树中删除一个节点.不幸的是，它只是不删除任何东西，我想知道这是怎么回事！任何帮助将不胜感激.
So I'm trying to delete a node from a tree by using these two functions inside the class.Unfortunately it just doesnt delete anything and i was wondering what is wrong about it! any help would be truly appreciated.
def Find_Min(self,node):
current=node
while current.left is None:
current=current.left
return current
def deletenode(self,node,ntbd): ##ntbd:node to be deleted /// node: root node
if node is None:
return None
elif node.data>ntbd:
node.left=self.deletenode(node.left,ntbd)
elif node.data<ntbd:
node.right=self.deletenode(node.right,ntbd)
else: ##Found you bastard
if node.left==None and node.right==None:
node=None
elif node.left==None:
temp=node.right
node=None
print("----",temp)
elif node.right==None:
temp=node.left
node=None
print("----",temp)
else:
smallest=self.Find_Min(node.right)
node.data=smallest.data
node.right=self.deletenode(node.right,smallest.data)
推荐答案
给出node-
class node:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
让我们创建一棵树t-
t = node \
( 1
, node(2, node(3), node(4))
, node(5, node(6), node(7))
)
哪个代表这棵树-
1
/ \
/ \
2 5
/ \ / \
3 4 6 7
普通功能
第一种打印树的方法to_str-
def to_str (root = None):
if not root:
return "_"
else:
return f"(node {root.data} {to_str(root.left)} {to_str(root.right)})"
print(to_str(t))
# (node 1 (node 2 (node 3 _ _) (node 4 _ _)) (node 5 (node 6 _ _) (node 7 _ _)))
现在有一种方法可以访问delete个节点-
Now a way to delete nodes -
def delete (root = None, q = None):
if not root or root.data == q:
return None
else:
return node(root.data, delete(root.left, q), delete(root.right, q))
print(to_str(t))
# (node 1 (node 2 (node 3 _ _) (node 4 _ _)) (node 5 (node 6 _ _) (node 7 _ _)))
print(to_str(delete(t, 2)))
# (node 1 _ (node 5 (node 6 _ _) (node 7 _ _)))
请注意两个程序之间的相似性.并注意delete返回一棵新树，并且不会破坏旧树-
Notice the similarity between the two programs. And notice delete returns a new tree and does not destroy the old one -
print(to_str(t))
# (node 1 (node 2 (node 3 _ _) (node 4 _ _)) (node 5 (node 6 _ _) (node 7 _ _)))
print(to_str(delete(t, 2)))
# (node 1 _ (node 5 (node 6 _ _) (node 7 _ _)))
print(to_str(delete(t, 3)))
# (node 1 (node 2 _ (node 4 _ _)) (node 5 (node 6 _ _) (node 7 _ _)))
print(to_str(t))
# (node 1 (node 2 (node 3 _ _) (node 4 _ _)) (node 5 (node 6 _ _) (node 7 _ _)))
功能后端，面向对象的前端
如果要将函数作为对象方法添加到某种tree类-
If you want to add functions as object methods to some sort of tree class -
def to_str (root = None):
# defined above ...
def delete (root = None, v = None):
# defined above ...
class tree:
def __init__(self, root = None):
self.root = root
def __str__(self):
return to_str(self.root) # <--
def delete(self, v = None):
return tree(delete(self.root, v)) # <--
这为您提供了与更熟悉的面向对象界面相同的不变(持久)功能-
This gives you the same immutable (persistent) functionality with the more familiar object-oriented interface -
print(tree(t))
# (node 1 (node 2 (node 3 _ _) (node 4 _ _)) (node 5 (node 6 _ _) (node 7 _ _)))
print(tree(t).delete(2))
# (node 1 _ (node 5 (node 6 _ _) (node 7 _ _)))
print(tree(t).delete(3))
# (node 1 (node 2 _ (node 4 _ _)) (node 5 (node 6 _ _) (node 7 _ _)))
print(tree(t))
# (node 1 (node 2 (node 3 _ _) (node 4 _ _)) (node 5 (node 6 _ _) (node 7 _ _)))
功能编程
功能编程很强大，因为程序的形状与数据的形状一致.使用函数，我们可以捕获过程的本质并以实际方式重复使用-
Functional programming is strong because the program's shape harmonises with the data's shape. Using functions, we can capture the essence of a procedure and reuse it in practical ways -
def identity (x = None):
return x
def call (f = identity):
return lambda *a: f(a)
def fold (root = None, f = call(tuple), init = None):
if not root:
return init
else:
return f \
( root.data
, fold(root.left, f, init)
, fold(root.right, f, init)
)
print(fold(t))
# (1, (2, (3, None, None), (4, None, None)), (5, (6, None, None), (7, None, None)))
在下面使用fold，请注意to_str不必关心递归.我们可以将left和right节点视为预折叠的字符串-
Using fold below, notice how to_str doesn't have to concern itself with recursion. We can treat the left and right nodes as pre-folded strings -
def to_str (root = None):
return fold \
( root
, lambda data, left, right: f"(node {data} {left} {right})"
, "_"
)
fold是通用的，允许我们编写各种有用的程序-
fold is generic and allows us to write a variety of useful programs -
def sum (root = None):
return fold \
( root
, lambda data, left, right: data + left + right
, 0
)
print(to_str(t))
# (node 1 (node 2 (node 3 _ _) (node 4 _ _)) (node 5 (node 6 _ _) (node 7 _ _)))
print(sum(t))
#28
print(to_str(delete(t, 5)))
# (node 1 (node 2 (node 3 _ _) (node 4 _ _)) _)
print(sum(delete(t, 5)))
# 19
我不会放弃您问题另一部分的答案，但是这就是我们如何写maximum-
I won't give away the answer to the other part of your question, but here's how we could write maximum -
import inf from math
def maximum (root = None):
return fold \
( root
, lambda data, left, right: max(data, left, right)
, -inf
)
print(maximum(t))
# 7
如果愿意，我们甚至可以使用fold编写delete-
We could even write delete using fold, if we wanted to -
def delete (root = None, q = None):
return fold \
( root
, lambda data, left, right:
node(data, left, right) if data != q else None
, None
)
fold是也可以实现常见的树遍历-
fold is can implement common tree traversals too -
def inorder (root = None):
return fold \
( root
, lambda data, left, right: [ data, *left, *right ]
, []
)
def preorder (root = None):
return fold \
( root
, lambda data, left, right: [ *left, data, *right ]
, []
)
def postorder (root = None):
return fold \
( root
, lambda data, left, right: [ *left, *right, data ]
, []
)
这里还有t一次供参考-
1
/ \
/ \
2 5
/ \ / \
3 4 6 7
print(inorder(t))
# [1, 2, 3, 4, 5, 6, 7]
print(preorder(t))
# [3, 2, 4, 1, 6, 5, 7]
print(postorder(t))
# [3, 4, 2, 6, 7, 5, 1]
扩展前端
功能使处理节点更加容易.如果需要，我们可以返回并将其添加到我们的tree类中-
functionals like fold made it much easier to work with nodes. We can go back and add these to our tree class, if we wanted -
class tree:
# def __init__ ...
# def __str__ ...
# def delete ...
def fold(self, f = call(tuple), init = None):
return fold(self.root, f, init) # <--
def sum(self):
return sum(self.root) # <--
def max(self)
return maximum(self.root) # <--
def inorder(self):
return inorder(self.root) # <--
def preorder(self):
return preorder(self.root) # <--
def postorder(self):
return postorder(self.root) # <--
使用舒适且熟悉-
print(tree(t).inorder())
# [1, 2, 3, 4, 5, 6, 7]
print(tree(t).preorder())
# [3, 2, 4, 1, 6, 5, 7]
print(tree(t).postorder())
# [3, 4, 2, 6, 7, 5, 1]
print(tree(t).sum())
# 28
print(tree(t).max())
# 7
我们可以将许多tree操作链接在一起，甚至可以内联fold-
We can chain many tree operations together and even fold inline -
print(tree(t).delete(7).delete(6).max())
# 5
print(tree(t).fold(lambda v, l, r: [[ v, *l, *r ]], []))
# [[1, [2, [3], [4]], [5, [6], [7]]]]
print(tree(t).delete(3).delete(7).fold(lambda v, l, r: [[ v, *l, *r ]], []))
# [1, [2, [4]], [5, [6]]]]
放松时间
正如我们在各种示例中看到的那样，fold在整个树上工作以计算值.但这并不总是可取的.考虑一个搜索函数，该函数在树中寻找一个值.值匹配后，深入树中搜索的目的是什么?
As we've seen with various examples, fold works over the entire tree to compute a value. But this is not always desirable. Consider a search function that looks for a value in the tree. After the value is matched, what is the purpose in searching deeper into the tree?
Python生成器是惰性的，完全放松的并且可以与普通函数无缝互操作.
Python generators are lazy, totally relaxed, and seamlessly interop with ordinary functions.
def inorder (root = None): # updated definition!
def lazy (data, left, right):
print("computing:", data) # <-- print just for demo purposes
yield data
yield from left # <-- lazy
yield from right # <-- lazy
return fold(root, lazy, []) # <-- normal call to fold
def zip_tree(tx = None, ty = None, traverse = inorder):
return zip(traverse(tx), traverse(ty)) # <-- python zip
def equal (tx = None, ty = None):
for (x, y) in zip_tree(tx, ty):
print("equal?", x, y) # <-- print just for demo purposes
if x != y:
return False
return True
print(equal(t, t))
仅当所有节点值彼此相等时，两棵树才相等
Two trees are equal only if all node values are equal to one another
computing: 1 # tx
computing: 1 # ty
equal? 1 1 # (x, y)
computing: 2 # tx
computing: 2 # ty
equal? 2 2 # (x, y)
computing: 3 # tx
computing: 3 # ty
equal? 3 3 # (x, y)
computing: 4 # tx
computing: 4 # ty
equal? 4 4 # (x, y)
computing: 5 # tx
computing: 5 # ty
equal? 5 5 # (x, y)
computing: 6 # tx
computing: 6 # ty
equal? 6 6 # (x, y)
computing: 7 # tx
computing: 7 # ty
equal? 7 7 # (x, y)
True # <-- answer
但是我们可以得出结论，只要一对节点值不相等，两棵树就不相等-
But we can conclude two trees are unequal as soon as one pair of node values is unequal -
print(equal(t, delete(t, 4)))
computing: 1 # tx
computing: 1 # ty
equal? 1 1 # (x, y)
computing: 2 # tx
computing: 2 # ty
equal? 2 2 # (x, y)
computing: 3 # tx
computing: 4 # ty
equal? 3 4 # (x, y)
False # <-- answer
如上所示，当equal返回早期的False结果时，我们的新惰性inorder不会继续计算.
Demonstrated above, our new lazy inorder does not continue with computation when equal returns an early False result.
Let's remove the print effects and update each inorder, preorder, and postorder with these more so-called Pythonic programs -
def inorder (root = None):
def lazy (data, left, right):
yield data # <-- inorder
yield from left
yield from right
return fold(root, lazy, [])
def preorder (root = None):
def lazy (data, left, right):
yield from left
yield data # <-- preorder
yield from right
return fold(root, lazy, [])
def postorder (root = None):
def lazy (data, left, right):
yield from left
yield from right
yield data # <-- postorder
return fold(root, lazy, [])
def zip_tree (tx = None, ty = None, traverse = inorder):
return zip(traverse(tx), traverse(ty)) # <-- python zip
def equal (tx = None, ty = None):
for (x, y) in zip_tree(tx, ty):
if x != y:
return False
return True
我们的tree类自动从这些更新的延迟inorder，preorder和postorder遍历中受益.不要忘记添加zip_tree和equal-
Our tree class automatically benefits from these updated lazy inorder, preorder, and postorder traversals. Don't forget to add zip_tree and equal -
class tree:
# def __init__ ...
# def __str__ ...
# def delete ...
# def fold ...
# def sum ...
# def max ...
# def inorder ...
# def preorder ...
# def postorder ...
def zip(self, other):
return zip_tree(self.root, other.root) # <-- zip_tree
def equal(self, other):
return equal(self.root, other.root) # <-- equal
print(tree(t).equal(tree(t)))
# True
print(tree(t).equal(tree(t).delete(3)))
# False
print(list(tree(t).zip(tree(t))))
# [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7)]
print([ x * y for (x, y) in tree(t).zip(tree(t)) ])
# [1, 4, 9, 16, 25, 36, 49]
pythonic
这只是Python所说的做事的一种方式. zip_tree和equal向我们展示了如何编写程序来支持tree.编写pythonic程序意味着我们尽可能使用Python约定-
This is just a way of saying do things the Python way. zip_tree and equal show us how we can write programs to support our tree. Writing pythonic programs means we use Python conventions where possible -
class node:
# def __init__ ...
def __iter__(self): # <-- __iter__ defines iterator
return inorder(self)
class tree:
# def __init__ ...
# def __str__ ...
# def delete ...
# def fold ...
# def sum ...
# def max ...
# def inorder ...
# def preorder ...
# def postorder ...
def __iter__(self): # <--
return iter(self.root or [])
def equal(self, other):
def __eq__(self, other): # <-- __eq__ defines tree equality
return equal(self.root, other.root)
def zip(self, other):
return zip_tree(self.root, other.root)
return zip(self, other) # <-- python zip works on all iterables
我们不再需要zip_tree-
def zip_tree (tx = None, ty = None, traverse = inorder):
return zip(traverse(tx), traverse(ty))
def equal (tx = None, ty = None):
for (x, y) in zip_tree(tx, ty):
for (x, y) in zip(tx, ty): # <-- use python zip directly on trees
if x != y:
return False
return True
tree.py
这是我们在本文中制作的模块的副本-
Here's a copy of the module we made in this post -
# tree.py
from math import inf
def identity (x = None):
return x
def call (f = identity):
return lambda *a: f(a)
def delete (root = None, q = None):
if not root or root.data == q:
return None
else:
return node(root.data, delete(root.left, q), delete(root.right, q))
def fold (root = None, f = call(tuple), init = None):
if not root:
return init
else:
return f \
( root.data
, fold(root.left, f, init)
, fold(root.right, f, init)
)
def to_str (root = None):
return fold \
( root
, lambda data, left, right: f"(node {data} {left} {right})"
, "_"
)
def maximum (root = None):
return fold \
( root
, lambda data, left, right: max(data, left, right)
, -inf
)
def sum (root = None):
return fold \
( root
, lambda data, left, right: data + left + right
, 0
)
def inorder (root = None):
def lazy (data, left, right):
yield data
yield from left
yield from right
return fold(root, lazy, [])
def preorder (root = None):
def lazy (data, left, right):
yield from left
yield data
yield from right
return fold(root, lazy, [])
def postorder (root = None):
def lazy (data, left, right):
yield from left
yield from right
yield data
return fold(root, lazy, [])
def equal (tx = None, ty = None):
for (x, y) in zip(tx, ty):
if x != y:
return False
return True
class node:
def __init__ (self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def __iter__ (self):
return inorder(self)
class tree:
def __init__ (self, root = None):
self.root = root
def __str__ (self):
return to_str(self.root)
def delete (self, v = None):
return tree(delete(self.root, v))
def fold (self, f = call(tuple), init = None):
return fold(self.root, f, init)
def sum (self):
return sum(self.root)
def max (self):
return maximum(self.root)
def inorder (self):
return inorder(self.root)
def preorder (self):
return preorder(self.root)
def postorder (self):
return postorder(self.root)
def __iter__ (self):
return iter(self.root or [])
def __eq__ (self, other):
return equal(self.root, other.root)
def zip (self, other):
return zip(self, other)
这篇关于使用递归从二进制搜索树中删除节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
