BST二叉搜索树

概念

二叉搜索树(Binary Search Tree,简称BST),又称为二叉排序树或二叉查找树,是一种特殊的二叉树数据结构。它具有以下基本性质:

  1. 节点的值的有序性:对于BST中的任意一个节点,其左子树中所有节点的值都小于该节点的值,而其右子树中所有节点的值都大于该节点的值。
  2. 递归定义:BST可以为空树,或者是由一个根节点以及两个互不相交的子树(左子树和右子树)组成,其中左子树和右子树也分别是二叉搜索树。
  3. 搜索效率:由于其有序性,BST支持高效的查找、插入和删除操作。在平均和最好情况下,这些操作的时间复杂度为O(log n),其中n是树中节点的数量。但在最坏情况下,如果树变得不平衡(例如,每个节点都只有左子树或只有右子树,形成一个链状结构),这些操作的时间复杂度会退化到O(n)。
    在这里插入图片描述

示例

首先创建了一个表示二叉树节点的TreeNode类,它包含一个整数值、一个左子节点和一个右子节点。然后我们创建了一个BinaryTree类,它包含一个根节点。insert方法用于向二叉树中插入一个新的值,它调用了一个私有的递归方法insertRecursively来实现插入操作。在insertRecursively方法中,我们首先检查当前节点是否为空,如果为空,则创建一个新的节点并返回。然后我们比较要插入的值和当前节点的值,如果要插入的值小于当前节点的值,则将其插入到左子树中;否则将其插入到右子树中。最后返回当前节点。

public class TreeNode {//整数值Integer val;//左孩子TreeNode left;// 右孩子TreeNode right;TreeNode(int x) {val = x;}}

二叉树的添加

public class BinaryTree {TreeNode root;//添加方法public void insert(int value) {root = insertRecursively(root, value);}//添加的实现(递归)private TreeNode insertRecursively(TreeNode node, int value) {if (node == null) {return new TreeNode(value);}if (value < node.val) {node.left = insertRecursively(node.left, value);} else if (value > node.val) {node.right = insertRecursively(node.right, value);}return node;}}

使用:

public static void main(String[] args) {BinaryTree tree = new BinaryTree();tree.insert(3);tree.insert(2);tree.insert(4);tree.insert(5);System.out.println(tree);}

遍历

先序遍历(Pre-order Traversal)

遍历顺序为“根-左-右”。首先访问根节点,然后递归地遍历左子树,最后遍历右子树。先序遍历的递归算法通常用于复制一棵树或计算树的前缀表达式。

public static void preOrder(TreeNode tree) {if (tree != null) {System.out.println(tree.val);preOrder(tree.left);preOrder(tree.right);}}

中序遍历(In-order Traversal)

遍历顺序为“左-根-右”。先递归遍历左子树,然后访问根节点,最后递归遍历右子树。对于二叉搜索树来说,中序遍历会得到一个按节点值升序排列的序列,这是BST特有的性质,常用于BST的排序输出或验证BST的性质。

public static void inOrder(TreeNode tree) {if(tree != null) {inOrder(tree.left);System.out.println(tree.val);inOrder(tree.right);}}

后序遍历(Post-order Traversal)

遍历顺序为“左-右-根”。先递归遍历左子树,然后递归遍历右子树,最后访问根节点。后序遍历常用于计算表达式的后缀表示或树的释放操作。

 public static void afterOrder(TreeNode tree) {if (tree != null) {preOrder(tree.left);preOrder(tree.right);System.out.println(tree.val);}}

查找

递归版本的代码:

    private TreeNode search(TreeNode x, Integer val) {if (x == null) {return null;}int cmp = val.compareTo(x.val);if (cmp < 0) {return search(x.left, val);} else if (cmp > 0) {return search(x.right, val);} else {return x;}}

非递归,用while循环:

private TreeNode iterativeSearch(TreeNode x, Integer key) {while (x!=null) {int cmp = key.compareTo(x.val);if (cmp < 0) {x = x.left;} else if (cmp > 0) {x = x.right;} else {return x;}}return x;}public TreeNode search(Integer key) {return iterativeSearch(node, key);}public static void main(String[] args) {BinaryTree tree = new BinaryTree();tree.insert(1);tree.insert(5);tree.insert(2);tree.insert(3);TreeNode search = tree.search(3);System.out.println(search);}

最大最小值

在二叉树中寻找最大值和最小值的效率通常非常高,特别是对于二叉搜索树(BST)。这是因为BST的性质保证了左子树的所有节点值小于根节点值,而右子树的所有节点值大于根节点值。

  • 最小值:在BST中,最小值总是位于树的最左侧,即沿着左子节点一直向下走,直到没有左子节点为止的节点,就是最小值。
  • 最大值:相应地,最大值总是位于树的最右侧,即沿着右子节点一直向下走,直到没有右子节点为止的节点,就是最大值。
private TreeNode maximum(TreeNode tree) {if (tree == null) {return null;}while(tree.right != null) {tree = tree.right;}return tree;}
private TreeNode minimum(TreeNode tree) {if (tree == null) {return null;}while(tree.left != null) {tree = tree.left;}return tree;}

删除

在二叉树中删除一个节点是一个相对复杂的过程,尤其是当涉及到二叉搜索树(BST)时,因为删除操作需要维护树的性质。删除节点的几种情况:

