使用递归从二进制搜索树中删除节点

本文介绍了使用递归从二进制搜索树中删除节点的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

所以我试图通过使用类中的这两个函数从树中删除一个节点.不幸的是，它只是不删除任何东西，我想知道这是怎么回事！任何帮助将不胜感激.

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.

让我们删除print效果，并使用这些更所谓的 Pythonic 程序-

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)