首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

java二进制搜索树插入递归似乎总是返回空根

Java二进制搜索树(Binary Search Tree,简称BST)是一种常用的数据结构,它具有快速的插入、删除和搜索操作。在插入节点时,可以使用递归方法来实现。

递归插入节点的过程如下:

  1. 如果树为空,则将新节点作为根节点插入,并返回根节点。
  2. 如果新节点的值小于当前节点的值,则递归地将新节点插入当前节点的左子树中。
  3. 如果新节点的值大于当前节点的值,则递归地将新节点插入当前节点的右子树中。
  4. 返回插入后的根节点。

在实现递归插入时,需要注意以下几点:

  1. 确保每个节点都有左子树和右子树的引用,以便递归地插入新节点。
  2. 插入操作可能会改变树的结构,因此需要更新父节点的子树引用。

下面是一个示例代码,演示了如何使用递归插入节点到二进制搜索树中:

代码语言:txt
复制
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

class BinarySearchTree {
    private TreeNode root;

    public void insert(int val) {
        root = insertNode(root, val);
    }

    private TreeNode insertNode(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }

        if (val < node.val) {
            node.left = insertNode(node.left, val);
        } else if (val > node.val) {
            node.right = insertNode(node.right, val);
        }

        return node;
    }
}

public class Main {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(5);
        bst.insert(3);
        bst.insert(7);
        bst.insert(2);
        bst.insert(4);
        bst.insert(6);
        bst.insert(8);
    }
}

在上述代码中,我们创建了一个BinarySearchTree类,其中包含了insert方法用于插入节点。通过调用bst.insert()方法,我们可以向二进制搜索树中插入节点。

关于二进制搜索树的更多详细信息,你可以参考腾讯云的文档:二叉搜索树(Binary Search Tree)

请注意,本回答中没有提及具体的腾讯云产品,因为问题要求不涉及特定品牌商。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

Java常见的8种数据结构「建议收藏」

对于深度优先遍历算法而言,他可分为以下三种: (1)先序遍历二叉 (2)中序遍历二叉 (3)后序遍历二叉 如果L、D、R表示左子树、、右子树,习惯上总是先遍历左子树,后遍历右子树...,根据遍历节点的顺序不同,上面三种方法可以表示如下: DLR:先序遍历 LDR:中序遍历 LRD:后序遍历 查找 增加 时间复杂度O(logN) 删除算法复杂 二叉搜索缺点...红黑详细介绍 avl一定是平衡的 在插入和删除的时候需要扫描两遍,一次是向下寻找插入点,一次是向上平衡,效率不如红黑高,也不如红黑常用 哈希表 哈希算法:这类算法接受任意长度的二进制输入值...数组的最大特点就是查找容易,插入和删除困难;而链表正好相反,查找困难,而插入和删除容易。哈希表很完美地结合了两者的优点, Java 的 HashMap 在此基础上还加入了的优点。...; 堆总是一棵完全二叉

76230

看动画学算法之:二叉搜索BST

先上图: 搜索的基本步骤是: 从节点41出发,比较节点和搜索值的大小 如果搜索值小于节点值,那么递归搜索左侧 如果搜索值大于节点值,那么递归搜索右侧 如果节点匹配,则直接返回即可。...相应的java代码如下: //搜索方法,默认从节点搜索 public Node search(int data){ return search(root,data);...插入的逻辑是这样的: 从节点出发,比较节点数据和要插入的数据 如果要插入的数据小于节点数据,则递归左子树插入 如果要插入的数据大于节点数据,则递归右子树插入 如果节点为空,则插入当前数据作为节点...相应的java代码如下: // 插入新节点,从节点开始插入 public void insert(int data) { root = insert(root, data);...return node; } BST的删除 BST的删除要比插入复杂一点,因为插入总是插入到叶子节点,而删除可能删除的是非叶子节点。

43430

数据结构和算法

