Java实现二叉搜索树的插入、删除功能

二叉树的结构

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }
        TreeNode(int val) {
            this.val = val;
        }
    }

中序遍历

  • 中序遍历:从根节点开始遍历,遍历顺序是:左子树->当前节点->右子树,在中序遍历中,对每个节点来说:

只有当它的左子树都被遍历过了(或者没有左子树),它才会被遍历到。
在遍历右子树之前,一定会先遍历当前节点。

  • 中序遍历得到的第一个节点是没有左子树的(也许是叶子节点,也许有右子树)
  • 同理,中序遍历的最后一个节点没有右子树

代码递归实现

List<TreeNode> list = new ArrayList<>();
    public void inorder_traversal(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            inorder_traversal(root.left);
        }
        list.add(root);
        if (root.right != null) {
            inorder_traversal(root.right);
        }
    }

二叉搜索树的定义

  • 对每一个节点而言,左子树的所有节点小于它,右子树的所有节点大于它
  • 二叉树中每一个节点的值都不相同
  • 中序遍历的结果是升序的

这些定义决定了它的优点:查找效率快,因为二叉搜索树查找一个值时,可以通过二分查找的方式,平均时间复杂度为log2(n),n是二叉树的层树

下图就是一个标准的二叉搜索树,右子树比根节点大,左子树比根节点小

查找节点

给定一个值,使用循环在二叉搜索树中查找,找到该节点为止

  • 从根节点开始,不断循环进行比较
  • 给定值大于当前节点,就找右子树,小于就找左子树,值相等就是找到了节点

代码实现如下

public TreeNode search(TreeNode root, int val) {
        // 节点不为空,且不等于特定值
        while(root != null && root.val != val){
            if(root.val > val){
                root = root.left;
            }else{
                root = root.right;
            }
        }
        return root;
    }

添加节点

设要添加的节点为b, 二叉搜索树的添加是将b作为叶子节点加入到其中,因为叶子节点的增加比较简单。

  • 跟搜索过程类似,从根节点开始,不断循环找,找到一个适合新节点的位置

