首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

手撸二叉树——二叉查找树

编程知识
2024年10月13日 09:22

二叉树是数据结构中非常重要的一种数据结构,它是的一种,但是每个节点的子节点不能多余两个,可以是0,1,2个子节点,0个子节点代表没有子节点。常见的二叉树结构如下图所示:

每个节点的子节点不多于2个,其中3,4,5没有子节点,2有一个子节点,0,1都有两个子节点。

基础概念

根节点:树的其实节点,没有父节点。

叶子节点:没有子节点的节点叫做叶子节点。

节点深度:从根节点到该节点的距离叫做深度,如上图:节点3的深度是2,节点1的深度是1。

节点高度:该节点到距离最长的叶子节点的距离。

二叉查找树

二叉树最重要的一个应用是在查询方面的应用,很多的索引结构都是二叉查找树,还有向HashMap里也使用到了红黑树,红黑树也是二叉查找树的一种。二叉查找树的一个重要性质,就是任何一个节点,它的左子树中的节点都小于该节点,它的右子树中的节点都大于该节点。最开始我们的例图它不是一棵二叉查找树,它不符合我们刚才说的性质。我们再看看下面的例图:

这是一棵二叉查找树,它的任何一个节点的子节点都小于该节点,右子树的节点都大于该节点。这样我们在查找数据的时候,就可以从根节点开始查找,如果查找的值小于该节点,就去左子树中查找,如果大于该节点,就去右子树中查找,如果等于,那就不用说了,直接返回就可以了。这种可以大大提升我们的查找效率,它的时间复杂度是O(logN)。

手撸二叉查找树

首先我们要抽象出节点类,每个节点可以有左子节点,和右子节点,当然节点要存储一个值,这个值的类型我们不做限制,可以是数字型,也可以是字符串,还可以是自己定义的类,但是这里要加一个前提条件,就是这个值是可比较的,因为两个节点比较后才能确定位置,所以节点值的类型要实现Comparable接口。好了,满足上面的条件,我们就可以抽象出二叉树节点的类了,如下:

public class BinaryNode<T extends Comparable<T>> {
    //节点数据
    @Setter@Getter
    private T element;
    //左子节点
    @Setter@Getter
    private BinaryNode<T> left;
    //右子节点
    @Setter@Getter
    private BinaryNode<T> right;

    //构造函数
    public BinaryNode(T element) {
        this(element,null,null);
    }
    //构造函数
    public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
        if (element == null) {
            throw new RuntimeException("二叉树节点元素不能为空");
        }
        this.element = element;
        this.left = left;
        this.right = right;
    }
}

我们定义二叉树节点的类为BinaryNode,我们注意一下后面的泛型,它要实现Comparable接口。然后我们定义节点数据element,左子节点left,和右子节点right,并且使用@Setter@Getter注解实现其set和get方法。接下来就是定义两个构造方法,一个是只传入节点元素的,另一个是传入节点元素和左右子树的。节点的元素是不能为空的,如果是空则抛出异常。

然后,我们再定义二叉查找树类,类中包括一些二叉查找树的基本操作方法,这些基本的操作方法我们后面讲,先看定义的基本元素,如下:

public class BinarySearchTree<T extends Comparable<T>> {
    //根节点
    private BinaryNode<T> root;

    public BinarySearchTree() {
        this.root = null;
    }
    
    //将树变为空树
    public void makeEmpty() {
        this.root = null;
    }

    //判断树是否为空
    public boolean isEmpty() {
        return this.root == null;
    }
}

类的名字定义为:BinarySearchTree,同样我们注意一下这里的泛型,它和BinaryNode的泛型是一样的,因为这个类型我们传递给BinaryNode。类中定义了树的根节点root,以及构造方法,构造方法只是定义了一棵空树,根节点为空。然后是两个比较基础的树的操作方法makeEmptyisEmpty,将树变为空树和判断树是否为空。

  1. 现在我们要编写一些树的操作方法了,首先我们要编写的就是contains方法,它会判断树中是否包含某个元素,比如上面例图中,我们判断树中是否包含3这个元素。具体实现如下:
/**
 * 二叉树是否包含某个元素
 *
 * @param element 检查的元素
 * @return true or false
 */
public boolean contains(T element) {
    return contains(root, element);
}

