删除二进制搜索树python中的节点

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

下面的代码是我的二进制搜索树的实现，并且我想实现delete方法以删除该节点.以下是我的实现，但是当我执行

The code below is my implement for my binary search tree, and I want to implement delete method to remove the node. Below is my implementation, but when I perform

bst = BSTRee() bst.insert(5) bst.insert(11) bst.insert(3) bst.insert(4) bst.insert(12) bst.insert(2) bst.delete(3)

当我调用delete方法时，它什么也没做.有人可以帮我修复它.下面的链接是我在github上的代码.非常感谢你的帮助. github/hly189/sort/blob/master/tree/BST.py

when I call delete method, it did nothing. Can someone help me to fix it. The link below is my code on github. Thank you so much for your help. github/hly189/sort/blob/master/tree/BST.py

class BSTreeNode def ____init__(self, value): self.value = value self.left = None self.right = None def insert(self,key): if self.value == key: print ("the node already exists") return False elif self.value > key: if self.left is not None: return self.left.insert(key) else: self.left = BSTreeNode(key) return True else: if self.right is not None: return self.right.insert(key) else: self.right = BSTreeNode(key) return False def delete(self, node, k): if node == None: return None elif node.value == k: if node.left is None and node.right is None: return None elif node.left is None: return node.right elif node.right is None: return node.left else: node.value = get_min(node.right) node.right.delete(node.right,node.value) elif k < node.value: node.left.delete(node.left,k) else: node.right.delete(node.right,k) return node class BSTree: def __init__(self): self.root = None def delete(self,key): self.root.delete(self.root,key) def insert(self,data): if self.root: self.root.insert(data) else: self.root = BSTreeNode(data) return True def find_min(self,node): current_node = node while current_node.left: current_node = current_node.left return current_node def get_min(node): current_node = node while current_node.left: current_node = current_node.left return str(current_node.value) def print_helper(root, indent): if root is not None: print_helper(root.right, indent + " ") print (indent + str(root.value)) print_helper(root.left, indent + " ") def print_tree(root): print_helper(root, "")

推荐答案

def delete(self, key): """ delete the node with the given key and return the root node of the tree """ if self.key == key: # found the node we need to delete if self.right and self.left: # get the successor node and its parent [psucc, succ] = self.right._findMin(self) # splice out the successor # (we need the parent to do this) if psucc.left == succ: psucc.left = succ.right else: psucc.right = succ.right # reset the left and right children of the successor succ.left = self.left succ.right = self.right return succ else: # "easier" case if self.left: return self.left # promote the left subtree else: return self.right # promote the right subtree else: if self.key > key: # key should be in the left subtree if self.left: self.left = self.left.delete(key) # else the key is not in the tree else: # key should be in the right subtree if self.right: self.right = self.right.delete(key) return self def _findMin(self, parent): """ return the minimum node in the current tree and its parent """ # we use an ugly trick: the parent node is passed in as an argument # so that eventually when the leftmost child is reached, the # call can return both the parent to the successor and the successor if self.left: return self.left._findMin(self) else: return [parent, self]

这可能会有所帮助.有关完整的代码和更好的理解，请访问 对于代码 Python中的二进制搜索树

This might help. For complete code and better understanding go to For code Binary search Tree in Python

说明 关于Python中BST的注意事项 据我所知，它工作正常.

For explanation Notes on BST in Python As per my knowledge its working fine.