有序二叉树的增删改查（源代码讲解）

有序二叉树的相关实体类

TreeNode类

二叉树结点类，包含三个属性：value，leftChild，rightChild

有序二叉树类就包括这样一个根节点

剩下的getter和setter方法，有参无参构造，toString方法都是老生长谈，在这里略过不表

public class TreeNode {

    private int value;

    private TreeNode LeftChild;

    private TreeNode rightChild;

    public TreeNode(int value, TreeNode leftChild, TreeNode rightChild) {
        this.value = value;
        LeftChild = leftChild;
        this.rightChild = rightChild;
    }

    public TreeNode() {

    }


    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "value=" + value +
                ", LeftChild=" + LeftChild +
                ", rightChild=" + rightChild +
                '}';
    }

    public TreeNode getLeftChild() {
        return LeftChild;
    }

    public void setLeftChild(TreeNode leftChild) {
        LeftChild = leftChild;
    }

    public TreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(TreeNode rightChild) {
        this.rightChild = rightChild;
    }
}

有序二叉树类

有序二叉树只有一个属性：TreeNode root

public class BinarySearchTree {

    private TreeNode root;

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }
    
}

现在我们开始有序二叉树的CURD讲解

insert：有序二叉树的结点插入

比结点value值大，放右边；反之，放左边

注意结点的遍历，循环的终止条件

这个方法要放到BinarySearchTree实体类当中，作为成员方法

    // 插入
    public void insert(int value) {
    	// 创建新结点
        TreeNode newNode = new TreeNode();
        newNode.setValue(value);
        // 若根节点为null，则新插入的结点就是根节点
        if (root == null) {
            root = newNode;
            return;
        }
        // 根节点不为null
        // index拷贝root，作为查询指针
        TreeNode index = root;
        // pre作为index的parent存在
        TreeNode pre = null;
        while (index != null) {
            if (value > index.getValue()) {
                pre = index;
                index = index.getRightChild();
            } else {
                pre = index;
                index = index.getLeftChild();
            }
        }
        // 此时pre指针指向的位置就是应该插入的位置，比较大小
        if (value > pre.getValue()) {
            pre.setRightChild(newNode);
        } else {
            pre.setLeftChild(newNode);
        }
    }

demo

public class TreeTest {

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setRoot(new TreeNode(14, null, null));
        tree.insert(5);
        tree.insert(20);
        tree.insert(4);
        tree.insert(8);
        tree.insert(7);
        tree.insert(9);
        tree.insert(17);
        tree.insert(22);
        tree.insert(15);
        tree.insert(19);
        System.out.println(tree.getRoot());
    }
}

输出结果：
在这里插入图片描述

query：有序二叉树的查询

遍历查询

时间复杂度O(n)，其实就是全部结点都访问一遍来查询

二叉树的遍历

根据遍历方式优先级的不同，可以分为深度优先遍历（DFS）和广度优先遍历（BFS）

深度优先遍历

先序遍历（根左右，DLR），中序遍历（左根右，LDR）和后序遍历（左右根，LRD）

以上三种遍历，是深度优先遍历的三种形式，他们都是深度优先的

这里的D是data的意思，理解成父节点即可

这三种遍历基本都是使用递归完成，代码清晰而且很好理解，使用非递归的方式（循环+栈）也可以，在这里不做展示

先序遍历
    public void beforeSearch(TreeNode treeNode) { // DLR
        // 根左右

        // 先访问根节点，打印
        if (treeNode == null) {
            return;
        }
        // 打印根节点
        System.out.println(treeNode.getValue());
        // 再访问到最深的左结点，不打印
        beforeSearch(treeNode.getLeftChild());
        // 最后访问到最深的右结点，不打印
        beforeSearch(treeNode.getRightChild());

    }
demo
public class TreeTest {

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setRoot(new TreeNode(14, null, null));
        tree.insert(5);
        tree.insert(20);
        tree.insert(4);
        tree.insert(8);
        tree.insert(7);
        tree.insert(9);
        tree.insert(17);
        tree.insert(22);
        tree.insert(15);
        tree.insert(19);
        System.out.println("=============");
        tree.beforeSearch(tree.getRoot());
    }
}

运行结果
在这里插入图片描述

中序遍历
    public void middleSearch(TreeNode treeNode) {// LDR

        // 左根右
        if (treeNode == null) {
            return;
        }
        // 只有碰到左结点才会打印
        middleSearch(treeNode.getLeftChild());
        System.out.println(treeNode.getValue());
        middleSearch(treeNode.getRightChild());

    }
