备战蓝桥杯Day25 - 二叉搜索树

一、基本概念

二叉搜索树(Binary Search Tree),又称为二叉查找树或二叉排序树,是一种具有特定性质的二叉树。

  1. 定义:二叉搜索树可以是一棵空树,也可以是具有以下特性的非空二叉树:

    • 若其左子树不空,则左子树上所有结点的值均小于其根结点的值。
    • 若其右子树不空,则右子树上所有结点的值均大于其根结点的值。
    • 它的左、右子树也分别为二叉排序树。
  2. 结构:二叉搜索树是以二叉树的形式组织的,通常可以使用链表数据结构来表示。每个结点除了包含关键字(key)和可能的其他数据外,还包含指向其左孩子(lchild)和右孩子(rchild)的指针,以及指向其父结点(parent)的指针(如果需要的话)。如果某个孩子结点或父结点不存在,则相应属性的值为空(NIL)。

  3. 元素特性:二叉搜索树中存储的元素必须具备可比较性,例如整数(int)或浮点数(double)等。如果是自定义类型,需要指定比较方式。

  4. 应用:二叉搜索树作为一种经典的数据结构,具有链表快速插入与删除操作的特点和数组快速查找的优势。因此,它在许多场合下都有广泛的应用,如在文件系统和数据库系统中用于高效的排序与检索操作。

二叉搜索树是一种非常有效的数据结构,它能够保持数据的有序性,同时提供快速的查找、插入和删除操作。

二、插入操作实现

代码实现

# 定义树的节点
class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None
        self.parent = None


class BST:
    def __init__(self):  # 初始化二叉搜索树
        self.root = None

    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
        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
            elif val > p.data:
                if p.rchild:  # 右孩子存在
                    p = p.rchild
                else:  # 右孩子不存在时直接创建节点插入
                    p.rchild = BiTreeNode(val)
                    p.rchild.parent = p
                    return
            else:
                return


非递归插入详细过程 

使用非递归函数插入数据详细过程

1、随便定义一颗二叉搜索树(非空),将val = 12 插入到树中 。通过循环比较来实现数值的插入。

先将定义的 p 指针指向根节点,然后开始 val 与 根节点数值的比较。

2、 根据图中数值可知, val = 12 < p.data = 17,且 p点的左孩子 (p.lchild)存在,那么 p 指针向下移动,只执行 if val < p.data: 这块代码,变为如下图所示。

 while True:
            if val < p.data:
                if p.lchild:
                    p = p.lchild
                else:
                    p.lchild = BiTreeNode(val)
                    p.lchild.parent = p

 

 3.此时, val = 12 < p.data = 13,且 p点的左孩子 (p.lchild)存在,执行 p = p.lchild 语句,那么 p 指针向下移动,变为如下图所示。

4.此时, val = 12 > p.data = 7, 那么他要往右子树进行插入,且p.data 的右孩子不存在,就直接创建新的节点进行插入即可。

 elif val > p.data:
                if p.rchild:  # 右孩子存在
                    p = p.rchild
                else:  # 右孩子不存在时直接创建节点插入
                    p.rchild = BiTreeNode(val)
                    p.rchild.parent = p
                    return

最后插入结果为:

测试结果

对定义的函数进行测试,分别以先序,中序,后序输出。中序遍历都是从小到大输出,可以用作一种排序。

import random
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):
        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
            elif val > p.data:
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild = BiTreeNode(val)
                    p.rchild.parent = p
                    return
            else:
                return

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


li = list(range(0, 10))
random.shuffle(li)

tree = BST(li)
tree.pre_order(tree.root)  # 先序
print(" ")
tree.in_order(tree.root)   # 中序
print(" ")
tree.post_order(tree.root) # 后序

 输出结果

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/445849.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

MAC OS 14.2.1 ASP.NET Core 调试遇到的端口占用的问题