  • 叶子节点(没有子节点):直接从父节点移除对该节点的引用即可。
  • 只有一个子节点:如果待删除节点只有左子节点,将父节点对当前节点的引用改为指向当前节点的左子节点。如果只有右子节点,类似地,将父节点对当前节点的引用改为指向当前节点的右子节点。
  • 有两个子节点:这是最复杂的情况。一种常见的做法是找到右子树中的最小节点(或左子树中的最大节点),用这个节点的值替换待删除节点的值,然后删除那个最小(或最大)节点。因为最小节点在右子树中肯定没有左子节点,所以它要么是叶子节点,要么只有一个右子节点,这两种情况都可以简化为前面讨论的简单情况。
// 删除节点的方法public void deleteNode(int key) {node = deleteRec(node, key);}private TreeNode deleteRec(TreeNode root, int key) {if (root == null) {return root;}// 如果键值小于根节点的值,则只可能在左子树中if (key < root.val) {root.left = deleteRec(root.left, key);}// 如果键值大于根节点的值,则只可能在右子树中else if (key > root.val) {root.right = deleteRec(root.right, key);}// 如果键值等于根节点的值,那么这就是我们要删除的节点else {// 节点没有子节点,即为叶子节点if (root.left == null && root.right == null) {root = null;}// 节点只有一个子节点else if (root.left == null) {TreeNode temp = root;root = root.right;temp = null; // 帮助垃圾回收} else if (root.right == null) {TreeNode temp = root;root = root.left;temp = null; // 帮助垃圾回收}// 节点有两个子节点else {// 找到右子树的最小节点TreeNode minNodeForRight = minValueNode(root.right);// 复制最小节点的值到当前节点root.val = minNodeForRight.val;// 删除右子树中最小的节点root.right = deleteRec(root.right, minNodeForRight.val);}}return root;}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

交通 | 电动汽车车辆路径问题及FRVCP包的调用以及代码案例

编者按&#xff1a; 电动汽车的应用给车辆路线问题带来了更多的挑战&#xff0c;如何为给定路线行驶的电动汽车设计充电决策是一个需要解决的难题&#xff0c;本文介绍了开源python包frvcpy使用精确式算法对该问题求解。 文献解读&#xff1a;Aurelien Froger, Jorge E Mendo…

H.265 与 H.264 的主要区别

H.265 与 H.264 的主要区别 H.265 与 H.264 的主要区别各模块技术差异汇总宏块划分帧内预测模式帧间预测模式去块滤波ALF自适应环路滤波采样点自适应偏移&#xff08;Sample Adaptive Offset&#xff09;滤波并行化设计TileEntropy sliceDependent SliceWPP&#xff08;Wavefro…

红米A2/A2+/POCO C51手机秒解BL+快速获取root权限+解谷歌锁刷机救砖教程

红米A2/A2/POCO C51手机是目前小米公司针对于国外用户的1个独立的品牌&#xff0c;或者和国内的红米手机都非常相似&#xff0c;几款手机由于硬件非常接近&#xff0c;我们这里将其放在一起和大家介绍而从他们的代号中我们可以得知&#xff0c;目前A2/POCO的代号为water&#x…

Text-to-SQL小白入门(12)Awesome-Text2SQL开源项目star破1000

项目介绍 项目地址 23年9月份刚开源这个项目&#xff0c;大半年过去了&#xff0c;star数终于破1000啦&#xff0c;决定在知乎更新一下内容&#xff0c;看看内容变化&#xff0c;知乎有上当时项目介绍的链接&#xff1a;追光者&#xff1a;Text-to-SQL小白入门&#xff08;六&…

水稻病害检测(YOLO数据集,多分类,稻瘟病、纹枯病、褐斑病、枯心病、霜霉病、水稻细菌性条纹斑病、稻苞虫)

是自己利用LabelImg工具进行手工标注&#xff0c;数据集制作不易&#xff0c;请尊重版权&#xff08;稻瘟病、纹枯病、褐斑病、枯心病、霜霉病、水稻细菌性条纹斑病、稻苞虫&#xff09; 如果需要yolv8检测模型和数据集放在一起的压缩包&#xff0c;可以关注&#xff1a;最新最…

汽车车灯的材料是什么?汽车车灯的灯罩如果破损破裂破洞了要怎么修复?

汽车车灯的材料主要包括灯罩和灯底座两部分&#xff0c;它们所使用的材料各不相同。 车灯罩的材料主要是透明且具有良好耐热性和耐紫外线性能的塑料。其中&#xff0c;聚碳酸酯&#xff08;PC&#xff09;是一种常用的材料&#xff0c;它具有高抗冲击性、耐化学品腐蚀和优良的…

【C++庖丁解牛】C++11---lambda表达式 | 包装器

&#x1f341;你好&#xff0c;我是 RO-BERRY &#x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f384;感谢你的陪伴与支持 &#xff0c;故事既有了开头&#xff0c;就要画上一个完美的句号&#xff0c;让我们一起加油 目录 1. lambda表达式1.1 C98中…

数字旅游打造个性化旅行体验,科技让旅行更精彩:借助数字技术,旅行者可以定制专属旅行计划,享受个性化的旅行体验

目录 一、引言 二、数字旅游的兴起与发展 三、数字技术助力个性化旅行体验 1、智能推荐系统&#xff1a;精准匹配旅行者需求 2、定制化旅行计划&#xff1a;满足个性化需求 3、实时互动与分享&#xff1a;增强旅行体验 四、科技提升旅行便捷性与安全性 1、移动支付与电…

28.Gateway-网关过滤器

GatewayFilter是网关中提供的一种过滤器&#xff0c;可以多进入网关的请求和微服务返回的响应做处理。 GatewayFilter(当前路由过滤器&#xff0c;DefaultFilter) spring中提供了31种不同的路由过滤器工厂。 filters针对部分路由的过滤器。 default-filters针对所有路由的默认…

重定义大语言模型的记忆能力:对抗性压缩如何挑战现有测量法

DeepVisionary 每日深度学习前沿科技推送&顶会论文分享&#xff0c;与你一起了解前沿深度学习信息&#xff01; Rethinking LLM Memorization through the Lens of Adversarial Compression 引言&#xff1a;探索大型语言模型的记忆能力 在当今信息时代&#xff0c;大型…

Pyspark+关联规则 Kaggle购物篮分析案例

数据集地址&#xff1a;Market Basket Analysis | Kaggle 我的NoteBook地址&#xff1a;pyspark Market Basket Analysis | Kaggle 零售商期望能够利用过去的零售数据在自己的行业中进行探索&#xff0c;并为客户提供有关商品集的建议&#xff0c;这样就能提高客户参与度、改…

50. 【Android教程】xml 数据解析

xml 是一种标记扩展语言&#xff08;Extension Mark-up Language&#xff09;&#xff0c;学到这里大家对 xml 语言一定不陌生&#xff0c;但是它在 Android 中的运用其实只是冰山一角。抛开 Android&#xff0c;XML 也被广泛运用于各种数据结构中。在运用 xml 编写 Android 布…

【氮化镓】GaN器件在航天器高可靠正向转换器中应用

文章是发表在《IEEE Journal of Emerging and Selected Topics in Power Electronics》2022年10月第10卷第5期上的一篇关于GaN(氮化镓)器件在航天器高可靠性正向转换器中应用的研究。文章的作者是匹兹堡大学电气与计算机工程系的Aidan Phillips, Thomas Cook和Brandon M. Gra…

ubuntu安装python

点个关注吧&#xff0c;谢谢&#xff01; python现在还未安装 解决方法&#xff1a; 一、更新软件包列表 sudo apt update二、根据需要安装 sudo apt install python3 sudo apt install python2 sudo apt install python3.8完成 三、添加链接 解决只有python3&#xff0c;没…

spring boot 自定义starter示例

springboot 约定规范 Starter项目的命名规范 建议自定义的starter 以 xxx-spring-boot-starter 命名&#xff0c;官方的Starter一般都是以spring-boot-starter-为前缀。这样做的目的是为了避免与官方或其他第三方提供的Starter产生冲突或混淆。 Starter项目的结构规范(重要) …

【C++容器map】map的相关用法

&#x1f389;博主首页&#xff1a; 有趣的中国人 &#x1f389;专栏首页&#xff1a; C进阶 &#x1f389;其它专栏&#xff1a; C初阶 | 初阶数据结构 | Linux 本篇文章主要讲解 C容器之map相关用法 的相关内容 文章目录 1. map的介绍2. map的使用<font size5 color #…

在做题中学习(48):朴素的二分查找

. - 力扣&#xff08;LeetCode&#xff09; 解法一&#xff1a; 暴力求解 for循环中&#xff0c;从nums[0]枚举到nums[n-1]&#xff0c;依次判断&#xff0c;返回 target的值。 时间复杂度 : O(N) :因为要遍历一遍数组 解法二&#xff1a;二分查找 因为此数组为有序的…

Springboot+Vue+小程序+基于微信小程序护农远程看护系统

开发平台为idea&#xff0c;maven管理工具&#xff0c;Mybatis操作数据库&#xff0c;根据市场数字化需要为农户打造小程序可远程查看农场的种植情况。项目是调试&#xff0c;讲解服务均可有偿获取&#xff0c;需要可在最下方QQ二维码处联系我。 SpringbootVue小程序&#xff…

QT——简易计算机(从0开始)

目录 一、题目描述&#xff1a; 二、创建工程&#xff1a; 三、UI界面设计&#xff1a; 四、程序编写&#xff1a; 五、总程序&#xff1a; 六、windows可执行文件 七、实现效果 一、题目描述&#xff1a; 创建一个简单的图形用户界面(GUI),包括一个文本框用于显示计算结…