demo
public class TreeTest {
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setRoot(new TreeNode(14, null, null));
        tree.insert(5);
        tree.insert(20);
        tree.insert(4);
        tree.insert(8);
        tree.insert(7);
        tree.insert(9);
        tree.insert(17);
        tree.insert(22);
        tree.insert(15);
        tree.insert(19);
        System.out.println("=============");
        tree.middleSearch(tree.getRoot());
     }
}

运行结果
在这里插入图片描述
我们可以发现，有序二叉树中序遍历的结果，实际上就是有序二叉树从小到大排列的结果

后序遍历
    public void afterSearch(TreeNode treeNode) {// LRD
        //左右根
        if (treeNode == null) {
            return;
        }
        afterSearch(treeNode.getLeftChild());
        afterSearch(treeNode.getRightChild());
        System.out.println(treeNode.getValue());
    }
demo
public class TreeTest {

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setRoot(new TreeNode(14, null, null));
        tree.insert(5);
        tree.insert(20);
        tree.insert(4);
        tree.insert(8);
        tree.insert(7);
        tree.insert(9);
        tree.insert(17);
        tree.insert(22);
        tree.insert(15);
        tree.insert(19);
        System.out.println("=============");
        tree.afterSearch(tree.getRoot());
   }
}

在这里插入图片描述

广度优秀遍历（BFS）

BFS，BreadthFirstSearch,广度优先遍历, 需要队列来辅助实现

队列的存取特点与栈相反，先进先出FIFO

public void bfs(TreeNode treeNode) {
		// 定义队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 树为空直接返回
        if (treeNode == null) {
            return;
        }
        // 首先将根节点放入队列
        queue.add(treeNode);
        while (!queue.isEmpty()) {
            // 队列末尾节点出列
            treeNode = queue.pop();
            System.out.println(treeNode.getValue());
            // 左右结点放入队列
            if (treeNode.getLeftChild() != null) {
                queue.add(treeNode.getLeftChild());
            }
            if (treeNode.getRightChild() != null) {
                queue.add(treeNode.getRightChild());
            }
        }
    }

运行结果：
在这里插入图片描述

二分查询

时间复杂度最好O(logn)，前提是二叉树有序，而且相对平衡（否则会退化成单链表）

没什么可说的，比当前结点值大就向右遍历，反之则向左遍历

 // 二分查找
    public TreeNode binarySearch(TreeNode treeNode, int val) {
		// 复制根节点指针    		
        TreeNode index = treeNode;
        while (index != null) {
            if (val == index.getValue()) {
                System.out.println(val + "找到了");
                return index;	
            } else if (val > index.getValue()) {
                index = index.getRightChild();
            } else if (val < index.getValue()) {
                index = index.getLeftChild();
            }
        }
        return null;
    }

demo

public class TreeTest {

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setRoot(new TreeNode(14, null, null));
        tree.insert(5);
        tree.insert(20);
        tree.insert(4);
        tree.insert(8);
        tree.insert(7);
        tree.insert(9);
        tree.insert(17);
        tree.insert(22);
        tree.insert(15);
        tree.insert(19);
//         二分查找
        System.out.println(tree.binarySearch(tree.getRoot(), 15));
    }
}

运行结果
在这里插入图片描述

update：有序二叉树的编辑

有序二叉树无法直接编辑，因为编辑前后要保证有序二叉树的性质不变

所以编辑变成了删除+插入

delete：有序二叉树的删除

有序二叉树的删除操做很复杂，我们不是直接删除找到的结点，而是将其与叶子结点交换，然后删除交换后的叶子结点

如果是根节点，不允许删除；
如果是叶子结点，直接删除；
如果是中间的结点，就需要交换+删除；

这里的交换也是大有讲究

如图所示
在这里插入图片描述

假设要删除结点8，我们需要找一个结点与结点8交换，然后将交换后的结点删除，要找哪个结点呢？

我们需要明白结点8的性质：比5大，比14小，我们需要重新找到一个这样的结点来替换结点8

比14小好说，只要从根节点的左子树部分找即可

比5大要怎么满足？

显然，要从结点8的右子树去寻找，右子树的每一个结点都比8大，所以肯定也比5大

但是具体是哪一个呢？

我们发现，这样的结点交换之后，依然需要满足有序二叉树的性质，如果交换的不是叶子结点，那么后续还需要新的交换

如果交换叶子节点，那么交换就会变得非常简单

结论

要删除的结点是父节点的左孩子时，就要去左孩子所在的左子树中寻找最右叶子结点去替换要删除结点；如果左子树不存在右孩子（比如只有左孩子），则直接将祖孙连接
要删除的结点是父节点的右孩子时，就要去右孩子所在的右子树中寻找最左叶子结点去替换要删除结点；如果右子树不存在左孩子（比如只有右孩子），则直接将祖孙连接