一、问题描述 在调试 ASP.NET Core 项目时&#xff0c;遇到一个很奇怪的问题&#xff0c;不管项目是否已经运行&#xff0c;使用 Postman 测试接口时&#xff0c;都返回 403 Forbidden。重启电脑&#xff0c;刚开始还好好的&#xff0c;过一会儿就返回 403 Forbidden。 二、问…

AOP切面编程,以及自定义注解实现切面

AOP切面编程 通知类型表达式重用表达式切面优先级使用注解开发&#xff0c;加上注解实现某些功能 简介 动态代理分为JDK动态代理和cglib动态代理当目标类有接口的情况使用JDK动态代理和cglib动态代理&#xff0c;没有接口时只能使用cglib动态代理JDK动态代理动态生成的代理类…

2024蓝桥杯每日一题(双指针)

一、第一题&#xff1a;牛的学术圈 解题思路&#xff1a;双指针贪心 仔细思考可以知道&#xff0c;写一篇综述最多在原来的H指数的基础上1&#xff0c;所以基本方法可以是先求出原始的H指数&#xff0c;然后分类讨论怎么样提升H指数。 【Python程序代码】 n,l map(int,…

一篇文章搞定数字电桥

大家好&#xff0c;我是砖一。 最近做项目过程中&#xff0c;有一个应届生问我怎么测电容和电感&#xff0c;我推荐他使用数字电桥&#xff08;也叫LCR表&#xff09;&#xff0c;他不会用&#xff0c;今天我写了一篇文章供小白们参考一下&#xff0c;包学会~ 一&#xff0c;…

WebRTC简介及实战应用 — 从0到1实现实时音视频聊天等功能

一、WebRTC简介 WebRTC 是由一家名为 Gobal IP Solutions,简称 GIPS 的瑞典公司开发的。Google 在 2011 年收购了 GIPS,并将其源代码开源。然后又与 IETF 和 W3C 的相关标准机构合作,以确保行业达成共识。其中: Web Real-Time Communications (WEBRTC) W3C 组织:定义浏览…

【npm】node包管理工具npm的介绍和基础使用

简言 npm 是 Node.js 的 包管理器&#xff08;Package Manager&#xff09;&#xff0c;它是专门用于管理 Node.js 项目中第三方库的工具。 本文介绍下npm和其使用方法。 npm介绍 npm 是世界上最大的软件注册中心。各大洲的开源开发者都使用 npm 共享和借用软件包&#xff…

开源组件安全风险及应对

在软件开发的过程中&#xff0c;为了提升开发效率、软件质量和稳定性&#xff0c;并降低开发成本&#xff0c;使用开源组件是开发人员的不二选择&#xff08;实际上&#xff0c;所有软件开发技术的演进都是为了能够更短时间、更低成本地构建软件&#xff09;。这里的开源组件指…

Spring事件发布监听器ApplicationListener原理- 观察者模式

据说监听器模式也是mq实现的原理, 不过mq我还没来得及深入学习, 先用spring来理解一下吧 Spring事件发布监听器ApplicationListener原理- 观察者模式 什么是观察者模式一个Demo深入认识一下观察者模式Spring中的事件发布监听ps 什么是观察者模式 大家都听过一个故事叫做烽火戏…

Git学习笔记(流程图+示例)

概念 图中左侧为工作区&#xff0c;右侧为版本库。Git 的版本库里存了很多东西&#xff0c;其中最重要的就是暂存区。 • 在创建 Git 版本库时&#xff0c;Git 会为我们自动创建一个唯一的 master 分支&#xff0c;以及指向 master 的一个指 针叫 HEAD。&#xff08;分支和HEAD…

设计模式-结构型模式-代理模式

代理模式&#xff08;Proxy&#xff09;&#xff0c;为其他对象提供一种代理以控制对这个对象的访问。[DP] // 定义接口 interface Subject {void request(); }// 真实主题对象 class RealSubject implements Subject {Overridepublic void request() {System.out.println(&quo…

redis使用笔记