/**
 * 二叉树是否包含某个元素
 *
 * @param tree    整棵树或左右子树
 * @param element 检查的元素
 * @return true or false
 */
private boolean contains(BinaryNode<T> tree, T element) {
    if (tree == null) {
        return false;
    }

    int compareResult = element.compareTo(tree.getElement());

    if (compareResult > 0) {
        return contains(tree.getRight(), element);
    }
    if (compareResult < 0) {
        return contains(tree.getLeft(), element);
    }
    return true;
}

这里我们定义了两个contains方法,第一个contains方法调用第二个contains方法,第二个contains方法是私有的,外部不能访问。在调用第二个contains方法时,我们将root传进去,也就是整棵树传入去查找。在第二个contains方法中,我们先判断树是否为空,如果为空,肯定不会包含我们要查找的元素,则直接返回false。然后我们用查找的元素和当前节点的元素作比较,这里我们使用compareTo方法,它是Comparable接口中定义好的方法,这也是我们定义泛型时要实现Comparable接口的原因了。比较结果大于0,说明查找的值大于当前节点值,我们递归调用contains方法,将右子树和查找的值传入;比较结果小于0,说明查找的值小于当前节点值,我们同样递归调用contains方法,将左子树和查找的值传入进行查找。最后如果比较结果等于0,说明查找的值和当前节点值是一样的,我们返回true就可以了。

contains方法算是一个开胃小菜,其中用到了递归,这也让我们对二叉树的编写方法有了一个初步的了解。

  1. 接下来我们要编写的是findMinfindMax方法,分别是找出树中最小值和最大值的方法。由于我们的树是一棵二叉查找树,左子树的值要小于当前节点,右子树的值大于当前节点,所以,最左侧节点的值就是最小值,最右侧的值则是最大值。我们用代码实现一下,
/**
 * 找出二叉树的最小元素
 *
 * @return
 */
public T findMin() {
    if (isEmpty()) throw new RuntimeException("二叉树为空");
    return findMin(root);
}

private T findMin(BinaryNode<T> tree) {
    if (tree.getLeft() != null) {
        return findMin(tree.getLeft());
    }
    return tree.getElement();
}

/**
 * 找出二叉树的最大元素
 *
 * @return
 */
public T findMax() {
    if (isEmpty()) throw new RuntimeException("二叉树为空");
    return findMax(root);
}

private T findMax(BinaryNode<T> tree) {
    while (tree.getRight() != null) {
        tree = tree.getRight();
    }
    return tree.getElement();
}

我们先来看findMin方法,先判断树是否为空,空树没有最小值,也没有最大值,所以我们这里抛出异常。然后我们将整棵树传入第二个findMin方法,在第二个findMin方法中,我们一直去寻找左子节点,如果左子节点不为空,我们就递归的再去寻找,直到节点的左子节点为空,那么当前节点就是整棵树的最左节点,那么它的值就是最小的,我们返回就可以了。

我们再来看findMax方法,和findMin方法一样,先判断树是否为空,为空则抛出异常。我们要重点看的是第二个findMax方法,这个方法中,我们没有使用递归去寻找最右侧的节点,而是使用了一个while循环,去找到最右侧的节点。这里我们使用了两种不同的方法实现了findMinfindMax,一个使用了递归,另一个使用了while循环,其实这两种方式也是互通的,能用递归的方法也可以用while循环去实现,反之亦然。

  1. 接下来我们再来看一下二叉查找树的一个非常重要的方法,那就是insert插入方法了。当我们向二叉查找树中添加一个节点时,要和当前节点做比较,如果小于当前节点值,则在左侧插入,如果大于则在右侧插入,这里我们不讨论等于的情况。具体代码如下:
/**
 * 插入元素
 *
 * @param element
 */
public void insert(T element) {
    if (root == null) {
        root = new BinaryNode<>(element);
        return;
    }
    insert(root, element);
}

private void insert(BinaryNode<T> tree, T element) {
    int compareResult = element.compareTo(tree.getElement());
    if (compareResult > 0) {
        if (tree.getRight() == null) {
            tree.setRight(new BinaryNode<>(element));
        } else {
            insert(tree.getRight(), element);
        }
    }

    if (compareResult < 0) {
        if (tree.getLeft() == null) {
            tree.setLeft(new BinaryNode<>(element));
        } else {
            insert(tree.getLeft(), element);
        }
    }
}

