二分搜索树(校招数据结构最低要求版)Java

这篇具有很好参考价值的文章主要介绍了二分搜索树(校招数据结构最低要求版)Java。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二分搜索树(Binary Search Tree,BST)是一种常见的数据结构,它能够高效地存储和查找数据。它的特点是每个节点都包含一个值,并且每个节点的左子树的值都小于节点的值,右子树的值都大于节点的值。

查找

通过这种有序的排列方式,我们可以在二分搜索树中进行高效的查找操作。想象一下,如果我们要查找一个特定的值,我们可以从根节点开始比较它与当前节点的值的大小关系。如果它比当前节点的值小,我们就去左子树中继续查找;如果它比当前节点的值大,我们就去右子树中查找。通过不断地比较和移动,我们最终要么找到了目标值,要么确定它不在树中。

插入

除了查找,二分搜索树还支持插入操作。当我们要插入一个新的值时

我们从根节点开始,比较新值和当前节点的大小关系。

如果它比当前节点的值小,我们就往左子树插入;

如果它比当前节点的值大,我们就往右子树插入。

我们不断地比较和移动,直到找到一个合适的位置,然后将新值插入为一个新的叶子节点。

删除

删除操作稍微复杂一些,因为我们要保持二分搜索树的有序性质。当我们要删除一个节点时,有三种可能的情况需要考虑:

  1. 如果待删除节点没有子节点,我们可以直接将其删除,不会破坏树的有序性。

  2. 如果待删除节点只有一个子节点,我们可以将子节点提升到待删除节点的位置上,同样不会破坏有序性。

  3. 如果待删除节点有两个子节点,我们需要找到它的后继节点(比待删除节点大的最小节点)或前驱节点(比待删除节点小的最大节点)来替代它。我们可以选择将后继节点提升到待删除节点的位置上,或者将前驱节点提升到待删除节点的位置上,然后删除后继或前驱节点。

但是二叉树的删除相对校招并不重要,而且代码过于复杂,所以我们这里就不再细讲,这里只是为了保证知识完整性罗列一下。

前中后序遍历和层序遍历

  1. 前序遍历:对于每个节点,先访问它自己,然后访问它的左子树,最后访问它的右子树。(根左右)

  2. 中序遍历:对于每个节点,先访问它的左子树,然后访问它自己,最后访问它的右子树。(左根右)

  3. 后序遍历:对于每个节点,先访问它的左子树,然后访问它的右子树,最后访问它自己。(左右根)

  4. 层序遍历:从根节点开始,先访问根节点,然后按照从左到右的顺序依次访问每一层的节点。

这些遍历方式各有特点,适用于不同的应用场景。

前序遍历可以用于复制整个树的结构,

中序遍历可以得到一个有序的节点值序列,

后序遍历常用于释放二叉树的内存,

而层序遍历可以逐层打印树的结构。

二分搜索树的特点在于每个节点的左子树的值都小于节点的值,右子树的值都大于节点的值。这种有序性质使得二分搜索树成为了很多应用中的首选数据结构之一。

 

代码实现:文章来源地址https://www.toymoban.com/news/detail-496798.html

package com.Search;
​
import java.util.LinkedList;
import java.util.Queue;
​
/**
 * @Author: 翰林猿
 * @Description: 二分搜索树
 **/
public class BSearchTree<E extends Comparable<E>> {
​
    private class Node {
        public E e;
        public Node left, right;
​
        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }
​
    private int size;   //节点数量
    private Node root;  //根节点
​
    public BSearchTree() {
        size = 0;
        root = null;
    }
​
    public int getSize() {
        return size;
    }
​
    public boolean isEmpty() {
        return size == 0;
    }
​
    /**
     * @Description: 插入
     **/
    public void add(E e) {
        root = add(root, e);
    }
​
    //向以node为根的树插入e元素,返回插入新节点之后的根。
    private Node add(Node node, E e) {
        if (node == null) {                 //如果没有该元素,直接返回一个新元素
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0)        //如果小于当前根元素,就往左边递归,
            node.left = add(node.left, e);  //传入的参数就是左边的子节点(意思就是说,以左节点作为左边的树的树根进行判断是否为空)
        else if (e.compareTo(node.e) > 0)   //如果大于当前根元素,就往右边递归
            node.right = add(node.right, e);
        return node;
    }
    /**
     * @Description: 查询
     **/
    public boolean contains(E e) {
        return contains(root, e);
    }
    private boolean contains(Node node, E e) {
        if (node == null)
            return false;
        if (e.compareTo(node.e) == 0)
            return true;
        else if (e.compareTo(node.e) > 0)   //如果查找的节点大于当前节点,递归去右子树找
            return contains(node.right, e);
        else  //e.compareTo(node.e) > 0       //如果查找的节点小于当前节点,递归去左子树找
            return contains(node.left, e);
    }
​
    /**
     * @Description: 前序遍历,根左右
     **/
    public void preOrder() {
        preOrder(root);
    }
    private void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.e + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    /**
     * @Description: 中序遍历,左根右
     **/
    public void inOrder() {
        inOrder(root);
    }
​
    private void inOrder(Node node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.e + " ");
            inOrder(node.right);
        }
    }
    /**
     * @Description: 后序遍历,左右根
     **/
    public void postOrder() {
        postOrder(root);
    }
