二叉搜索树java实现

顾名思义,二叉搜索树是一棵二叉树,每个节点就是一个对象,这个对象包含属性left、right和parent。left指向节点的左孩子,right指向节点的右孩子,parent指向节点的父节点(双亲)。如果某个孩子节点和父节点不存在,则相应的属性为null。根节点是树中唯一父节点指针为null的节点。

二叉搜索树中的关键字满足以下性质:

假设x是二叉搜索树中的一个节点,如果y是x的左子树中的一个节点,那么y.key ≤ x.key;如果y是x右子树中的一个节点,那么y.key ≥ x.key。

两棵二叉搜索树的示意图如下:
在这里插入图片描述
二叉搜索树支持查询、求最大值、最小值以及追加和删除等操作,其基于java的简单实现如下:

/**
 * 数据结构-二叉搜索树
 */
public class BinarySearchTree {

    /**
     * 树的根节点
     */
    private Node root;

    /**
     * 根据关键字搜索节点
     *
     * @param key 关键字
     * @return key所在的节点
     */
    public Node search(int key) {
        Node node = root;
        while (node != null && key != node.key) {
            // 如果key小于当前节点的key,则往左孩子节点找,否则往右孩子节点找
            if (key < node.key) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return node;
    }

    /**
     * 获取key最小的节点
     *
     * @return key最小的节点
     */
    public Node min() {
        return min(root);
    }

    /**
     * 获取以node为根的子树中key最小的节点
     *
     * @param node 子树根节点
     * @return 子树中key最小的节点
     */
    public Node min(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    /**
     * 获取key最大的节点
     *
     * @return key最大的节点
     */
    public Node max() {
        return max(root);
    }

    /**
     * 获取以node为根的子树中key最大的节点
     *
     * @param node 子树根节点
     * @return 子树中key最大的节点
     */
    public Node max(Node node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    /**
     * 向树中添加节点
     *
     * @param key 插入节点的key
     */
    public void add(int key) {
        Node node = root;
        Node temp = null;

        // 寻找合适的节点添加新节点
        while (node != null) {
            temp = node;
            if (key < node.key) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        Node newNode = new Node();
        newNode.parent = temp;
        newNode.key = key;
        if (temp == null) { // 该树上还没有节点
            root = newNode;
        } else if (key < temp.key) {
            temp.left = newNode;
        } else {
            temp.right = newNode;
        }
    }

    /**
     * 删除以key为关键字的节点
     *
     * @param key 关键字
     */
    public void delete(int key) {
        Node node = search(key);
        if (node.left == null) {
            transplant(node, node.right);
        } else if (node.right == null) {
            transplant(node, node.left);
        } else {
            Node min = min(node.right);
            if (!min.parent.equals(node)) {
                transplant(min, min.right);
                min.right = node.right;
                min.right.parent = min;
            } 
            transplant(node, min);
            min.left = node.left;
            min.left.parent = min;
        }
    }

    /**
     * 用node2为跟的子树替换node1为根的子树
     *
     * @param node1 子树1
     * @param node2 子树2
     */
    private void transplant(Node node1, Node node2) {
        // node1是根节点
        if (node1.parent == null) {
            root = node2;
        } else if (node1 == node1.parent.left) { // 如果node1是左孩子
            node1.parent.left = node2;
        } else { // 如果node1是右孩子
            node1.parent.right = node2;
        }
        if (node2 != null) {
            node2.parent = node1.parent;
        }
    }

    public Node getRoot() {
        return root;
    }

    /**
     * 树上的节点
     */
    public static class Node {
        /**
         * 节点关键字
         */
        private int key;

        /**
         * 节点的左孩子
         */
        private Node left;

        /**
         * 节点的右孩子
         */
        private Node right;

        /**
         * 节点的父节点
         */
        private Node parent;

        public int getKey() {
            return key;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }

        public Node getParent() {
            return parent;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return key == node.key && Objects.equals(left, node.left)
                    && Objects.equals(right, node.right) && Objects.equals(parent, node.parent);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key, left, right, parent);
        }
    }
}

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

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

相关文章

校园圈子论坛,交友,帖子内短视频,二手市场,APP小程序H5三端交付,源码交付,支持二开

校园圈子论坛&#xff0c;交友频道&#xff0c;商城&#xff0c;二手市场&#xff0c;活动专区&#xff0c;短视频&#xff0c;从校园生活的方方面面展现出了充满活力和创造力的镜头。这个频道是一个让学生们相互交流、结识新朋友的平台&#xff0c;不仅有交友功能&#xff0c;…

RK3588平台开发系列讲解(嵌入式AI篇)嵌入式AI模型的部署

文章目录 一、嵌入式AI模型的部署二、AI模型训练框架有哪些三、rknn-toolkit可支持转换的模型沉淀、分享、成长,让自己和他人都能有所收获!😄 📢 本篇将给大家介绍嵌入式AI模型的部署。 一、嵌入式AI模型的部署 模型的部署,是指将训练好的模型放到运行环境中进行推理的…

自动解决IP冲突的问题 利用批处理更改末位IP循环+1直到网络畅通为止 解放双手 事半功倍

好久没出来写点什么了&#xff0c;难道今天有点时间&#xff0c;顺便把这两天碰到的问题出个解决方法吧。 这几天去客户那儿解决网络问题&#xff0c;因为客户的网络是固定的静态IP&#xff0c;因为没做MAC绑定&#xff0c;IP固定在本地电脑上&#xff0c;只要上不了网&#xf…

《安富莱嵌入式周报》第327期:Cortex-A7所有外设单片机玩法LL/HAL库全面上线,分享三款GUI, PX5 RTOS推出网络协议栈,小米Vela开源

周报汇总地址&#xff1a;嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 1、2023 Hackaday大赛胸牌开源 Vectorscope-main.zip (66.83MB) GitHub - Hack-a-Day/Vectorscope: Vectorscope badg…

逸学java【初级菜鸟篇】9.3 Stream流

hi&#xff0c;我是逸尘&#xff0c;一起学java吧 得益于Lambda所带来的函数式编程&#xff0c;引入了一个全新的Stream流概念&#xff08;就是都基本使用lambda的形式&#xff09;。 流处理 我们首先理解什么是流处理&#xff0c;它类似于sql语句&#xff0c;可以执行非常复…

【MATLAB源码-第85期】基于farrow结构的滤波器仿真,截止频率等参数可调。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 Farrow结构是一种用于实现可变数字滤波器的方法&#xff0c;尤其适用于数字信号处理中的采样率转换和时变滤波。它通过多项式近似来实现对滤波器系数的平滑变化&#xff0c;使得滤波器具有可变的群延时或其他参数。 Farrow结…

AR道具特效制作工具

AR&#xff08;增强现实&#xff09;技术已经逐渐渗透到各个行业&#xff0c;为企业带来了全新的营销方式和用户体验。在这个背景下&#xff0c;美摄科技凭借其强大的技术实力和创新精神&#xff0c;推出了一款专为企业打造的美摄AR特效制作工具&#xff0c;旨在帮助企业轻松实…

8年老鸟整理,自动化测试-准备测试数据详细...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 大部分类型的测试…

陪玩圈子系统APP小程序H5,详细介绍,源码交付,支持二开!

陪玩圈子系统&#xff0c;页面展示&#xff0c;源码交付&#xff0c;支持二开&#xff01; 陪玩后端下载地址&#xff1a;电竞开黑陪玩系统小程序&#xff0c;APP&#xff0c;H5: 本系统是集齐开黑&#xff0c;陪玩&#xff0c;陪聊于一体的专业APP&#xff0c;小程序&#xff…

黑马React18: ReactRouter

黑马React: ReactRouter Date: November 21, 2023 Sum: React路由基础、路由导航、导航传参、嵌套路由配置 路由快速上手 1. 什么是前端路由 一个路径 path 对应一个组件 component 当我们在浏览器中访问一个 path 的时候&#xff0c;path 对应的组件会在页面中进行渲染 2. …

服务器主机安全的重要性及防护策略

在数字化时代&#xff0c;服务器主机安全是任何组织都必须高度重视的问题。无论是大型企业还是小型企业&#xff0c;无论是政府机构还是个人用户&#xff0c;都需要确保其服务器主机的安全&#xff0c;以防止数据泄露、网络攻击和系统瘫痪等严重后果。 一、服务器主机安全的重…

帝国cms开发一个泛知识类的小程序的历程记录

#帝国cms小程序# 要开发一个泛知识类的小程序&#xff0c;要解决以下几个问题。 1。知识内容的分类。 2。知识内容的内容展示。 3。知识内容的价格设置。 4。用户体系&#xff0c;为简化用户的操作&#xff0c;在用户进行下载的时候&#xff0c;请用户输入手机号&#xff…

AI:86-基于深度学习的街景图像地理位置识别

🚀 本文选自专栏:人工智能领域200例教程专栏 从基础到实践,深入学习。无论你是初学者还是经验丰富的老手,对于本专栏案例和项目实践都有参考学习意义。 ✨✨✨ 每一个案例都附带有在本地跑过的代码,详细讲解供大家学习,希望可以帮到大家。欢迎订阅支持,正在不断更新中,…

鸿蒙4.0开发笔记之DevEco Studio页面操作router的pushUrl页面跳转与back返回上一页(五)

一、认识组件 关于HarmonyOS中ArkTS的基础组件请参见文章鸿蒙4.0开发笔记之ArkTs语言基础与基本组件结构&#xff08;四&#xff09; 二、实现页面跳转pushUrl 1、操作说明 实现页面跳转的核心便是router.pushUrl的调用&#xff0c;操作起来也很简单&#xff0c;总共就四步…

微机原理_1

一、单项选择题(本大题共15小题,每小题3分,共45分。在每小题给出的四个备选项中,选出一个正确的答案,请将选定的答案填涂在答题纸的相应位置上。) 1,下列8086CPU标志寄存器的标志位中,不属于状态标志位的是(&#xff09; A. OF B. IF C. AF D. PF 8086微处理器可寻址访问的最大…

Ps:裁剪工具 - 裁剪预设的应用

裁剪工具提供了两种类型的裁剪方式。 一种是仅按宽高比&#xff08;比例&#xff09;进行裁剪&#xff0c;常在对图像进行二次构图时采用。 另一种则按指定的图像尺寸&#xff08;宽度值和高度值&#xff09;及分辨率&#xff08;宽 x 高 x 分辨率&#xff09;进行裁剪。其实质…

Sentinel 监控数据持久化(mysql)

Sentinel 实时监控仅存储 5 分钟以内的数据&#xff0c;如果需要持久化&#xff0c;需要通过调用实时监控接口来定制&#xff0c;即自行扩展实现 MetricsRepository 接口&#xff08;修改 控制台源码&#xff09;。 本文通过使用Mysql持久化监控数据。 1.构建存储表&#xff08…

leetcode:520. 检测大写字母

一、题目&#xff1a; 链接&#xff1a;520. 检测大写字母 - 力扣&#xff08;LeetCode&#xff09; 函数原型&#xff1a;bool detectCapitalUse(char* word) 二、思路&#xff1a; 本题较为简单&#xff0c;分为三种情况&#xff1a; 1.首字母大写&#xff0c;其余小写 2.首字…

Github Copilot AI编码完成工具

目录 一、GitHub Copilot 1、简介 2、工作原理 3、功能 二、GitHub Copilot X 1、什么是 GitHub Copilot X 2、GitHub Copilot X 的功能 三、支持、使用 1、支持 2、使用 四、实际研究、验证(代码方向) 1、代码生成 2、代码提示 3、生成测试用例 4、代码解释 5…

【Axure高保真原型】树形表格

今天和大家分享树形表格的原型模板&#xff0c;点击树的箭头可以打开或者收起子节点&#xff0c;点击表格内容&#xff0c;可以选中该行内容实现高亮变色效果&#xff0c;树形表格是通过中继器制作的&#xff0c;使用简单&#xff0c;只需要按要求填写中继器表格即可&#xff0…