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

为什么在删除函数调用后指针没有将BST的节点置零?

在删除函数调用后,指针没有将BST的节点置零的原因是因为在删除节点时,只是将节点从树中移除,并没有对指针进行置零操作。这是因为在删除节点时,只需要将其父节点指向其子节点即可完成删除操作,不需要对被删除节点的指针进行修改。

BST(二叉搜索树)是一种特殊的二叉树,它的每个节点的值大于其左子树中的所有节点的值,小于其右子树中的所有节点的值。在删除节点时,有以下几种情况需要考虑:

  1. 被删除节点没有子节点:直接将其父节点指向空即可。
  2. 被删除节点只有一个子节点:将其父节点指向其子节点即可。
  3. 被删除节点有两个子节点:需要找到其右子树中的最小节点(或左子树中的最大节点),将其值替换到被删除节点中,然后再删除该最小节点(或最大节点)。

在以上情况中,只有第一种情况需要将指针置零,其他情况只需要修改指针的指向即可。这是因为在删除节点后,BST的结构并没有发生改变,只是节点的值发生了变化或者节点的位置发生了调整。

需要注意的是,删除节点时需要保证BST的性质仍然成立,即左子树中的所有节点的值小于根节点的值,右子树中的所有节点的值大于根节点的值。如果删除节点后没有进行相应的调整,可能会导致BST的性质被破坏。

推荐的腾讯云相关产品:腾讯云数据库TDSQL、腾讯云云服务器CVM、腾讯云容器服务TKE、腾讯云对象存储COS等。具体产品介绍和链接地址可以参考腾讯云官方网站。

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

相关·内容

盘点那些必问的数据结构算法题之二叉树基础

而二叉搜索树(BST)是有序的二叉树,BST需要满足如下条件: 若任意结点的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若任意结点的右子树不空,则右子树上所有节点的值均大于或等于它的根节点的值...二叉查找树(BST)特有的操作都在函数前加了 bst 前缀区分,其他函数则是二叉树通用的。 1) 创建结点 分配内存,初始化值即可。...删除结点 删除结点稍微复杂一点,要考虑3种情况: 删除的是叶子结点,好办,移除该结点并将该叶子结点的父结点的 left 或者 right 指针置空即可。...删除的结点有两个子结点,则需要找到该结点左子树的最大结点(使用后面的bstSearchIter 函数),并将其值替换到待删除结点中,然后递归调用删除函数删除该结点左子树最大结点即可。...这里值得一提的是层序遍历,先是计算了二叉树的高度,然后调用的辅助函数依次遍历每一层的结点,这种方式比较容易理解,虽然在时间复杂度上会高一些。

11410

【43期】盘点那些必问的数据结构算法题之二叉树基础

树中基本单位是结点,结点之间的链接,称为分支。一棵树最上面的结点称之为根节点,而下面的结点为子结点。一个结点可以有0个或多个子结点,没有子结点的结点我们称之为叶结点。...而二叉搜索树(BST)是有序的二叉树,BST需要满足如下条件: 若任意结点的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若任意结点的右子树不空,则右子树上所有节点的值均大于或等于它的根节点的值...删除结点 删除结点稍微复杂一点,要考虑3种情况: 删除的是叶子结点,好办,移除该结点并将该叶子结点的父结点的 left 或者 right 指针置空即可。...删除的结点有两个子结点,则需要找到该结点左子树的最大结点(使用后面的bstSearchIter 函数),并将其值替换到待删除结点中,然后递归调用删除函数删除该结点左子树最大结点即可。 ?...这里值得一提的是层序遍历,先是计算了二叉树的高度,然后调用的辅助函数依次遍历每一层的结点,这种方式比较容易理解,虽然在时间复杂度上会高一些。

