二叉搜索树

1. 二叉搜索树

　　二叉搜索树又称二叉排序树，他的左子树上的节点都小于根节点，他的右子树上的节点都大于根节点，每一个左右子树又是一个二叉搜索树

2. 删除节点的几种情况：

 3. 二叉搜索树的实现：

# 构建节点类
class BiTreeNode:
    def __init__(self, item):
        self.item = item
        self.lchild = None  # 左孩子
        self.rchild = None  # 右孩子
        self.parent = None  # 父节点
# 二叉搜索树类
class BiSelectTree:
    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.item:
            node.lchild = self.insert(node.lchild, val)
        # 如果元素大于当前指针指向节点，则插入当前节点的右孩子处
        elif val > node.item:
            node.rchild = self.insert(node.rchild, val)
        return node

    # 非递归插入
    def insert_no_rec(self, val):
        # 构建指针
        pointer = self.root
        # 如果输为空，则直接插入节点
        if not pointer:
            self.root = BiTreeNode(val)
            return
        # 重复循环
        while True:
            # 当插入元素小于指针指向节点时
            if val < pointer.item:
                if pointer.lchild:      # 如果存在左孩子时，则指针指向下一层
                    pointer = pointer.lchild
                else:
                    pointer.lchild = BiTreeNode(val)    # 不存在左孩子，直接插入元素至左孩子处
                    pointer.lchild.parent = pointer     # 插入元素的父节点指向指针所在元素
                    return
            # 当插入元素大于指针指向节点时
            elif val > pointer.item:
                if pointer.rchild:      # 如果存在右孩子时，则指针指向下一层
                    pointer = pointer.rchild
                else:
                    pointer.rchild = BiTreeNode(val)    # 不存在右孩子，直接插入元素至左孩子处
                    pointer.rchild.parent = pointer     # # 插入元素的父节点指向指针所在元素
                    return
            else:
                return

    # 递归查询
    def query(self, node, val):
        # 传入的二叉树如果为空树，则直接返回None
        if not node:
            return None
        # 如果查询的元素小于当前的节点，则递归传入左孩子作为根节点继续查询
        if val < node.item:
            return self.query(node.lchild, val)
        # 如果查询的元素大于当前的节点，则递归传入右孩子作为根节点继续查询
        elif val > node.item:
            return self.query(node.rchild, val)
        # 等于时输出
        else:
            return node

    # 非递归查询
    def query_no_rec(self, val):
        pointer = self.root         # 指针指向当前根节点
        while pointer:              # 如果存在指针元素
            if val > pointer.item:          # 如果查询元素大于指针指向节点，则指针进入右孩子层
                pointer = pointer.rchild
            elif val < pointer.item:        # 如果查询元素小于指针指向节点，则指针进入左孩子层
                pointer = pointer.lchild
            else:
                return pointer        # 等于直接输出
        return None         # 不存在指针，说明到底了

    # 删除节点
    # 情况1：删除的是叶子节点，即没有子节点的节点
    def remove_node_1(self, node):
        # 如果删除节点时根节点，则变成一棵空树
        if not node.parent:
            self.root = None
        # 如果删除元素node是它父节点的左孩子
        elif node == node.parent.lchild:
            node.parent.lchild = None
        # 如果删除元素node是它父节点的右孩子
        else:
            node.parent.rchild = None

    # 情况2：删除节点只有一个左孩子
    def remove_node_2(self, node):
        # 如果删除的是根节点，那他的左孩子为根节点
        if not node.parent:
            self.root = node.lchild
            node.lchild.parent = 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

    # 情况3：删除节点只有一个右孩子
    def remove_node_3(self, node):
        # 如果删除的是根节点,则他的右孩子为根节点
        if not node.parent:
            self.root = node.rchild
            node.rchild.parent = None
        # 删除节点是它父节点的左孩子，但它只有一个右孩子
        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)   # 查询到该节点
            # 当node不存在
            if not node:
                return False
            # 当它没有左孩子和右孩子，即叶子节点，符合情况1
            if not node.lchild and not node.rchild:
                self.remove_node_1(node)
            # 如果只有一个左孩子，符合情况2
            elif not node.rchild:
                self.remove_node_2(node)
            # 如果只有一个右孩子，符合情况3
            elif not node.lchild:
                self.remove_node_3(node)
            # 如果左右孩子都存在,方法一：将有孩子集合中最小的节点提至删除节点处
            else:
                min_node = node.rchild      # 取删除节点的有孩子
                while min_node.lchild:      # 当它存在左孩子时，说明该节点不是最小节点
                    min_node = min_node.lchild  # 在进入下一层，指向它的左孩子
                node.item = min_node.item       # 如果没有左孩子，说明该节点是最小的，将删除的节点等于右最小节点
                # 删除该最小节点，两种情况：只有一个右孩子和叶子节点
                if min_node.rchild:         # 只有一个右孩子时，符合第三章情况
                    self.remove_node_3(min_node)
                else:
                    self.remove_node_1(min_node)    # 叶子节点，符合第一种情况

    # 前序遍历
    def pro_order(self, root):
        if root:
            print(root.item,end=',')
            self.pro_order(root.lchild)
            self.pro_order(root.rchild)

    # 中序遍历
    def cen_order(self, root):
        if root:
            self.cen_order(root.lchild)
            print(root.item, end=',')
            self.cen_order(root.rchild)

    # 后续遍历
    def later_order(self, root):
        if root:
            self.later_order(root.lchild)    # 先找左边的子节点
            self.later_order(root.rchild)   # 在找优点的子节点
            print(root.item, end=',')

tree = BiSelectTree([4,3,6,9,1,2,5,8])