数据结构学习-python实现-二叉搜索树--0415---到不了的都叫做远方

二叉查找树的生成，以及增删查，删除最为复杂，考虑的情况特别多，左右子树，容易把人弄乱。最重要的是删除后，需要将其右子树的最小值补充过来，有一番替换的过程。

class BinarySearchTree: def __init__(self): self.root = None self.size = 0 def length(self): return self.size def __len__(self): return self.size def __iter__(self): return self.root.__iter__() def put(self, key, val): # 插入操作 if self.root: # 若已存在根节点，直接插入数据 self._put(key, val, self.root) else: # 不存在根节点，则插入根节点的值 self.root = TreeNode(key, val) self.size += 1 def _put(self, key, val, currentnode): if key < currentnode.key: # 若插入值与根节点的值的大小，将插入值链接到左或右子节点 if currentnode.hasleftchild(): self._put(key, val, currentnode.leftchild) else: currentnode.leftchild = TreeNode(key, val, parent=currentnode) else: if currentnode.hasrightchild(): self._put(key, val, currentnode.rightchild) else: currentnode.rightchild = TreeNode(key, val, parent=currentnode) def __setitem__(self, key, value): self.put(key, value) def get(self, key): # 查找方法 if self.root: res = self._get(key, self.root) if res: return res.payload else: return None else: return None def _get(self, key, currentnode): # 查找节点 if not currentnode: return None elif currentnode.key == key: return currentnode elif key < currentnode.key: return self._get(key, currentnode.leftchild) # 递归的查找 else: return self._get(key, currentnode.rightchild) def __getitem__(self, key): return self.get(key) def __contains__(self, key): if self._get(key, self.root): return True else: return False def delete(self, key): # 删除节点 if self.size > 1: nodetoremove = self._get(key, self.root) # 先查找要删除的节点 print(nodetoremove.payload) if nodetoremove: self.remove(nodetoremove.key,nodetoremove) # 找到了就调用remove方法 self.size -= 1 else: raise KeyError('Error, key not in tree') elif self.size == 1 and self.root.key == key: self.root = None self.size -= 1 else: raise KeyError('Error, key not in tree') def remove(self, key, currentnode): if currentnode.isleaf(): # 删除节点为叶节点，则将父节点的相应子节点设置为None if currentnode == currentnode.parent.leftchild: currentnode.parent.leftchild = None else: currentnode.parent.rightchild = None elif currentnode.hasbothchildren(): # 若有两个子节点，则寻找右子节点的最小节点，替换该位置 succ = currentnode.findsuccessor() succ.spliceout() currentnode.key = succ.key currentnode.payload = succ.payload else: if currentnode.hasleftchild(): if currentnode.isleftchild(): currentnode.leftchild.parent = currentnode.parent currentnode.parent.leftchild = currentnode.leftchild elif currentnode.isrightchild(): currentnode.leftchild.parent = currentnode.parent currentnode.parent.rightchild = currentnode.leftchild else: currentnode.replacenodedata(currentnode.leftchild.key,currentnode.leftchild.payload,currentnode.leftchild.leftchild,currentnode.leftchild.rightchild) else: if currentnode.isleftchild(): currentnode.rightchild.parent = currentnode.parent currentnode.parent.leftchild = currentnode.rightchild elif currentnode.isrightchild(): currentnode.rightchild.parent = currentnode.parent currentnode.parent.rightchild = currentnode.rightchild else: currentnode.replacenodedata(currentnode.rightchild.key,currentnode.rightchild.payload,currentnode.rightchild.leftchild,currentnode.rightchild.rightchild) def __delitem__(self, key): self.delete(key) class TreeNode: def __init__(self, key, val, left=None, right=None, parent=None): self.key = key self.payload = val self.leftchild = left self.rightchild = right self.parent = parent def hasleftchild(self): return self.leftchild def hasrightchild(self): return self.rightchild def isleftchild(self): return self.parent and self.parent.leftchild == self def isrightchild(self): return self.parent and self.parent.rightchild == self def isroot(self): return not self.parent def isleaf(self): return not (self.rightchild or self.leftchild) def hasanychildren(self): return self.rightchild or self.leftchild def hasbothchildren(self): return self.rightchild and self.leftchild def replace_node_data(self, key, value, lc, rc): self.key = key self.payload = value self.leftchild = lc self.rightchild = rc if self.hasleftchild(): self.leftchild.parent = self if self.hasrightchild(): self.rightchild.parent = self def findsuccessor(self): succ = None if self.hasrightchild(): succ = self.rightchild.findmin() return succ def findmin(self): current = self while current.hasleftchild(): current = current.leftchild return current def spliceout(self): if self.isleaf(): if self.isleftchild(): self.parent.leftchild = None else: self.parent.rightchild = None elif self.hasanychildren(): if self.isleftchild(): self.parent.leftchild = self.leftchild # 它应该没有左子树了，因为是最小值 else: self.parent.rightchild = self.leftchild # 应该不会出现 self.leftchild.parent = self.parent # 大体不会出现 else: if self.isleftchild(): self.parent.leftchild = self.rightchild # 将被移走的节点的子树接到起父节点的相应子树上 else: self.parent.rightchild = self.rightchild self.rightchild.parent = self.parent # def __iter__(self): # 这个迭代代码始终报错，但是没有迭代的话，就不能for循环内部节点。还没解决这个问题 # if self: # if self.hasleftchild(): # for elem in self.leftchild: # yield elem # yield self.key # if self.hasrightchild(): # for elem in self.rightchild: # yield elem if __name__ == "__main__": alist = [70, 31, 93, 94, 14, 23, 73] bst = BinarySearchTree() bst.put(alist[0], 'luffy') bst.put(alist[1], 'ace') bst.put(alist[2], 'sanji') bst.put(alist[3], 'joba') bst.put(alist[4], 'flank') bst.put(alist[5], 'solo') bst.put(alist[6], 'namei') print(len(bst)) # bst.delete(alist[6]) bst.delete(alist[0]) # print(bst.root.leftchild.leftchild.rightchild.key) print(bst.root.key) ---来自腾讯云社区的---到不了的都叫做远方