备战蓝桥杯Day25 - 二叉搜索树查询和删除操作

一、查询

递归查询

寻找的值比根节点大，遍历右子树；

寻找的值比根节点小，遍历左子树。

    def qurey(self, node, val):
        if not node:  # 没有节点，返回空
            return None
        if node.data < val:
            return self.qurey(node.rchild, val)
        elif node.data > val:
            return self.qurey(node.lchild, val)
        else:
            return node

非递归查询 

通过比较，指针不断向下移动，直到找到节点。

 def query_no_rec(self, val):
        p = self.root
        while p:
            if p.data < val:
                p = p.rchild
            elif p.data > val:
                p = p.lchild
            else:
                return p
        return None

二、删除 

删除操作比较难，需要考虑三种情况

1、删除叶子节点：直接删除

2、如果删除的节点只有一个孩子：将此节点的孩子与父亲链接，然后删除此节点。（如果删除的根节点只有一个孩子，删除根节点后，要重新更新一下根节点）

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

代码实现

 def __remove_node_1(self, node):
        # 情况1：node是叶子节点
        if not node.parent:
            self.root = None
        if node == node.parent.lchild:
            node.parent.lchild = None
        else:
            node.parent.rchild = None

    def __remove_node_21(self, node):
        # 情况2.1：node只有一个左孩子
        if not node.parent:
            self.root = node.lchild
            node.parent.lchild = None
        elif node == node.parent.lchild:
            node.parent.lchild = node.lchild
            node.lchild.parent = node.parent
        else:
            node.parent.rchild = node.lchild
            node.lchild.parent = node.parent

    def __remove_node_22(self, node):
        # 情况2.2：node只有一个右孩子
        if not node.parent:
            self.root = node.rchild
        elif node == node.parent.lchild:
            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:
                return False
            if not node.lchild and not node.rchild:  # 1. 叶子节点
                self.__remove_node_1(node)
            elif not node.rchild:   # 2.1只有一个左孩子
                self.__remove_node_21(node)
            elif not node.lchild:   # 2.3 只有一个右孩子
                self.__remove_node_22(node)
            else:  # 3.两个孩子都有
                min_node = node.rchild
                while min_node.lchild:
                    min_node = min_node.lchild
                node.data = min_node.data
                # 删除min_node节点
                if min_node.rchild:
                    self.__remove_node_22(node)
                else:
                    self.__remove_node_1(node)

先呈现全部代码，具体实现过程的详细解释我明天再补充。