​
    private void postOrder(Node node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.e + " ");
        }
    }
    /**
     * @Description: 层序遍历,广度优先遍历
     * 1.将节点入队,进入循环
     * 2.取出一个节点并打印,并将其左右子节点(如果存在)入队。
     * 3.重复直到队列为空
     **/
    public void levelOrder() {
        if (root == null) {
            return;
        }
​
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
​
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.e + " ");
​
            if (node.left != null) {
                queue.offer(node.left);
            }
​
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
​
​
    /**
     * @Description: 测试用例
     *
     *             7
     *           /   \
     *          4     9
     *         / \   / \
     *        2   5 8   10
     *       / \          \
     *      1   3          11
     **/
    public static void main(String[] args) {
        BSearchTree<Integer> bst = new BSearchTree<>();
        bst.add(7);
        bst.add(4);
        bst.add(9);
        bst.add(2);
        bst.add(5);
        bst.add(8);
        bst.add(10);
        bst.add(1);
        bst.add(3);
        bst.add(11);
        System.out.println("二叉搜索树节点数量: " + bst.getSize());
​
        System.out.println("是否存在5号节点: " + bst.contains(5));
        System.out.println("是否存在100号节点: " + bst.contains(100));
​
        System.out.print("前序遍历: ");
        bst.preOrder();
        System.out.println();
​
        System.out.print("中序遍历: ");
        bst.inOrder();
        System.out.println();
​
        System.out.print("后序遍历: ");
        bst.postOrder();
        System.out.println();
​
        System.out.print("层序遍历: ");
        bst.levelOrder();
    }
}

到了这里,关于二分搜索树(校招数据结构最低要求版)Java的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构算法--1 顺序查找二分查找

    顺序查找时间复杂度为O(n) 我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值 也可以通过列表长度依次遍历: 但是二分查找时间复杂度为O(logn):

    2024年02月12日
    浏览(52)
  • 【手撕数据结构】二分查找(好多细节)

    🌈键盘敲烂,年薪30万🌈 目录 普通版本的二分查找: right只负责控制边界(少了两次比较): 时间复杂度更稳定的版本: BSLeftmost: BSRightmost:   🏸细节1:循环判定条件是left = right ⭐细节2:mid = (left + right ) 1 原因见代码注释 改动1:while条件是left right 改动2:right = nums.len

    2024年02月05日
    浏览(46)
  • 【数据结构与算法】python实现二分查找

    二分查找 又称折半查找,它是一种效率较高的查找方法 原理:首先,假设表中元素是按升序排列,将表中间位置记录的与查找比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的大于查找,则

    2024年02月05日
    浏览(40)
  • 数据结构和算法之二分法查找

    二分法查找,也称作 二分查找 或 折半查找 ,是一种在有序数组中快速查找特定元素的算法。它采用分治法思想,通过将问题划分为规模更小的子问题,并且通过对子问题的查找来解决原问题。 二分法查找的思路是不断地将数组一分为二,然后判断目标值在哪一部分,进而

    2024年02月09日
    浏览(45)
  • Java数据结构与算法:查找算法之二分查找

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,欢迎回到本专栏。在这个冰冷的季节里,我们将一同探讨Java中一种高效的查找算法——二分查找。让我们点燃知识的火花,一同解锁这个查找奇迹的秘密! 二分查找简介 二分查找,也称为折半查找,

    2024年01月21日
    浏览(45)
  • 浙大数据结构第一周01-复杂度3 二分查找

    本题要求实现二分查找算法。 函数接口定义: 其中 List 结构定义如下: L 是用户传入的一个线性表,其中 ElementType 元素可以通过、==、进行比较,并且题目保证传入的数据是递增有序的。函数 BinarySearch 要查找 X 在 Data 中的位置,即数组下标(注意:元素从下标1开始存储)

    2024年02月12日
    浏览(46)
  • 数据结构-查找(顺序查找与二分查找的讲解与代码实现)

    顺序查找概念:从表的另一端开始,一次将记录的和给定值进行比较,若某个记录的和给定的值相等,则查找成功,反之则查找失败。 ASL:平均查找长度 pi查找概率,ci查找次数 eg:序列1,2,3 查找1的次数为1概率为1/3,2为两次概率1/3,3的次数为3概率1/3  将12

    2024年02月06日
    浏览(68)
  • 数据结构 | 搜索和排序——搜索

    目录 一、顺序搜索 二、分析顺序搜索算法 三、二分搜索 四、分析二分搜索算法 五、散列 5.1 散列函数 5.2 处理冲突 5.3 实现映射抽象数据类型 搜索是指从元素集合中找到某个特定元素的算法过程。搜索过程通常返回True或False,分别表示元素是否存在。有时,可以修改搜索过

    2024年02月14日
    浏览(37)
  • 【数据结构】6.搜索树

    二叉搜索树:  一棵非空的二叉搜索树每个元素都有一个,并且任意两个元素的不同,所有都是唯一的 根节点的左子树小于根节点的 根节点的右子树大于根节点的 左右子树也是二叉搜索树 索引二叉搜索树: 源于普通的二叉搜索树,在每个

    2024年02月08日
    浏览(34)
  • 数据结构——二叉搜索树

    本章代码:二叉搜索树 二叉搜索树又叫二叉排序树,它具有以下性质: 若左子树不为空,则左子树上所有结点的值都小于根结点的值 若右子树不为空,则右子树上所有结点的值都大于根结点的值 它的左右子树也分别为二叉搜索树 这个结构的时间复杂度为一般人会以为是 O(

    2024年02月12日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包