image 二进制搜索:二叉搜索(BST)是二叉。左子树包含其键小于节点键值的节点,而右子树包含其键大于或等于节点键值的节点。此外,两个子树也是二叉搜索。二叉搜索可以有效地检索数据。 ?...在该结构中,在一端插入新元件,从另一端移除现有元件。 ? image Max-Heap:堆是基于的数据结构,其中的所有节点都按特定顺序排列。最大堆是二叉。它是完整的。...在trie中,每个节点(节点除外)存储一个字符或一个数字。通过将trie从节点向下遍历到特定节点n,可以形成字符或数字的公共前缀,其也由特里结构的其他分支共享。 ?...image 搜索搜索是基于密钥查找内容。有线性搜索二进制搜索。 线性搜索:线性搜索是一种在列表中查找目标值的方法。它按顺序检查列表中每个元素的目标值,直到找到匹配项或者直到搜索完所有元素为止。...image 二进制搜索二进制搜索是一种有效的算法,用于从有序的项目列表中查找项目。它的工作原理是反复将列表中可能包含该项目的部分分成两半; 直到你将可能的位置缩小到一个。

2K40

文心一言 VS 讯飞星火 VS chatgpt (155)-- 算法导论12.3 2题

节点的节点数为1。 在构造二叉搜索的过程中,插入关键字的顺序将决定的结构。每次插入关键字时,都会从节点开始搜索,直到找到合适的位置。...由于在构造的过程中,我们总是节点开始搜索,因此插入关键字所检查的节点数目等于目标节点的高度加1。 根据二叉搜索的性质,目标节点的高度等于先前插入这个关键字所检查的节点数目加1。...然后,我们可以使用递归的方式来构造这棵,并在查找过程中记录检查过的结点数目。...因此,可以证明在这棵中查找关键字所检查过的结点数目等于先前插入这个关键字所检查的结点数目加1。 在这里插入图片描述 chatgpt: 首先,我们可以利用递归的方式来插入关键字到二叉搜索中。...可以看出,无论是在左子树还是右子树中进行递归搜索时,都满足“先前插入这个关键字所检查过的结点数目加 1”的规律。

18520

剑指offer | 面试题25:从上到下打印二叉

