今天写二叉排序树
class BTNode: def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right class BST: def __init__(self): self.root = None # 头指针 def insert(self, data): if self.root is None: self.root = BTNode(data) return True pre = None node = self.root dire = None while node is not None: pre = node if data < node.data: dire = "left" node = node.left elif data > node.data: dire = "right" node = node.right else: return False if dire == "left": pre.left = BTNode(data) else: pre.right = BTNode(data) return True @staticmethod def __height(node): if node is None: return 0 lh = BST.__height(node.left) rh = BST.__height(node.right) return lh + 1 if lh > rh else rh + 1 def height(self): return self.__height(self.root) def remove(self, data): # 上提左子树(左子树存在、左子树不存在) if self.root is None: return False if self.root.data == data: left = self.root.left right = self.root.right if left is not None: self.root = left if right is not None: while left.right is not None: left = left.right left.right = right else: self.root = right return True pre = None node = self.root dire = None while node is not None: if data < node.data: pre = node dire = "left" node = node.left elif data > node.data: pre = node dire = "right" node = node.right else: if node.left is not None: if dire == "left": pre.left = node.left else: pre.right = node.left if node.right is not None: left = node.left while left.right is not None: left = left.right left.right = node.right else: if dire == "left": pre.left = node.right else: pre.right = node.right return True return False @staticmethod def __vlr(node, function): if node is None: return function(node.data) if node.left is not None: BST.__vlr(node.left, function) if node.right is not None: BST.__vlr(node.right, function) def vlr(self, function): self.__vlr(self.root, function) @staticmethod def __lvr(node, function): if node is None: return if node.left is not None: BST.__lvr(node.left, function) function(node.data) if node.right is not None: BST.__lvr(node.right, function) def lvr(self, function): self.__lvr(self.root, function) @staticmethod def __lrv(node, function): if node is None: return if node.left is not None: BST.__lrv(node.left, function) if node.right is not None: BST.__lrv(node.right, function) function(node.data) def lrv(self, function): self.__lrv(self.root, function) if __name__ == "__main__": def function(data): print(data, end=" ") bst = BST() bst.insert(9) bst.insert(3) bst.insert(5) bst.insert(13) bst.insert(2) bst.insert(7) bst.insert(4) print(bst.height()) bst.vlr(function) print() bst.lvr(function) print() bst.lrv(function) print() print(bst.remove(5)) bst.vlr(function) print() bst.lvr(function) print() print(bst.remove(9)) bst.vlr(function) print() bst.lvr(function)下面是测试结果：
