二叉排序树实现(Python)

基本概念

定义： 二叉排序树或者是空树，或者满足以下性质

1. 若它的左子树不空，则左子树上所有节点的值均小于根节点的值
2. 若它的右子树不空，则右子树上所有节点的值均大于根节点的值
3. 左右子树又各是一颗二叉排序树

注： 二叉排序树的中序遍历为递增有序序列

数据结构：

classNode():
    def__init__(self,value):
        self.value= value
        self.left= None
        self.right= None

二叉排序树查找

defBST_serach(root, value):if not root: # 遇到空节点，未找到return Falseif root.value== value: # 找到return True
    elif value< root.value: # 若值小于根节点值，继续从左子树中查找returnBST_serach(root.left, value)else: # 否则，该值大于根节点的值，从右子树中查找returnBST_serach(root.right, value)

二叉排序树插入

对于一个不存在于二叉排序树中的值，其查找不成功的位置即为该值的插入位置
因此，只需要在找到空指针的时候，进行插入

defBST_insert(root, value):if not root: # 遇到空节点，即为插入位置
        root=Node(value)returnif root.value== value: # 若该值已存在于二叉树中，插入失败print("Existed!!!")return
    elif value< root.value: # 若值小于根节点值，继续从左子树中查找插入位置if not root.left: # 该判断不可删除，会出现无法插入的问题，原因尚未知
            root.left=Node(value)returnBST_insert(root.left, value)
        # 注：以上四句不可用return self.BST_insert(root.right, value)代替，
        # 会出现节点无法插入的问题else: # 否则，该值大于根节点的值，从右子树中查找插入位置if not root.right:
            root.right=Node(value)returnBST_insert(root.right, value)

完整类实现

classBSTree():
    def__init__(self, root):
        self.root= root
    
    defserach(self, value):return self.BST_serach(self.root, value)
    
    definsert(self, value):
        self.BST_insert(self.root, value)
    
    defprint_tree(self):
        self.BST_print(self.root)
    
    defBST_insert(self, root, value):if not root: # 遇到空节点，即为插入位置print("Insert!!!")
            root=Node(value)returnif root.value== value: # 若该值已存在于二叉树中，插入失败print("Existed!!!")return
        elif value< root.value: # 若值小于根节点值，继续从左子树中查找插入位置if not root.left:print("Insert!!!")
                root.left=Node(value)return
            self.BST_insert(root.left, value)else: # 否则，该值大于根节点的值，从右子树中查找插入位置if not root.right:print("Insert!!!")
                root.right=Node(value)return
            self.BST_insert(root.right, value)
            # 注：以上四句不可用return self.BST_insert(root.right, value)代替
            # 会出现节点无法插入的问题
    
    defBST_serach(self, root, value):if not root: # 遇到空节点，未找到return Falseif root.value== value: # 找到return True
        elif value< root.value: # 若值小于根节点值，继续从左子树中查找return self.BST_serach(root.left, value)else: # 否则，该值大于根节点的值，从右子树中查找return self.BST_serach(root.right, value)
    
    defBST_print(self, root):"""Middle Serach"""if not root:return
        
        self.BST_print(root.left)print(root.value)
        self.BST_print(root.right)

删除操作较复杂，暂未编写