redis使用笔记 1、Redis简介1.1 含义1.2 功能1.3 特点 2. 常用的数据结构2.1 HASH 3 redis接口定义3.1 redisReply3.2 redisContext3.3 redisCommand 4 实践操作4.1 遇到问题4.1.1 Get哈希的时候返回error4.1.2 长度一直为0&#xff0c;str没法打印&#xff08;未解决&#xff…

享受当下,2024,一顺百顺!

永远都不要提前焦虑&#xff0c; 也不要一直烦恼&#xff0c; 更不要被当前的情绪耗尽&#xff0c; 那样会对自己的身体造成严重的伤害&#xff0c; 自己只需要好好享受当下就行了。 车到山前必有路&#xff0c;关关难过关关过&#xff01; 不要执着于过去&#xff0c;也不要过…

10-ARM gicv3/gicv4的总结-基础篇

目录 1、gic的版本2、GICv3/gicv4的模型图3、gic中断号的划分4、GIC连接方式5、gic的状态6、gic框架7、gic Configuring推荐 本文转自 周贺贺&#xff0c;baron&#xff0c;代码改变世界ctw&#xff0c;Arm精选&#xff0c; armv8/armv9&#xff0c;trustzone/tee&#xff0c;s…

LeetCode59:螺旋矩阵Ⅱ

题目描述 给你一个正整数 n &#xff0c;生成一个包含 1 到 n2 所有元素&#xff0c;且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;[[1,2,3],[8,9,4],[7,6,5]] 代码 class Solution { public:vector…

AWS 入门实践-远程访问AWS EC2 Linux虚拟机

远程访问AWS EC2 Linux虚拟机是AWS云计算服务中的一个基本且重要的技能。本指南旨在为初学者提供一系列步骤&#xff0c;以便成功地设置并远程访问他们的EC2 Linux实例。包括如何上传下载文件、如何ssh远程登录EC2虚拟机。 一、创建一个AWS EC2 Linux 虚拟机 创建一个Amazon…

GSEA -- 学习记录

文章目录 brief统计学原理部分其他注意事项转录组部分单细胞部分 brief 上一篇学习记录写了ORA&#xff0c;其中ORA方法只关心差异表达基因而不关心其上调、下调的方向&#xff0c;也许同一条通路里既有显著高表达的基因&#xff0c;也有显著低表达的基因&#xff0c;因此最后…

iMazing3 2024详细解析数据备份与恢复备份

iMazing 3的备份功能支持增量备份&#xff08;类似苹果电脑里的Time Machine功能&#xff09;&#xff0c;意思是第一次把移动设备的数据全部备份下来&#xff0c;之后的备份就只针对数据有变化的那部分&#xff0c;这样可以节省大量的时间和存储空间&#xff0c;不会让使用者为…

LeetCode刷题日志-17.电话号码的字母组合

纯暴力解法&#xff0c;digits有多长&#xff0c;就循环多少次进行字母组合 class Solution {public List<String> letterCombinations(String digits) {List<String> reslut new ArrayList<>();if(digits.equals(""))return reslut;Map<Inte…

ubuntu 23.04 安装 中文输入法

1、安装 fcitx sudo apt install fcitxfcitx 安装好后&#xff0c;可以使用 fcitx-configtool 命令进行配置&#xff0c;其界面如下所示。在这里可以配置不同输入法的切换快捷键&#xff0c;默认输入法等。刚安装系统后&#xff0c;这里只有一个输入法&#xff0c;所以接下来要…

Mysql深入学习 基础篇 Ss.02 详解四类SQL语句

我亲爱的对手&#xff0c;亦敌亦友&#xff0c;但我同样希望你能成功&#xff0c;与我一起&#xff0c;站在人生的山顶上 ——24.3.1 一、DDL 数据定义语言 1.DDL —— 数据库操作 查询 查询所有数据库 show databases; 查询当前数据库 select database(); 创建 create databa…