代码

// 删除: 根节点不是叶子结点的情况下不允许删除/删除叶子结点/其他结点的删除
    // 1. 先遍历找到结点位置，
    // 2. 然后判断是否存在父节点
    // 3. 确定要删除的结点是左子树还是右子树
    // 4. 根据第三步的情况删除（左子树则parent.setLeftChild(null);右子树则parent.setRightChild(null)）
    public void delete(TreeNode treeNode, int val) {
    	// 为空直接返回
        if (treeNode == null) {
            return;
        }
        // 指针拷贝
        TreeNode index = treeNode;
        TreeNode parent = null;
        // 查询要删除的结点
        while (index != null) {
            if (val == index.getValue()) {
                System.out.println(val + "找到了");
                break;
            } else if (val > index.getValue()) {
                parent = index;
                index = index.getRightChild();
            } else if (val < index.getValue()) {
                parent = index;
                index = index.getLeftChild();
            }
        }
        // 找不到要删除的结点，直接返回
        if (index == null) {
            System.out.println("有序二叉树中无值为" + val + "的结点");
            return;
        }
        // 要删除的结点是根节点，直接返回
        if (parent == null) {
            System.out.println("根节点不允许删除");
            return;
        }

        // 如果index是parent的左子树，那么就去index子树当中搜索最右结点（最大结点）；若index是parent的右子树，就去找index子树中最左结点（最小结点）
		
        // 跳出循环后，index指向要删除的结点，parent指向删除结点的父节点
        // 分情况讨论
        // 情况1：index是叶子结点，直接删除
        if (index.getRightChild() == null && index.getLeftChild() == null) {
            parent.setLeftChild(null);
            return;
        }
        // 判断要删除结点的类型：左孩子还是右孩子        
        if (index.getValue() < parent.getValue()) {
            // 情况2：index不是叶子节点，但是右子树为空，祖孙连接
            if (index.getRightChild() == null) {
                parent.setLeftChild(index.getLeftChild());
                return;
            }
            // 情况3：index不是叶子节点,右子树不为空，遍历查询最右结点
   			// 指针拷贝，标记叶子节点和叶子结点的父节点
        	TreeNode query = index;
        	TreeNode queryParent = parent;
            while (query.getRightChild() != null) {
                // 查询最右结点
                queryParent = query;
                query = query.getRightChild();
            }
            // 数值交换,删除叶子节点
            index.setValue(query.getValue());
            queryParent.setRightChild(null);
        } else {
           	// 情况2：index不是叶子节点，但是左子树为空，祖孙连接
            if (index.getLeftChild() == null) {
                parent.setRightChild(index.getRightChild());
            }
            // 情况3：index不是叶子节点,且左子树不为空，遍历查询最左结点
            // 指针拷贝，标记叶子节点和叶子结点的父节点
            TreeNode query = index;
            TreeNode queryParent = parent;
            while (query.getLeftChild() != null) {
                // 查询最左结点
                queryParent = query;
                query = query.getLeftChild();
            }
            // 数值交换,删除叶子节点
            index.setValue(query.getValue());
            queryParent.setLeftChild(null);
        }
    }

demo

public class TreeTest {

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setRoot(new TreeNode(14, null, null));
        tree.insert(5);
        tree.insert(20);
        tree.insert(4);
        tree.insert(8);
        tree.insert(7);
        tree.insert(9);
        tree.insert(17);
        tree.insert(22);
        tree.insert(15);
        tree.insert(19);


        tree.delete(tree.getRoot(), 14);
        tree.delete(tree.getRoot(), 100);

        tree.delete(tree.getRoot(), 5);
        System.out.println(tree.getRoot());

    }
}

运行结果：
在这里插入图片描述

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

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

相关文章

Zotero插件ZotCard中AI-NNDL文献笔记卡分享及卡片使用方法

Zotero插件ZotCard中AI-NNDL文献笔记卡分享及卡片使用方法

一、卡片社区分享 github&#xff1a;ZotCard插件AI-NNDL论文卡片模板 Issue #67 018/zotcard (github.com) 二、卡片效果预览 ZotCard插件AI-NNDL论文卡片模板是关于人工智能神经网络与深度学习论文的笔记卡片&#xff0c;效果预览如下图&#xff1a; 三、卡片代码 经过了…
阅读更多...
【MySQL】MySQL在Centos 7环境安装

【MySQL】MySQL在Centos 7环境安装