37710
  • 二叉搜索树

    ---- 查找操作 算法如下: 1)树为空,返回NULL 2)树非空时,对根节点的键值与x即你想那个比较,如果相等则返回根节点 3)如果x小于根结点的键值,在左子树进行查找x 4)如果x...,最大值一定在最右分支的端节点上,最小值在最左分支的端节点上。...算法如下: 1)树空时,直接返回NULL 2)树非空时,如果要删除的是叶子节点时,直接删除,并把父节点的相应指针置为NULL。...3)要删除的只有一个孩子时,把其父节点的指针指向要删除的结点的孩子结点。...3)若当前结点为树的根结点时,直接返回根结点的右子树 4)否则,若当前结点的右子树为空,即当前结点为叶子结点时,父节点的左子树置NULL,释放当前结点。

    67020

    Binary Search Trees(BST)

    BST的性质 BST的形状为 image.png 每个BST中的节点x,存在一个key,一个指向父节点的parent指针,同时还有一个左子树和右子树 root的parent不存在 左子树值y与父节点...然后插入第二个元素40,它比30要大,置为它的右节点 image.png 插入第三个元素17,比30要小,置为它的左节点 image.png 然后是20,比30小,找到做子树,左子树的节点值为17...y.right = z else: y.left = z 复制代码 它的耗时为O(lgn) 找到后继节点 后继节点即从值上来讲,找到比要找的元素要大最接近的值,根据BST的性质,它肯定在右子树上...,由于20没有右子树,会先回溯到17,然后17是它的父节点的左子树,那么它就是后继节点; 40的后继不存在; def successor(self,node): if node == None...=None: x = x.left return x 复制代码 删除节点 节点删除之后,必须要维持原有的BST性质 image.png 删除节点13,它一个子节点都没有,直接删除即可 image.png

    38430

    【二叉搜素树】——LeetCode二叉树问题集锦:6个实用题目和解题思路

    递归遍历每条路径,沿途维护一个当前的数字值,将每个节点的值添加到数字的末尾。 如果到达叶子节点,将当前生成的数字添加到总和中。 返回所有根到叶路径数字的总和。...return ret; } }; 二叉树剪枝 解题思路: 需要剪除二叉树中所有的子树,如果整个子树中没有 1,就删除该子树。...可以使用后序遍历递归判断每个节点的左右子树: 先递归处理左子树和右子树。 如果左子树没有 1,则将左子树置为 None;如果右子树没有 1,则将右子树置为 None。...可以通过递归设定上下边界来验证每个节点: 对于根节点,其值在 (−∞, +∞) 范围内。 对于左子节点,设定其值范围为 (min, 当前节点值)。...由于 BST 的中序遍历会按从小到大的顺序输出节点值,因此可以通过中序遍历找到第 k 小的元素。

    23510

    数据结构学习—树(2)

    二叉搜索树(Binary Search Tree) 1.非空左子树的所有键值小于其根节点的键值 2.非空右子树的所有键值大于其根节点的键值 3.左右子树都是二叉搜索树 二叉搜索树的删除 要删除的是叶节点...:直接删除,并再修改其父节点指针—置为NULL 要删除的节点只有一个孩子节点:将其父节点的指针指向要删除节点的孩子节点 要删除的节点有左、右两颗子树:右子树最小元素或左子树最大元素替代被删除的节点...) //树置空 { if(BST !...return NULL; } Position Find(int x, Tree BST) //找到值为x的元素在树中位置,使用递归方式 { if(!...) 找到值为x的元素在树中位置,使用循环迭代方式 { while(BST){ if(x > BST->Data) BST = BST->Right;

    45930

    整理得吐血了,二叉树、红黑树、B&B+树超齐全,快速搞定数据结构

    为什么选择AVL树而不是BST? 大多数BST操作(如搜索、最大值、最小值、插入、删除等)的时间复杂度为O(h),其中h是BST的高度。对于极端情况下的二叉树,这些操作的成本可能变为O(n)。...image 根据BST规则删除节点133,155替代133位置 从155位置往上检测到100为失衡节点u,左高右低为LR情况,对u左子节点ul=37左旋,再对u节点执行右旋(可以看成对50同时插入2个子节点导致...个人引申的疑问 为什么红黑树也算平衡树呢?它的平衡因子是什么? 为什么AVL比红黑树更平衡?为什么AVL树插入和删除会引起更多选择呢?...插入步骤: 将新节点n根据BST规则插入,且新使节点颜色为红色 根据n的父节点p情况执行不同的操作 2.1 n没有父节点p,即N为根,将n的颜色更改为黑色 2.2 p为黑色,直接插入 2.3 p为红色,...数据指针在B+树中仅存在于叶节点,因此叶节点必须将所有键值及其对应的数据指针存储到磁盘文件块以便访问。此外,叶节点也用于链接以提供对记录的有序访问。

    3.1K21

    使用 Go 语言实现二叉搜索树

    原文链接: 使用 Go 语言实现二叉搜索树二叉树是一种常见并且非常重要的数据结构,在很多项目中都能看到二叉树的身影。...二叉搜索树的特点最重要的就是它的有序性,在二叉搜索树中,每个节点的值都大于其左子树中的所有节点的值,并且小于其右子树中的所有节点的值。图片这意味着通过二叉搜索树可以快速实现对数据的查找和插入。...,分三种情况来考虑:如果要删除的节点没有子节点,只需要直接将父节点中,指向要删除的节点指针置为 nil 即可如果删除的节点只有一个子节点,只需要更新父节点中,指向要删除节点的指针,让它指向删除节点的子节点即可如果删除的节点有两个子节点...,我们需要找到这个节点右子树中的最小节点,把它替换到要删除的节点上。...然后再删除这个最小节点,因为最小节点肯定没有左子节点,所以可以应用第二种情况删除这个最小节点即可最后是一个打印树形结构的方法,在实际项目中其实并没有实际作用:func (bst *ItemBinarySearchTree

    19520

    导师计划--数据结构和算法系列(上)

    ,并将元素传递给回调函数。...回调函数的四个参数的意义如下:accumulator,必需,累计器累计回调的返回值, 它是上一次调用回调时返回的累积值,或initialValue;currentValue,必需,数组中正在处理的元素;...哈希表把key(键)通过一个固定的算法函数(此函数称为哈希函数/散列函数)转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value(值)存储在以该数字为下标的数组空间里...,而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value。...在遍历的时候,我们分为三种遍历方法--先序遍历,中序遍历和后序遍历: 删除节点是一个比较复杂的操作,考虑的情况比较多: 该节点没有叶子节点的时候,直接将该节点置空; 该节点只有左子树,直接将该节点赋予左子树

    17010

    【数据结构与算法】详解什么是树结构,并用代码手动实现一个二叉查找树

    树结构的优点: 空间利用率比较高 可以非常快速地查找到最大值和最小值 三、树结构的术语 因为本文是从零开始学习树结构,所以我们在这里有必要讲解一下,在我们封装各种树结构的过程中涉及到的术语,方便大家理解...该方法接收一个回调函数 handle 作为参数, 用于在遍历过程中执行某些操作 实现思路: 从根结点开始,按照 访问根结点 => 访问左子树 => 访问右子树 的顺序对各个结点进行访问 访问到结点时,执行回调函数...== null) { // 将根结点的 key传给回调函数处理 handle(node.key) // 遍历左子树 this.preOrderNodes...该方法无需传入参数 实现思路: 从根结点开始,按照 访问左子树 => 访问根节点 => 访问右子树 的顺序对各个结点进行访问 访问到结点时,执行回调函数 handle ,并将访问到的结点的 key 作为参数传入...删除的结点为叶子结点 假设我们要删除 结点14 ,因为该结点为叶子结点,后面没有其它结点,所以直接删除它不会对后续结点造成影响,即将 结点14 的父节点 结点13 的右子结点设置为 null ,如图

    67930

    查找--数据结构

    从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。...SearchMax(root->rchild); } //删除节点代码: void DeleteBSTNode(BST_P *root, DataType data) { BST_P p...result 指针的值:" data << endl; //在二叉排序树中插入9 Insert_BST(&root, 9); printf...,若余数为零再加上30而为哈希函数值。...注:会产生空隙 三、 哈希表的查找及分析 在哈希表上进行查找的过程跟哈希造表过程基本一致,给定K值,根据造表时设计的哈希函数计算出哈希地址,若此位置上没有记录,则查找不成功;否则比较关键字若与给定的关键字相同

    65420

    2022前端常考手写面试题总结

    // 移动指针位置 return head // 返回删除的元素 }else { let current = this.head for (let i = 0; i 删除的指针的上一个 current.next.next // 如删除200, 100=>200=>300 找到200的上一个100的next的next为300,把300赋值给...({age:20})bst.add({age: 5})console.log(bst)手写 Promise.thenthen 方法返回一个新的 promise 实例,为了在 promise 状态发生变化时...我们可以将传给 then 的函数和新 promise 的 resolve 一起 push 到前一个 promise 的 callbacks 数组中,达到承前启后的效果:承前:当前一个 promise 完成后...),这个函数内执行add(m+n),n是此次传进来的数值5,m值还是上一步中的7,所以add(m+n)=add(7+5)=add(12),此时m=12,并且返回temp函数由于后面没有传入参数,等于返回的

    41920

    实现一个二叉搜索树(JavaScript 版)

    二叉树在计算机科学中应用很广泛,学习它有助于让我们写出高效的插入、删除、搜索节点算法。二叉树的节点定义:一个节点最多只有两个节点,分别为左侧节点、右侧节点。...初始化一个二叉搜索树 声明一个 BST 类,在构造函数的 constructor() 里声明它的结构: class BST { constructor () { this.root...中序遍历 中序遍历,先访问左侧节点,直到为最小节点访问到树的最底端,将当前节点的 value 取出来,在访问右侧节点,适用于从小到大排序。...二叉树搜索销毁 在上面最后讲解了二叉搜索树的后序遍历,这里讲下它的实际应用,在 C++ 等面向对象编程语言中可以定义析构函数使得某个对象的所有引用都被删除或者当对象被显式销毁时执行,做一些善后工作。...例如,我们本次实现的二叉搜索树,可以利用后序遍历的方式,逐渐将每个节点进行释放。 定义一个 destroy 方法,以便在树的实例上能够调用。

    1.4K30

    【算法】二叉查找树(BST)实现字典API

    所以代码默认不能选择 -1作为 Key或者Value (在实际场景中,我们会将int类型的Key替换为实现Compare接口的类的对象,同时将“失败”时的返回值从-1设为null,这时是没有这个问题的)..., 设置为外部类BST的成员变量不是就可以了吗,  为什么要为每个结点都设置一个N属性呢 Node类里的成员变量N除了为size方法服务外, 更多地是为rank方法和select方法服务的。...: 递归调用前代码和递归调用后代码 put的递归将一段代码分割成两部分: 递归调用前代码和递归调用后代码,如图所示 ?...,能够“继承”某个结点的结点 删除的实现思路 查找到相应的结点 将其删除 分析删除某个结点的三种情况 删除结点时, 按结点的位置,可以分三种情况分析: 第一种情况: 当被删除的结点没有子树时, 直接将它父节点指向它的链接置为...都是:在查找到待删除结点后,判断左子树或右子树是否为空, 若其中一个子树为空,则将该结点的父节点指向该节点的链接, 改为指向该节点的另一颗子树(左子树为null则指向右子树,右子树为null则指向右子树

    1.6K90

    美团面试官:你对二叉树后续遍历一无所知

    那有的读者可能会问,根据 BST 的定义,有没有可能一棵二叉树中不存在 BST?...不会的,因为按照 BST 的定义,任何一个单独的节点肯定是 BST,也就是说,再不济,二叉树最下面的叶子节点肯定是 BST。...res; } 这样,这道题就解决了,traverse函数在遍历二叉树的同时顺便把之前辅助函数做的事情都做了,避免了在递归函数中调用递归函数,时间复杂度只有 O(N)。...其实也不是,主要是看题目,就好比 BST 的中序遍历是有序的一样。 这道题为什么用后序遍历呢,因为我们需要的这些变量都是可以通过后序遍历得到的。...因为以上几点都可以通过后序遍历的方式「顺便」计算出来,所以这道题使用后序遍历肯定是最高效的。

    52220

    百度前端一面常见手写面试题(持续更新中)

    // 移动指针位置 return head // 返回删除的元素 }else { let current = this.head for (let i = 0; i 删除的指针的上一个 current.next.next // 如删除200, 100=>200=>300 找到200的上一个100的next的next为300,把300赋值给...因为 Promise 的状态只能改变一次, 那么我们只需要把 Promise.race 中产生的 Promise 对象的 resolve 方法, 注入到数组中的每一个 Promise 实例中的回调函数中即可...在这个对象上使用 open 方法创建一个 HTTP 请求,open 方法所需要的参数是请求的方法、请求的地址、是否异步和用户的认证信息。在发起请求前,可以为这个对象添加一些信息和监听函数。...('cxk', 'father');child.say() // father好,我是练习时长两年半的cxk手写防抖函数函数防抖是指在事件被触发 n 秒后再执行回调,如果在这 n 秒内事件又被触发,则重新计时

    38620

    【C++课程学习】:二叉搜索树

    此时的节点结构为: ⚽️ 构造函数: 在实践情况中,我们一般用一个T类型的值(键值)去进行构造一个节点。其他的用BST_node去进行拷贝构造基本是不可能的。所以写这一个构造函数就够了。...(key) { } //左右节点指针,以及键值 BST_Node* _left; BST_Node* _right; T _key; }; 另外下面还有对该节点和节点指针重命名的...: 删除步骤: 把搜索二叉树的节点进行分类,具体点可以分为三种情况: ●叶子节点(左右指针都为空): 删除叶子节点时,直接删除即可,如果叶子节点在父节点的左边,就把父节点的左指针变为空,如果叶子节点在父节点的右边...注意:如果此时叶子节点为_root(根节点),就没有父节点,只需把_root变为nullptr。...析构函数也要进行逐一释放。 BST(const BST& t) { _root = copy(t.

    11010

    数据结构简单复习

    插入 先判断队列是否已满,如果还没满,rear=(rear+1)%n 删除 先判断队列是否为空,如果不为空,front=(front+1)%n BST(二叉查找树) BST上节点的左孩子的值总是小于该结点...在剩余字符结点与哈夫曼树的树根结点间选择最小的两个结点,将两个结点合成一颗树(此时有多棵哈夫曼树)或将一个结点加入哈夫曼树(这个结点和树根有同一个父节点)。 重复第三步直到所有结点被加入哈夫曼树。...大顶堆 删除 将堆尾部的元素与将要删除的元素交换位置,再重新调整先前处于尾部的元素的位置。...针对合并的过程,也可以再组织一个数组,前半部分正向存储数组,后半部分反向存储,同样拥有两个指针,形如:1367|5432。这么做的好处是不需要判断指针是否越界,两个指针指向同一位置时合并过程结束。...闭哈希( Closed Hashing ) 闭哈希遇到不同关键字处于同一位置的情况,会确定下一个可能存储的位置,其中最简单的一种是线性探测,当哈希函数计算出的位置存放了别的数据时,依次往后寻找。

    98420
    领券