在插入节点的过程中,我们先判断根节点是否为空,如果为空,说明是一棵空树,我们直接将插入元素给到根节点就可以了。如果根节点不为空,我们进入到第二个insert方法,在第二个insert方法中,我们先将插入的值和当前节点做比较,比较结果如果大于0,说明插入的值比当前节点大,所以我们要在右侧插入,如果当前节点的右子节点为空,我们直接插入就可以了;如果右子节点不为空,还要和右子节点作比较,这里我们用递归的方法实现,逻辑比较清晰。同理,如果比较结果小于0,我们对左侧节点做操作就可以了,这里不再赘述。

  1. 上面我们做了节点的插入,最后再来看看节点的删除remove。要删除一个节点,首先我们要找到这个节点,找到这个节点后,要分情况对这个节点进行处理,如下:
  • 删除节点没有子节点:我们直接将该节点删除,也就是将节点置为null;
  • 删除节点只有左子节点或右子节点:这种只有一个子节点的情况,我们直接将要删除的节点改为它的唯一的子节点就可以了。这里等于是用子节点覆盖掉当前节点;
  • 删除节点有两个子节点:这种是最复杂的情况,要解决这个问题,我们还是要利用二叉查找树的特性,就是当前节点的左子树的值都比当前节点小,右子树的值都比当前节点大。那么我们把当前节点删除后,用哪个节点代替当前节点呢?这里我们可以在左子树中找到最大的值,或者从右子树中找到最小的值,代替当前要删除的节点。这样替换后,还是可以保证左子树的值比当前值小,右子树的值比当前值大。然后我们再把替换的值,也就是左子树中的最大值,或者右子树中的最小值,在左或右子树中删掉就可以了。这一段逻辑比较绕,小伙伴们可以多读几遍,理解一下。具体实现如下:
/**
 * 删除元素
 * @param element
 */
public void remove(T element) {
    remove(root, element);
}

private void remove(BinaryNode<T> tree, T element) {
    if (tree == null) {
        return;
    }
    int compareResult = element.compareTo(tree.getElement());
    if (compareResult > 0) {
        remove(tree.getRight(), element);
        return;
    }
    if (compareResult < 0) {
        remove(tree.getLeft(), element);
        return;
    }
    if (tree.getLeft() != null && tree.getRight() != null) {
        tree.setElement(findMin(tree.getRight()));
        remove(tree.getRight(), tree.getElement());
    } else {
        tree = tree.getLeft() != null ? tree.getLeft() : tree.getRight();
    }
}

第一个remove方法不说了,我们重点看第二个。方法进来后,节点是否为空,为空则说明是空树,或者要删除的节点没有找到,那么直接返回就可以了。然后再用删除的元素和当前节点作比较,如果大于0,我们用递归方法在右子树中继续执行删除方法。同理如果小于0,用左子树递归。再下面就是等于0的情况,也就是找到了要删除的节点。我们先处理最复杂的情况,就是删除节点左右子节点都存在的情况,我们使用上面的逻辑,使用右子树中最小的节点覆盖当前节点,然后再在右子树中,将这个值删掉,我们也是递归的调用了remove方法。当然这里也可以使用左子树中的最大值,小伙伴们自己实现吧。最后就是处理没有子节点和只有一个子节点的情况,这两种情况在代码中可以合并,如果左子节点不为空,就用左子节点覆盖掉当前节点,否则使用右子节点覆盖。如果右子节点也为空,也就是没有子节点,那么当前节点也就变为空了。

问题

到这里,二叉查找树的基本的操作方法就编写完了。这里引申一个问题,如果我们顺序的向一棵树中插入1,2,3,4,5,这个树会是什么形状?这个也不难想象,如下:

这和链表没有什么区别了呀,查找的性能和链表一样了,并没有提升。这就引出了下一篇的内容:平衡二叉树,小伙伴们,敬请期待~~