目录 准备工作 第一步&#xff1a;卸载不要的环境 第二步&#xff1a;下载官方的mysql 第三步 上传到Linux中 第四步 安装 正式安装 启动 ​编辑 登录 准备工作 第一步&#xff1a;卸载不要的环境 使用root进行安装 如果是普通用户&#xff0c;使用 su - 命令&#…
阅读更多...
a == 1 a== 2 a== 3 返回 true ？

a == 1 a== 2 a== 3 返回 true ？

1. 前言 下面这道题是 阿里、百度、腾讯 三个大厂都出过的面试题&#xff0c;一个前端同事跳槽面试也被问了这道题 // &#xff1f; 位置应该怎么写&#xff0c;才能输出 trueconst a ?console.log(a 1 && a 2 && a 3) 看了大厂的面试题会对面试官的精神…
阅读更多...
r3live 使用前提 雷达-相机外参标定 livox_camera_lidar_calibration

r3live 使用前提 雷达-相机外参标定 livox_camera_lidar_calibration

标定的是相机到雷达的,R3live下面配置的雷达到相机的,所以要把得到外参旋转矩阵求逆,再填入,平移矩阵则取负 港科大livox_camera_calib虽然操作方便&#xff0c;但是使用mid360雷达会有视角问题&#xff08;投影三维点到相机&#xff09;&#xff0c;尝试了很多场景&#xff0c…
阅读更多...
蓝牙介绍 1

蓝牙介绍 1

大纲 蓝牙简介 BLE协议栈 开发环境搭建I OSAL层工作原理 UART实验 LED实验、ADC实验 深入了解GAP和GATT 添加特征值-主从机通信实验 无线网络开发 进阶学习 蓝牙智能手环介绍 1 蓝牙4.0简介 为什么需要蓝牙技术 wifi功耗太高&#xff0c;电池无法支撑 短距离、小电池支持的设…
阅读更多...
[论文翻译]GLU Variants Improve Transformer

[论文翻译]GLU Variants Improve Transformer

引言 今天带来一篇短小精悍的论文GLU Variants Improve Transformer笔记&#xff0c;作者提出了GLU1的一种变体。 GLU(Gated Linear Units,门控线性单元)由两个线性投影的逐元素乘积组成&#xff0c;其中一个首先经过sigmoid函数。GLU的变体是可能生效的&#xff0c;可以使用…
阅读更多...
Leetcode刷题之删除有序数组的重复项

Leetcode刷题之删除有序数组的重复项

一、题目描述 删除有序数组的重复项 给你一个 非严格递增排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次 &#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums…
阅读更多...
【计算机网络】ip子网划分--超详细例题解析

【计算机网络】ip子网划分--超详细例题解析

Hello!这一篇主要是计算机网络中的ip地址子网划分的例题&#xff0c;这里例举了四个题型。保证即便从0也可以掌握&#xff01;(前面是一些预备知识&#xff0c;不熟悉的小伙伴一定要看下学习下哦&#xff5e;) 这也是博主的学习过程&#xff0c;做题中仅仅我的理解哦。若文章中…
阅读更多...
1.Hexo安装和环境搭建引导

1.Hexo安装和环境搭建引导

Hexo是一个依赖于一个名为nodejs的程序 因此安装它的方式在Mac和Windows上实际上是一样的 为了在电脑上安装Hexo 需要做两件事 nodejs&#xff0c;基本上是hexo依赖运行的JavaScript框架 Node.js — Run JavaScript Everywheregit&#xff0c;是一个程序&#xff0c;用来管理电…
阅读更多...
前端知识学习笔记-六（vue）

前端知识学习笔记-六（vue）

简介 Vue是前端优秀框架是一套用于构建用户界面的渐进式框架 Vue优点 Vue是目前前端最火的框架之一 Vue是目前企业技术栈中要求的知识点 vue可以提升开发体验 Vue学习难度较低 Vue开发前准备 一、nodejs环境 Nodejs简介 Nodejs诞生于2009年&#xff0c;主攻服务器方向&#x…
阅读更多...
IDEA中sql语句智能提示设置

IDEA中sql语句智能提示设置

选中一句sql语句&#xff0c;点击鼠标右键 指定数据库
阅读更多...
机器学习入门实战1：鸢尾花分类

机器学习入门实战1：鸢尾花分类

花名&#xff1a;鸢尾花 别名&#xff1a;爱丽丝、蓝蝴蝶、紫蝴蝶 花语&#xff1a;爱的使者、长久思念 花期&#xff1a;5-6月 颜色&#xff1a;蓝色、紫色、白色、粉色等 鸢尾花主要色彩为蓝紫色&#xff0c;有“蓝色妖姬”的美誉&#xff0c;因花瓣形如鸢鸟尾巴而得名&#…
阅读更多...
vi编辑器