| 面试题8:旋转数组的最小数字 剑指offer | 面试题9:斐波那契数列 剑指offer | 面试题10:青蛙跳台阶问题 剑指offer | 面试题11:矩阵覆盖 剑指offer | 面试题12:二进制中...] 提示:节点总数 <= 1000 解题思路: 题目要求的二叉的 从上至下 打印(即按层打印),又称为二叉的 广度优先搜索(BFS)。...算法流程: 特例处理: 当节点为空,则直接返回空列表 [] ; 初始化: 打印结果列表 res = [] ,包含节点的队列 queue = [root] ; BFS 循环: 当队列 queue...*/ public int[] levelOrder(TreeNode root) { if (root == null) return new int[0];//空则返回空数组...res.length; i++) { res[i] = list.get(i); } return res; } /************ 递归

83330

文心一言 VS 讯飞星火 VS chatgpt (148)-- 算法导论12.2 3题

如果该节点有父节点,则直接返回父节点;如果该节点是节点,则返回nil。如果该节点没有左子节点,则递归查找右子树的前驱节点。如果该节点既没有左子节点也没有右子节点,则返回nil,表示没有前驱节点。...在实际的二叉搜索中,你需要根据的特性来调整算法的具体实现。如果你想要在不同的树结构中实现 TREE-PREDECESSOR 过程,那么你需要根据的具体定义来调整算法。...,并且有一个全局变量 root 指向节点。...它提供了一种实现TREE-PREDECESSOR过程的思路和结构,并通过递归或迭代方式在二叉搜索中查找给定节点的前驱节点。具体实现可能需要根据具体的数据结构和逻辑进行调整。...在这里插入图片描述 在这里插入图片描述 kimi: TREE-PREDECESSOR 是一个用于在二叉中查找给定节点的前驱节点的算法。

18020

【C++深度探索】二叉搜索的全面解析与高效实现

1.二叉搜索 二叉搜索(BST,Binary Search Tree)又称二叉排序,是一种特殊的二叉,它或者是一棵空,或者是具有以下性质的二叉: 若它的左子树不为空,则左子树上所有节点的值都小于节点的值...这个特性使得二叉搜索可以用来实现非常高效的查找、插入和删除操作。 2.二叉搜索的功能 二叉搜索是一种特殊的二叉,它具有以下功能: 插入节点:可以将一个新节点插入到二叉搜索中。...Insert()   插入新节点时我们首先需要借助节点的类来构建新节点,然后判断插入二叉搜索的位置,因为二叉的左子树的节点总是小于节点,右子树总是大于节点,所以不能随便插入,确定好插入位置后将新节点插入到二叉搜索中...,当root不为空并且还没有找到时就会一直查找,而当root为空并且还没有找到此时就可以返回空指针,表示当前二叉搜索不存在要查找的节点。...✨析构函数   析构函数也直接使用递归删除节点即可,但是注意要使用后序遍历,最后释放节点,如果先释放节点会找不到子节点,会报错。

8910

数据结构之-第二篇

1 package com.tree; 2 3 4 import java.util.*; 5 6 /** 7 * 1、二分搜索,二分搜索存储的内容支持泛型,但是不是支持所有的类型...100 // * 101 // * 整体上是,向以node为的二分搜索插入元素E,递归算法。...171 * 172 * 返回插入新节点后二叉搜索。 173 * 174 * 向以node为的二分搜索插入元素e,递归算法。...175 * 176 * 177 * 对于新的add递归函数,将向以node为的二分搜索插入元素e,并且返回在做完这个操作以后这个二分搜索节点,...相应的节点将他返回回去。 183 * 184 * 链表的递归插入和二分搜索的添加具有高度相似性的,在二分搜索中需要判断一下,是要插入到左子树还是右子树。

42510

二叉——700.二叉搜索中的搜索

1 题目描述 给定二叉搜索(BST)的节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为的子树。 如果节点不存在,则返回 null 。...1 <= val <= 10^7 4 思路 方法一:递归 二叉搜索满足如下性质: 左子树所有节点的元素值均小于的元素值; 右子树所有节点的元素值均大于的元素值。...据此可以得到如下算法: 若root为空则返回空节点; 若val = root.val,则返回root; 若val < root.val,递归左子树; 若val > root.val,递归右子树。...复杂度分析 时间复杂度:O(N),其中N是二叉搜索的节点数。最坏情况下二叉搜索是—条链,且要找的元素比链末尾的元素值还要小(大),这种情况下我们需要递归N次 空间复杂度:O(N)。...复杂度分析 时间复杂度:O(N),其中N是二叉搜索的节点数。最坏情况下二叉搜索是—条链,且要找的元素比链末尾的元素值还要小(大),这种情况下我们需要迭代Ⅳ次 空间复杂度:O(1)。

35220

数据结构:堆(Heap)

根据这一属性,那么最大堆总是将其中的最大值存放在节点。而对于最小堆,节点中的元素总是中的最小值。堆属性非常有用,因为堆常常被当做优先队列使用,因为可以快速地访问到“最重要”的元素。...堆和普通的区别 堆并不能取代二叉搜索,它们之间有相似之处也有一些不同。我们来看一下两者的主要差别: 节点的顺序。在二叉搜索中,左子节点必须比父节点小,右子节点必须必比父节点大。...二叉搜索必须是“平衡”的情况下,其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据,或者使用 AVL 或者红黑,但是在堆中实际上不需要整棵都是有序的。...搜索。在二叉搜索会很快,但是在堆中搜索会很慢。在堆中搜索不是第一优先级,因为使用堆的目的是将最大(或者最小)的节点放在最前面,从而快速的进行相关插入、删除操作。...删除根节点 我们将这个中的 (10) 删除: ? 现在顶部有一个空的节点,怎么处理? ? 当插入节点的时候,我们将新的值给数组的尾部。

1.5K11

C++进阶:二叉搜索介绍、模拟实现(递归迭代两版本)及其应用

查找、插入和删除操作的平均时间复杂度为O(log N),其中N为中节点的数量 1.3 二叉搜索的操作 插入操作 为空,则直接新增节点,赋值给root指针 不空,按二叉搜索性质查找插入位置...如果二叉搜索不为空,则从节点开始,沿着的路径向下搜索应该插入新节点的位置。...(也是起到链接的作用) 在拷贝构造函数中,调用 copy 函数复制传入二叉搜索节点,从而完成整棵的复制。...操作: 插入:将新的关键码插入到二叉搜索中的合适位置,保持的有序性。 搜索:通过比较关键码,可以快速判断给定的值是否在中存在。...操作: 插入插入新的键值对到二叉搜索中,保持的有序性。 搜索:通过比较关键码,可以快速查找对应的值。

17110

用javascript分类刷leetcode22.字典(图文视频讲解)

目录Trie,即字典,又称前缀,是一种树形结构,典型应用是用于统计和排序大量的字符串(但不限于字符串),所以经常被搜索引擎用于文本词频统计。...请你实现 Trie 类:Trie() 初始化前缀对象。void insert(String word) 向前缀插入字符串 word 。...插入字符串:从字段节点开始,如果子节点存在,继续处理下一个字符,如果子节点不存在,则创建一个子节点到children的相应位置,沿着指针继续向后移动,处理下一个字符,以插入‘cad’为例查找前缀:...从节点开始,子节点存在,则沿着指针继续搜索下一个子节点,直到最后一个,如果搜索到了前缀所有字符,说明字典包含该前缀。...:将所有字符串插入trie中,递归寻找那个长度最大的单词复杂度:时间复杂度O(mn),m是字符串数组的长度,n是字符串最大长度。

55220

为实习准备的数据结构(4)-- 二叉

具体思路: 对于任意一颗而言,前序遍历的形式总是 [ 节点, 左子树的前序遍历结果, 右子树的前序遍历结果 ] 即节点总是前序遍历中的第一个节点。...具体思路: 对于任意一颗而言,后序遍历的形式总是 [ 左子树的前序遍历结果, 右子树的前序遍历结果,节点 ] 即节点总是后序遍历中的最后一个节点。...= NULL) q.push(front->right); } cout<<endl; } ----------------- 二叉搜索 所谓二叉搜索,可提供对数时间的元素插入和访问。...二叉搜索的节点放置规则是:任何节点的键值一定大于去其左子树中的每一个节点的键值,并小于其右子树的每一个节点的键值。 所以在二叉中找到最大值和最小值是很简单的,比较麻烦的是元素的插入和移除。...[在这里插入图片描述] 构造二叉搜索 现有序列:A = {61, 87, 59, 47, 35, 73, 51, 98, 37, 93}。

36410

【C++】二叉搜索

二叉搜索 一、二叉搜索概念 二叉搜索又称二叉排序,可以简写成 BST,它或者是一棵空,或者是具有以下性质的二叉: 若它的左子树不为空,则左子树上所有节点的值都小于节点的值 若它的右子树不为空...,则右子树上所有节点的值都大于节点的值 它的左右子树也分别为二叉搜索 如下就为一颗简单的二叉搜索: 二、二叉搜索操作 二叉搜索的查找 从开始比较,查找,比大则往右边走查找,比小则往左边走查找...二叉搜索插入 插入的具体过程如下: 为空,则直接新增节点,赋值给 root 指针 不空,按二叉搜索性质查找插入位置,插入新节点 例如有以下这个数组,依次按照数组的元素插入就如下图的二叉搜索:...BST的插入递归插入 // 插入 bool Insert(const K& val) { // 如果节点为空 if (_root == nullptr)...五、二叉搜索的性能分析 首先插入和删除操作都必须先查找,查找效率代表了二叉搜索中各个操作的性能。

9010

基于中序有序的二叉搜索

二叉搜索又称为二叉排序,它要么是一棵空,要么是一棵具有以下特点的: 1.如果它的左子树不为空,那么它左子树上所有节点的值都小于节点的值 2.如果它的右子树不为空,那么它右子树上所有节点的值都小于节点的值...所以后面还有平衡二叉等对结果做进一步的限制,能大大的提升查找的效率 查找的非递归写法 在搜索中查找某一个值,如果这个值比节点的值要小,就往的左子树中找;如果比节点的值要大,就往右子树中找。...false : true; } 二叉搜索插入搜索插入不能破坏搜索的结构,所以不能插入和树种元素相同的值 非递归 //二叉搜索中序遍历结果是有序的数列,不允许往其中插入相同的值,插入删除不允许破坏结构...//它左孩子的值比小,右孩子比大 bool Insert(const K& key) { //插入,分为空插入和非空插入 if (_root == nullptr)...//它左孩子的值比小,右孩子比大 bool Insert(const K& key) { //插入,分为空插入和非空插入 if (_root == nullptr)

18730

精读《算法基础数据结构》

& 二叉搜索 二叉搜索是一种特殊二叉,更复杂的还有红黑,但这里就不深入了,只介绍二叉搜索。...二叉搜索满足对于任意节点,left 的所有节点 < 节点 < right 的所有节点,注意这里是所有节点,因此在判断时需要递归考虑所有情况。...二叉搜索的好处在于,访问、查找、插入、删除的时间复杂度均为 O(logn),因为无论何种操作都可以通过二分方式进行。...更好的方案有 AVL 、红黑等,像 JAVA、C++ 标准库实现的二叉搜索都是红黑。 字典 字典多用于单词搜索场景,只要给定一个单独开头,就可以快速查找到后面有几种推荐词。...并查集的实现不同,数据也会有微妙的不同,高效的并查集在插入时,会递归将元素的值尽量指向老大,这样查找判断时计算的快一些,但即便指向的不是老大,也可以通过递归的方式找到老大。

42600

可能是最可爱的一文读懂系列:皮卡丘の复杂度分析指南

用于归并排序的递归 每一个节点表示一个子问题,每个节点上的数值表示解决该问题需要花费的工作量。节点表示的就是初始问题。 在我们的递归中,每个非叶节点有2个子节点,而且标有子所划分处的子问题数量。...Master方法的情况2,其中大部分工作是在递归处完成的,这就是为什么 Θ(f(n))控制算法的复杂度的原因。...( 注:排序是运行二进制搜索的前提条件,一旦列表被排序后,皮卡丘可以在此排序列表上多次运行二进制搜索)。 让我们看看这个算法的代码,然后分析它的复杂性。 ? 显然,该算法的本质是递归。...除了根据某种条件进行递归调用之外,它实际上并没有做任何事情。那么,让我们快速查看二进制搜索算法的递归关系。 T(n) = T(n / 2) + O(1) 这看起来好像是一个非常简单的递归关系。...首先让我们尝试分析递归并从中得出复杂性,然后我们将使用主定理方法,看看三种情况中哪一种适合这种递归。 ? 哇!这种二进制搜索算法非常快。它比线性搜索快得多。

88750

C++二叉搜索

【C++进阶学习】二叉搜索 零、前言 一、二叉搜索概念 二、二叉搜索的详解及模拟 1、二叉搜索的结构 2、二叉搜索的构造和析构 3、二叉搜索的查找 4、二叉搜索插入 5、二叉搜索的删除...Tree)又称二叉排序,也称作二叉查找它或者是一棵空,或者是具有以下性质的二叉 若它的左子树不为空,则左子树上所有节点的值都小于节点的值 若它的右子树不为空,则右子树上所有节点的值都大于节点的值...,查找、插入为O(n)(形似单链表) 示图: 二叉查找是基础性数据结构,用于构建更为抽象的数据结构,如map,set等 二、二叉搜索的详解及模拟 1、二叉搜索的结构 二叉搜索结点结构...具体操作过程: 若走到空节点,则搜索失败,返回空指针 若key大于当前结点的数据域之值,则搜索右子树 若key小于当前结点的数据域之值,则搜索左子树 若key等于当前结点的数据域之值,则查找成功,...,并且保护私有成员 子函数一般建议设置为私有,避免接口暴露 4、二叉搜索插入 具体操作过程: 若key大于当前结点的数据域之值,则插入右子树 若key小于当前结点的数据域之值,则插入左子树 若key

28940
领券