本文共 5334 字，大约阅读时间需要 17 分钟。

二叉搜索树

1. 概念

二叉搜索树是一颗二叉树且满足性质:

2. 操作

二叉搜索树的操作:查询、插入、删除，

1. 如果要删除的节点是叶结点: 直接删除

   

2. 要删除的节点只有一个孩子: 将此节点的父亲与孩子连接，然后删除该节点。

   

3. 如果要删除的节点有两个孩子:将其右子树的最小节点(该节点最多有一个右孩子)删除，并替换当前节点。

   

3. 代码:

'''TOPIC: 二叉搜索树: 插入author: Bluetime: 2020-08-16QQ: 2458682080'''class BiTreeNode:    def __init__(self, data):        self.data = data        self.lchild = None        self.rchild = None        self.parent = Noneclass BST:    def __init__(self, li=None):        self.root = None        if li:            for val in li:                self.insert_no_rec(val)    # 利用递归插入    def insert(self, node, val):        if not node:            node = BiTreeNode(val)        elif val < node.data:            node.lchild = self.insert(node.lchild, val)            node.lchild.parent = node        elif val > node.data:            node.rchild = self.insert(node.rchild, val)            node.rchild.parent = node        return node    # 利用非递归插入    def insert_no_rec(self, val):        p = self.root   # p代表当前点        if not p:  # 空树            self.root = BiTreeNode(val)            return        while True:            if val < p.data:                if p.lchild:  # 如果p存在左孩子                    p = p.lchild                else:        # 如果p不存在左孩子                    p.lchild = BiTreeNode(val)                    p.lchild.parent = p                    return            elif val > p.data:                if p.rchild:                    p = p.rchild                else:                    p.rchild = BiTreeNode(val)                    p.rchild.parent = p                    return            else:                return    # 用递归查询    def query(self, node, val):        if not node:            return None        if node.data < val:  # 当前点的值
   <要查找的值，就往当前点的右子树找 return self.query(node.rchild, val) elif node.data>
     val:  # 当前点的值>要查找的值，就往当前点的左子树找            return self.query(node.lchild, val)        else:            return node    # 不用递归查询    def query_no_rec(self, val):        p = self.root   # p代表当前点        while p:            if p.data < val:                p = p.rchild            elif p.data > val:                p = p.lchild            else:                return p        return None    # 情况1: node是叶子节点    def __remove_node_1(self, node):        if not node.parent:  # 如果这个节点是根            self.root = None        if node == node.parent.lchild:  # 如果node是它父亲的左孩子            node.parent.lchild = None        else:            node.parent.rchild = None    # 情况2.1: node只有一个左孩子    def __remove_node_21(self, node):        if not node.parent:   # 根结点            self.root = node.lchild            node.lchild.parent = None        elif node == node.parent.lchild:   # node是它父亲的左孩子            node.parent.lchild = node.lchild # node删掉，node的左孩子给node的父亲作为左孩子            node.lchild.parent = node.parent        else:            node.parent.rchild = node.lchild            node.lchild.parent = node.parent    # 情况2.2: node只有一个右孩子    def __remove_node_22(self, node):        if not node.parent:            self.root = node.rchild        elif node == node.parent.lchild:  # node是它父亲的左孩子            node.parent.lchild = node.rchild            node.rchild.parent = node.parent        else:            node.parent.rchild = node.rchild            node.rchild.parent = node.parent    # 删除    def delete(self, val):        if self.root:  # 不是空树            node = self.query_no_rec(val)            if not node:  # node不存在                return False            # 情况1: node是叶结点            if not node.lchild and not node.rchild:                self.__remove_node_1(node)            # 情况2.1: 只有左孩子            elif not node.rchild:                self.__remove_node_21(node)            # 情况2.2: 只有右孩子            elif not node.lchild:                self.__remove_node_22(node)            # 情况3: 两个孩子都有            else:                min_node = node.rchild                # 找到右子树的最小节点                while min_node.lchild:                    min_node = min_node.lchild                node.data = min_node.data                # 删除min_node,这里min)node只有两种情况，要么是叶结点，要么就是只有右孩子                if min_node.rchild:                    self.__remove_node_22(min_node)                else:                    self.__remove_node_1(min_node)    # 前序遍历(先递归左子树，再递归右子树)    def pre_order(self, root):        if root:            print(root.data, end=",")            self.pre_order(root.lchild)            self.pre_order(root.rchild)    # 中序遍历(先递归左子树，再访问自己，再递归右子树)    def in_order(self, root):        if root:            self.in_order(root.lchild)            print(root.data, end=",")            self.in_order(root.rchild)    # 后续遍历(先递归左，后递归有，最后打印自己)    def post_order(self, root):        if root:            self.post_order(root.lchild)            self.post_order(root.rchild)            print(root.data, end=",")import random# li = list(range(500))# random.shuffle(li)# tree = BST(li)# tree.pre_order(tree.root)# print("")# tree.in_order(tree.root)   # 将列表从小到大输出# print("")# tree.post_order(tree.root)# print("")# li2 = list(range(0, 500, 2))# random.shuffle(li2)# tree = BST(li2)# print(tree.query_no_rec(3))tree = BST([1, 4, 2, 5, 3, 8, 6, 9, 7])tree.in_order(tree.root)print("")tree.delete(4)tree.delete(1)tree.delete(8)tree.in_order(tree.root)
   

结果为:

1,2,3,4,5,6,7,8,9,2,3,5,6,7,9,

4. 效率

二叉搜索树的效率:

转载地址：http://vbiwi.baihongyu.com/