vi编辑器

目录 一、文本编辑器vi命令 1.作用&#xff1a; 2.vi和vim 二、vi编辑器的三种模式 三、输入模式 四、命令模式 五、末行模式 一、文本编辑器vi命令 1.作用&#xff1a; 创建或修改文本文件 维护Linux系统中的各种配置文件 2.vi和vim vi:类UNIX操作系统的默认文本编辑器…
阅读更多...
揭示空间依赖性：运用先进自相关技术挖掘地理数据中的规律

揭示空间依赖性：运用先进自相关技术挖掘地理数据中的规律

原文地址&#xff1a;deciphering-spatial-dependence-unlocking-patterns-in-geographical-data-through-advanced 2024 年 4 月 9 日 简介 空间自相关分析是用于衡量和分析一组空间数据点在地理空间中相关程度的统计方法。该技术是空间分析和地理信息系统 (GIS) 的组成部分…
阅读更多...
第十五届蓝桥杯c++b组赛后复盘和真题展示

第十五届蓝桥杯c++b组赛后复盘和真题展示

题目变成八道了&#xff0c;分数一百分可能&#xff0c;感觉拿奖难度还是很高 第一题是一个简单的握手问题 答案算出来1204&#xff0c;纯手写 第二题是 物理题 纯蒙&#xff0c;随便猜了个轨迹&#xff0c;答案具体忘了&#xff0c;最后是 .45 第三题暴力 第四题 我是傻逼…
阅读更多...
分布式技术--------------ELK大规模日志实时收集分析系统

分布式技术--------------ELK大规模日志实时收集分析系统

目录 一、ELK日志分析系统 1.1ELK介绍 1.2ELK各组件介绍 1.2.1ElasticSearch 1.2.2Kiabana 1.2.3Logstash 1.2.4可以添加的其它组件 1.2.4.1Filebeat filebeat 结合logstash 带来好处 1.2.4.2缓存/消息队列&#xff08;redis、kafka、RabbitMQ等&#xff09; 1.2.4.…
阅读更多...
【C++】详解类的--封装思想（让你丝滑的从C语言过度到C++！！）

【C++】详解类的--封装思想（让你丝滑的从C语言过度到C++！！）

目录 一、前言 二、【面向过程】 与 【面向对象】 三、结构体 与 类 &#x1f34e;C中结构体的变化 &#x1f349;C中结构体的具体使用 &#x1f350;结构体 --> 类 ✨类-----语法格式&#xff1a; ✨类的两种定义方式&#xff1a; 四、类的访问限定符及封装【⭐】 …
阅读更多...
python--4函数def,本质、值传递、引用传递、默认值参数、*参数名、**变量、lambda [参数]: 函数、偏函数、递归

python--4函数def,本质、值传递、引用传递、默认值参数、*参数名、**变量、lambda [参数]: 函数、偏函数、递归

学习目标&#xff1a; 函数def,本质、值传递、引用传递、默认值参数、*参数名、**变量、lambda [参数]: 函数、偏函数、递归 学习内容&#xff1a; 函数def,本质、值传递、引用传递、默认值参数、*参数名、**变量、lambda [参数]: 函数、偏函数、递归 目录 学习目标&…
阅读更多...
【零基础学鸿蒙】ArkTS开发语言介绍

【零基础学鸿蒙】ArkTS开发语言介绍

在之前的教学中&#xff0c;我们学习了下载安装DevEco Studio等相关知识。今天开始讲ArkTS 1.1 TypeScrip快速入门 学习TypeScript对于HarmonyOS应用开发至关重要。在HarmonyOS中&#xff0c;主力编程语言为ArKTS&#xff0c;它是基于TypeScript的一种语言&#xff0c;其通过…
阅读更多...
Vue 3 项目中如何使用 TypeScript 类型来优化 Vuex 的状态管理？

Vue 3 项目中如何使用 TypeScript 类型来优化 Vuex 的状态管理？

在 Vue 3 项目中&#xff0c;使用 TypeScript 可以极大地优化 Vuex 的状态管理&#xff0c;提供更强的类型检查和更好的开发体验。以下是一些使用 TypeScript 来优化 Vuex 状态管理的方法&#xff1a; 定义状态类型&#xff1a; 使用 TypeScript 的接口&#xff08;Interfaces&…
阅读更多...
最新文章

Copyright @ 2022~2023