From:https://www.cnblogs.com/boboooo/p/18461934
本文地址: http://www.shuzixingkong.net/article/2495
0评论
提交 加载更多评论
其他文章 推荐一款支持Vue3的管理系统模版:Vue-Vben-Admin
近年来,随着前端技术的飞速发展,各类后台管理系统框架层出不穷。Vue 作为热门的前端框架,也有许多优秀的后台模板涌现。而 Vue-Vben-Admin,凭借其高效、灵活的架构设计和完善的功能体系,成为了许多前端开发者的不二选择。其Github Star达到了24K之多,可见其受欢迎程度。本文将详细介
推荐一款支持Vue3的管理系统模版:Vue-Vben-Admin 推荐一款支持Vue3的管理系统模版:Vue-Vben-Admin
封神台 SQL注入 靶场 (猫舍)手动注入
封神台 SQL注入 靶场 (猫舍)手动注入 靶场地址 http://pu2lh35s.ia.aqlab.cn/?id=1 使用脚本 可以直接使用sqlmap脚本 直接 对这个地址进行测试 不过这样实在是太没意思了 这里使用的是 sqlmap 二次开发的 sqlmapplus 脚本 sqlmap 也是
封神台 SQL注入 靶场 (猫舍)手动注入 封神台 SQL注入 靶场 (猫舍)手动注入 封神台 SQL注入 靶场 (猫舍)手动注入
mongo对文档中数组进行过滤的三种方法
想要实现数组的过滤有三种方法,包括: 1. 聚合查询 使用`$unwind`将`travel`数组打散,获取结果集后用`$match`筛选符合条件的数据,最后使用`$group`进行聚合获取最终结果集 2. 聚合查询 使用`$match`过滤符合条件的根文档结果集,然后使用`$projec`t返回
mongo对文档中数组进行过滤的三种方法
Nuxt.js 应用中的 ready 事件钩子详解
title: Nuxt.js 应用中的 ready 事件钩子详解 date: 2024/10/12 updated: 2024/10/12 author: cmdragon excerpt: ready 钩子是 Nuxt.js 中一个重要的生命周期事件,它在 Nuxt 实例初始化完成后被调用。当 N
Nuxt.js 应用中的 ready 事件钩子详解 Nuxt.js 应用中的 ready 事件钩子详解
C#轻松实现Modbus通信
1、前言 大家好!我是付工。前面给大家介绍了一系列关于RS485与Modbus的知识。 终于有人把RS485说清楚了终于有人把Modbus说明白了通透!终于把ModbusRTU弄明白了这样看来,ModbusTCP协议太简单了今天跟大家聊聊关于C#如何实现Modbus通信。 2、开源通信库 通信库是对
C#轻松实现Modbus通信 C#轻松实现Modbus通信
Nuxt.js 应用中的 close 事件钩子详解
title: Nuxt.js 应用中的 close 事件钩子详解 date: 2024/10/13 updated: 2024/10/13 author: cmdragon excerpt: close 钩子是 Nuxt.js 中一个重要的生命周期事件,它在 Nuxt 实例正常关闭时被调用。当 Nu
Nuxt.js 应用中的 close 事件钩子详解 Nuxt.js 应用中的 close 事件钩子详解
OpenAI官方开源多智能体框架「Swarm」,并不是我想要的多智能体框架
今天早上,OpenAI实施团队的 @shyamal在Github上开源了Swarm这个OpenAI官方的多智能体框架。不得不说,OpenAI官方下场,获得的社区影响就是不一样,在微信群、朋友圈里已经出现大量的解析文章。这个多智能体框架确实已经把多智能体的关键,说的很透彻了,Swarm 里面定义了两个
OpenAI官方开源多智能体框架「Swarm」,并不是我想要的多智能体框架 OpenAI官方开源多智能体框架「Swarm」,并不是我想要的多智能体框架 OpenAI官方开源多智能体框架「Swarm」,并不是我想要的多智能体框架
关于使用plsql操作oracle的一点小技巧和几个常用的查询语句
plsql是什么: 就是这个,专门操作oracle的一个工具,好用还免费。 创建一个测试表: create table Student( Id number not null, Name varchar(20), Age number, Grade number, Gender varchar(2)
关于使用plsql操作oracle的一点小技巧和几个常用的查询语句 关于使用plsql操作oracle的一点小技巧和几个常用的查询语句 关于使用plsql操作oracle的一点小技巧和几个常用的查询语句