ActiveMQ 宽禁带半导体 云计算架构 dll deployment emacs swagger Zeptojs easyui视频 jq去空格 idea导入多个项目 pcie转sata python数据库 input函数python python使用正则表达式 python中集合 linux硬盘 javascript实例 xp系统修复 内存整理工具 r语言和python 彻底删除mysql 一件换肤 eclipse中文版下载 福昕阅读器绿色版 掌门一对一下载 x64dbg medcalc deallocate qq流览器下载 迅雷单机游戏下载 g4560配什么显卡 su模型交错 jquery添加样式 快剪辑去水印 ps怎么把人p瘦 total同级生2下载 优酷网打不开 橙子助手 微信筛子
当前位置: 首页 > 学习教程  > python

二叉搜索树(二叉排序树)

2021/2/6 22:30:40 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

二叉排序树 class BiTreeNode:def __init__(self, data):self.data dataself.lchild None # 左孩子self.rchild None # 右孩子self.parent Noneclass BST:def __init__(self, liNone):self.root Noneif li:for val in li:self.insert_no_rec(val)def insert(self, node…

二叉排序树

class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None  # 左孩子
        self.rchild = None  # 右孩子
        self.parent = None


class 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):
        """
        非递归
        :param val:
        :return:
        """
        p = self.root
        if not p:  # 空树
            self.root = BiTreeNode(val)
            return
        while True:
            if val < p.data:
                if p.lchild:
                    p = p.lchild
                else:  # 左孩子不存在
                    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):
        """
        查询
        :param node:
        :param val:
        :return:
        """
        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):
        """
        非递归查询
        :param val:
        :return:
        """
        p = self.root
        while p:
            if p.data < val:
                p = p.rchild
            elif p.data > val:
                p = p.lchild
            else:
                return p
        return None

    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=',')

    def __remove_node_1(self, node):
        # 情况1:node是叶子节点
        if not node.parent:
            self.root = None
        if node == node.parent.lchild:  # node是它父亲的左孩子
            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.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

    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.2 只有一个右孩子
                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(min_node)
                else:
                    self.__remove_node_1(min_node)


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、删除
	1.1 删除的节点为叶子节点,则直接删除即可。

在这里插入图片描述

    def __remove_node_1(self, node):
        # 情况1:node是叶子节点
        if not node.parent:
            self.root = None
        if node == node.parent.lchild:  # node是它父亲的左孩子
            node.parent.lchild = None
        else:  # 右孩子
            node.parent.rchild = None
1、删除
	1.2 删除的节点只有左子树或者只有右子树,被删除的节点是只有左子树

在这里插入图片描述

    def __remove_node_21(self, node):
        # 情况2.1: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
1、删除
	1.3 删除的节点只有左子树或者只有右子树,被删除的节点是只有右子树

在这里插入图片描述

    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
1、删除
	1.4 删除的节点既有左子树也有右子树

在这里插入图片描述

    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.2 只有一个右孩子
                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(min_node)
                else:
                    self.__remove_node_1(min_node)

本文链接: http://www.dtmao.cc/news_show_2000141.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?