b值比当前节点大(小),并且当前节点的右(左)子树为空,将b插入到当前节点的右(左)子树中
如果当前节点的子树不为空,继续往下寻找

  • 使用一个随着搜索过程,不断更新的pre节点作为b的父节点,由pre节点添加b
  • 有可能要插入节点的二叉树是一颗空树,创建一个新的二叉树
  • 如果二叉搜索树中已经有跟b相等的值,不需要进行添加
 public TreeNode insertInto(TreeNode root, int val) {

        if (root == null) {
            // 树为空树的情况
            return new TreeNode(val);
        }
        // 一个临时节点指向根节点,用于返回值
        TreeNode tmp = root;
        TreeNode pre = root;

        while (root != null && root.val != val) {
            // 保存父节点
            pre = root;
            if (val > root.val) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        // 通过父节点添加
        if (val > pre.val) {
            pre.right = new TreeNode(val);
        } else {
            pre.left = new TreeNode(val);
        }
        return tmp;
    }

删除节点

删除过程比较复杂,先设二叉搜索树要删除的节点为a,a有以下三种情况

  • a为叶子节点
  • a有一个子节点
  • a有两个子节点删除叶子节点

过程类似搜索节点,找到到a后,通过它的父节点删除,并且叶子节点的删除不影响树的性质

有一个子节点的节点

要将a删除,并且保留a的子节点,让它的父节点连接它的子节点即可,因为a的子节点 与 a的父节点 关系 == a与 a的父节点 关系,所以不改变树的性质

  • 二叉搜索树的定义决定了:对于每一个节点而言,它 大于(小于) 它的父节点,那么它的子节点 大于(小于) 它的父节点

过程像这张图一样

删除有两个子节点的节点

我们可以通过交换节点的方式,让a 和 只有一个子节点的节点 交换,删除a的操作就变成了上面第二种情况。

我们知道中序遍历二叉搜索树的结果是升序的,如果要交换,肯定要找中序遍历在a左右两边的节点(因为值交换之后也满足二叉搜索树的定义)

  • 中序遍历的后(前)一个节点是右(左)子树中序遍历的第一个(最后一个)节点,而且它们都只有一个子节点

过程跟下面这张图类似(a的值与中序遍历的后一个节点交换,并删除这个节点)

代码实现

public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode tmp = root;
        TreeNode pre = root;
        // 寻找要删除的节点
        while (root != null && root.val != key) {
            pre = root;
            if (key > root.val) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        // 找不到符合的节点值
        if (root == null) {
            return tmp;
        }
        // 只有一个子节点或者没有子节点的情况
        if (root.left == null || root.right == null) {
            if (root.left == null) {
                // 要删除的是根节点,返回它的子节点
                if (root == tmp) {
                    return root.right;
                }
                // 使用父节点连接子节点,实现删除当前节点
                if (pre.left == root) {
                    pre.left = root.right;
                } else {
                    pre.right = root.right;
                }
            } else {
                if (root == tmp) {
                    return root.left;
                }
                if (pre.left == root) {
                    pre.left = root.left;
                } else {
                    pre.right = root.left;
                }
            }
            return tmp;
        }
        // 第一种方式
        // 寻找中序遍历的后一个节点,也就是右子树进行中序遍历的第一个节点,右子树的最左节点
        pre = root;
        TreeNode rootRight = root.right;
        while (rootRight.left != null) {
            pre = rootRight;
            rootRight = rootRight.left;
        }
        // 节点的值进行交换
        int tmpVal = rootRight.val;
        rootRight.val = root.val;
        root.val = tmpVal;
        // 中序遍历的第一个节点肯定是没有左子树的,但是可能有右子树,将右子树连接到父节点上(相当于删除有一个子节点的节点)
        if (pre.left == rootRight) {
            pre.left = rootRight.right;
        }else {
            pre.right = rootRight.right;
        }
        // 第二种方式
        // 寻找中序遍历的前一个节点,也就是左子树进行中序遍历的最后一个节点,左子树的最右节点
//        pre = root;
//        TreeNode rootLeft = root.left;
//        while (rootLeft.right != null){
//            pre = rootLeft;
//            rootLeft = rootLeft.right;
//        }
//
//        int tmpVal = rootLeft.val;
//        rootLeft.val = root.val;
//        root.val = tmpVal;
//
//        // 中序遍历的最后一个节点肯定是没有右子树的,但是可能有左子树,将左子树连接到父节点上(相当于删除有一个子节点的节点)
//        if (pre.left == rootLeft) {
//            pre.left = rootLeft.left;
//        }else {
//            pre.right = rootLeft.left;
//        }
        return tmp;
    }

到此这篇关于Java实现二叉搜索树的插入、删除的文章就介绍到这了,更多相关Java二叉搜索树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java基础之二叉搜索树的基本操作

    一.二叉搜索树插入元素 /** * user:ypc: * date:2021-05-18; * time: 15:09; */ class Node { int val; Node left; Node right; Node(int val) { this.val = val; } } public void insert(int key) { Node node = new Node(key); if (this.root == null) { root = node; } Node cu

  • Java底层基于二叉搜索树实现集合和映射/集合Set功能详解

    本文实例讲述了Java底层基于二叉搜索树实现集合和映射功能.分享给大家供大家参考,具体如下: 前言:在第5章的系列学习中,已经实现了关于二叉搜索树的相关操作,详情查看第5章即可.在本节中着重学习使用底层是我们已经封装好的二叉搜索树相关操作来实现一个基本的集合(set)这种数据结构. 集合set的特性: 集合Set存储的元素是无序的.不可重复的.为了能达到这种特性就需要寻找可以作为支撑的底层数据结构. 这里选用之前自己实现的二叉搜索树,这是由于该二叉树是不能盛放重复元素的.因此我们可以使用二叉搜索

  • Java创建二叉搜索树,实现搜索,插入,删除的操作实例

    Java实现的二叉搜索树,并实现对该树的搜索,插入,删除操作(合并删除,复制删除) 首先我们要有一个编码的思路,大致如下: 1.查找:根据二叉搜索树的数据特点,我们可以根据节点的值得比较来实现查找,查找值大于当前节点时向右走,反之向左走! 2.插入:我们应该知道,插入的全部都是叶子节点,所以我们就需要找到要进行插入的叶子节点的位置,插入的思路与查找的思路一致. 3.删除: 1)合并删除:一般来说会遇到以下几种情况,被删节点有左子树没右子树,此时要让当前节点的父节点指向当前节点的左子树:当被删节点

  • 利用java实现二叉搜索树

    二叉搜索树的定义 它是一颗二叉树 任一节点的左子树上的所有节点的值一定小于该节点的值 任一节点的右子树上的所有节点的值一定大于该节点的值 特点: 二叉搜索树的中序遍历结果是有序的(升序)! 实现一颗二叉搜索树 实现二叉搜索树,将实现插入,删除,查找三个方面 二叉搜索树的节点是不可以进行修改的,如果修改,则可能会导致搜索树的错误 二叉搜索树的定义类 二叉搜索树的节点类 -- class Node 二叉搜索树的属性:要找到一颗二叉搜索树只需要知道这颗树的根节点. public class BST {

  • Java 求解如何把二叉搜索树转换为累加树

    一.题目 给出二叉搜索树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和. 提醒一下,二叉搜索树满足下列约束条件: 节点的左子树仅包含键 小于 节点键的节点. 节点的右子树仅包含键 大于 节点键的节点. 左右子树也必须是二叉搜索树. 二.题解 观察示例图发现,树的遍历顺序为右,中,左的顺序,每个节点的值,是按照这个顺序累加的状态 由于是需要累加,所以需要pre指针记录当前遍历节点

  • Java 实现二叉搜索树的查找、插入、删除、遍历

    由于最近想要阅读下JDK1.8 中HashMap的具体实现,但是由于HashMap的实现中用到了红黑树,所以我觉得有必要先复习下红黑树的相关知识,所以写下这篇随笔备忘,有不对的地方请指出- 学习红黑树,我觉得有必要从二叉搜索树开始学起,本篇随笔就主要介绍Java实现二叉搜索树的查找.插入.删除.遍历等内容. 二叉搜索树需满足以下四个条件: 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值: 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值: 任意节点的左.右子

  • Java实现二叉搜索树的插入、删除功能

    二叉树的结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = val; } } 中序遍历 中序遍历:从根节点开始遍历,遍历顺序是:左子树->当前节点->右子树,在中序遍历中,对每个节点来说: 只有当它的左子树都被遍历过了(或者没有左子树),它才会被遍历到.在遍历右子树之前,一定会先遍历当前节点. 中序遍历得到的第一个节点是没

  • java实现 二叉搜索树功能

    一.概念 二叉搜索树也成二叉排序树,它有这么一个特点,某个节点,若其有两个子节点,则一定满足,左子节点值一定小于该节点值,右子节点值一定大于该节点值,对于非基本类型的比较,可以实现Comparator接口,在本文中为了方便,采用了int类型数据进行操作. 要想实现一颗二叉树,肯定得从它的增加说起,只有把树构建出来了,才能使用其他操作. 二.二叉搜索树构建 谈起二叉树的增加,肯定先得构建一个表示节点的类,该节点的类,有这么几个属性,节点的值,节点的父节点.左节点.右节点这四个属性,代码如下 sta

  • java基础二叉搜索树图文详解

    目录 概念 直接实践 准备工作:定义一个树节点的类,和二叉搜索树的类. 搜索二叉树的查找功能 搜索二叉树的插入操作 搜索二叉树删除节点的操作-难点 性能分析 总程序-模拟实现二叉搜索树 和java类集的关系 总结 概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:1.若它的左子树不为空,则左子树上所有节点的值都小于根结点的值.2.若它的右子树不为空,则右子树上所有节点的值都大于根结点的值.3.它的左右子树也分别为二叉搜索树 直接实践 准备工作:定义一个树节点的类,和二

  • 二叉搜索树的插入与删除(详细解析)

    题目:创建一个类,类中的数据成员时一棵二叉搜索树,对外提供的接口有添加结点和删除结点这两种方法.用户不关注二叉树的情况.要求我们给出这个类的结构以及实现类中的方法. 思路添加结点:添加结点其实很容易,我们只需要找到结点所行对应的位置就可以了,而且没有要求是平衡的二叉搜索树,因此每次添加结点都是在叶子结点上操作,不需要修改二叉搜索树整体的结构.要找出添加节点在二叉搜索树中的位置,可以用一个循环解决.判断插入结点与当前头结点的大小,如果大于头结点则继续搜索右子树,如果小于头结点则继续搜索左子树.直到

  • C++深入细致探究二叉搜索树

    目录 1.二叉搜索树的概念 2.二叉搜索树的操作 二叉搜索树的查找 二叉搜索树的插入 二叉搜索树的删除 3.二叉搜索树的实现 4.二叉搜索树的性能分析 1.二叉搜索树的概念  二叉搜索树又称二叉排序树,它可以是一颗空树,亦可以是一颗具有如下性质的二叉树:   ①若根节点的左子树不为空,则左子树上的所有节点的值域都小于根节点的值   ②若根节点的右子树不为空,则右子树上的所有节点的值域都大于根节点的值   ③根节点的左右子树分别也是一颗二叉搜索树 例如下面的这棵二叉树就是一棵二叉搜索树: 注意:判

  • C++数据结构之二叉搜索树的实现详解

    目录 前言 介绍 实现 节点的实现 二叉搜索树的查找 二叉搜索树的插入 二叉搜索树的删除 总结 前言 今天我们来学一个新的数据结构:二叉搜索树. 介绍 二叉搜索树也称作二叉排序树,它具有以下性质: 非空左子树的所有键值小于其根节点的键值 非空右子树的所有键值大于其根节点的键值 左,右子树都是二叉搜索树 那么我先画一个二叉搜索树给大家看看,是不是真的满足上面的性质. 我们就以根节点6为例子来看,我们会发现比6小的都在6的左边,而比6大的都在6的右边.对于6的左右子树来说,所有的节点都遵循这个规则.

  • C++简单实现与分析二叉搜索树流程

    目录 二叉搜索树 二叉搜索树的重要操作 二叉搜索树实现(key模型) 二叉搜索树的应用 二叉搜索树的实现(key/value模型) 二叉搜索树 二叉搜索树又被称为二叉排序树.它可以是一个空树,如果不是空树则满足下列性质: 1.如果它的左子树不为空,那么左子树上的所有节点都小于根. 2.如果它的右子树不为空,那么右子树上的所有节点都大于根 3.它的左子树.右子树也是二叉搜索树. 二叉搜索树的重要操作 二叉搜索树的插入 1.如果树为空,则直接插入 2.如果树不为空,则找到对应的位置插入. 查找办法:

随机推荐