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

如何在C中的二叉搜索树中正确插入/删除?

在C语言中,二叉搜索树(Binary Search Tree,BST)是一种特殊的二叉树,其中每个节点的值都大于或等于其左子树中所有节点的值,且小于或等于其右子树中所有节点的值。为了正确地在C语言中的二叉搜索树中插入和删除节点,我们需要遵循以下步骤:

  1. 插入节点:
代码语言:c
复制
#include<stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*) malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Node* insert(Node* root, int data) {
    if (root == NULL) {
        root = createNode(data);
    } else if (data< root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

int main() {
    Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    return 0;
}
  1. 删除节点:
代码语言:c
复制
#include<stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} Node;

Node* findMin(Node* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

Node* deleteNode(Node* root, int data) {
    if (root == NULL) {
        return root;
    }

    if (data< root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }

        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

int main() {
    Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    root = deleteNode(root, 20);
    return 0;
}

这些代码示例展示了如何在C语言中的二叉搜索树中正确插入和删除节点。请注意,这些代码示例仅用于演示目的,实际应用中可能需要进行更多的错误检查和内存管理。

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

相关·内容

二叉搜索插入操作

根节点和要插入值,将值插入二叉搜索。...返回插入二叉搜索根节点。输入数据保证,新值和原始二叉搜索任意节点值都不同。 注意,可能存在多种有效插入方式,只要插入后仍保持为二叉搜索即可。你可以返回任意有效结果。...701.二叉搜索插入操作 例如插入元素10 ,需要找到末尾节点插入便可,一样道理来插入元素15,插入元素0,插入元素6,需要调整二叉结构么?并不需要。。...迭代 再来看看迭代法,对二叉搜索迭代写法不熟悉,可以看这篇:二叉二叉搜索登场! 在迭代法遍历过程,需要记录一下当前遍历节点父节点,这样才能做插入节点操作。...在530.二叉搜索最小绝对差和501.二叉搜索众数,都是用了记录pre和cur两个指针技巧,本题也是一样

39320

如何删除二叉搜索节点?

450.删除二叉搜索节点 题目链接:https://leetcode-cn.com/problems/delete-node-in-a-bst/ 给定一个二叉搜索根节点 root 和一个值 key...,删除二叉搜索 key 对应节点,并保证二叉搜索性质不变。...递归 递归三部曲: 确定递归函数参数以及返回值 说道递归函数返回值,在二叉搜索插入操作通过递归返回值来加入新节点, 这里也可以通过递归返回值删除节点。...第五种情况有点难以理解,看下面动画: 450.删除二叉搜索节点 动画中颗二叉搜索删除元素7, 那么删除节点(元素7)左孩子就是5,删除节点(元素7)右子树最左面节点是元素8。...:搜索删除操作

1.4K30

二叉——700.二叉搜索搜索

1 题目描述 给定二叉搜索(BST)根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 节点。 返回以该节点为根子树。 如果节点不存在,则返回 null 。...来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/search-in-a-binary-search-tree 2 题目示例 3 题目提示 数节点数在...[1, 5000] 范围内 1 <= Node.val <= 10^7 root 是二叉搜索 1 <= val <= 10^7 4 思路 方法一:递归 二叉搜索满足如下性质: 左子树所有节点元素值均小于根元素值...复杂度分析 时间复杂度:O(N),其中N是二叉搜索节点数。最坏情况下二叉搜索是—条链,且要找元素比链末尾元素值还要小(大),这种情况下我们需要递归N次 空间复杂度:O(N)。...复杂度分析 时间复杂度:O(N),其中N是二叉搜索节点数。最坏情况下二叉搜索是—条链,且要找元素比链末尾元素值还要小(大),这种情况下我们需要迭代Ⅳ次 空间复杂度:O(1)。

34520

二叉搜索众数

二叉搜索众数 给定一个有相同值二叉搜索BST,找出BST所有众数(出现频率最高元素)。 假定BST有如下定义: 结点左子树中所含结点值小于等于当前结点值。...结点右子树中所含结点值大于等于当前结点值。 左子树和右子树都是二叉搜索。 示例 给定BST [1,null,2,2],返回[2]。...(假设由递归产生隐式调用栈开销不被计算在内),如果不考虑这个进阶条件的话,直接遍历一遍二叉并且顶一个哈希表将遍历过值以及出现次数记录,之后再遍历一遍哈希表取出众数即可,考虑到这个进阶条件,那么就需要定义一些变量保存当前状态...,判断哪些条件符合要求,置入返回值,当对二叉搜索进行二叉序遍历时,能够得到一个有序序列,通过数列有序以及存储当前状态变量即可达到目标,此外还需要注意是题目要求是返回一个数组,也就说众数可能有多个...,若左节点存在则向左递归,之后定义处理位置即序遍历,如果当前结点值与存储遍历当前节点值相同则将计数器递增,否则将当前值置数为节点值,将计数器置0,如果当前计数器大于等于最大值计数器则进入条件,如果这两个值相等

62230

​LeetCode刷题实战450:删除二叉搜索节点

今天和大家聊问题叫做 删除二叉搜索节点,我们先来看题面: https://leetcode-cn.com/problems/delete-node-in-a-bst/ Given a root...给定一个二叉搜索根节点 root 和一个值 key,删除二叉搜索 key 对应节点,并保证二叉搜索性质不变。返回二叉搜索(有可能被更新)根节点引用。...递归函数,有两个要点要理解,一个是递归函数作用,二是它返回结果是什么。这道题里,这个递归函数作用就是 删除一棵目标节点,返回是这棵修改后根节点root。...(启示:说到 二叉搜索BST时,不仅要想到序遍历结果是排好序,还要想到可以递归,有点像二分查找模式寻找目标值,提高效率) 删除节点: 经过上一步递归过程,找到了key,而且key是要调整这个子树根节点...刷题实战449:序列化和反序列化二叉搜索

31920

【leetcode刷题】T154-二叉搜索插入操作

---- 木又第154篇leetcode解题报告 二叉类型第44篇解题报告 leetcode第701题:二叉搜索插入操作 https://leetcode-cn.com/problems/insert-into-a-binary-search-tree.../ ---- 【题目】 给定二叉搜索(BST)根节点和要插入值,将值插入二叉搜索。...返回插入二叉搜索根节点。保证原始二叉搜索不存在新值。 注意,可能存在多种有效插入方式,只要插入后仍保持为二叉搜索即可。你可以返回任意有效结果。...例如, 给定二叉搜索: 4 / \ 2 7 / \ 1 3 和 插入值: 5 你可以返回这个二叉搜索:...当node为空,则比较parent->val和val大小,parent->val较大时,则插入节点作为parent节点左孩子,parent->val较小时,插入节点作为parent节点右孩子;当node

41530

LeetCode 701: 二叉搜索插入操作 Insert into a Binary Search Tree

题目: 给定二叉搜索(BST)根节点和要插入值,将值插入二叉搜索。返回插入二叉搜索根节点。保证原始二叉搜索不存在新值。...注意,可能存在多种有效插入方式,只要插入后仍保持为二叉搜索即可。你可以返回任意有效结果。...例如, 给定二叉搜索: 4 / \ 2 7 / \ 1 3 和 插入值: 5 你可以返回这个二叉搜索:...7 / \ 1 3 \ 4 解题思路: 二叉搜索插入操作与搜索操作类似,对于每个节点: 根据节点值与目标节点值关系,搜索左子树或右子树...; 如果目标值小于节点值,则继续在左子树搜索; 如果目标值大于节点值,则继续在右子树搜索

94720

LeetCode 450: 删除二叉搜索节点 Delete Node in a BST

题目: 给定一个二叉搜索根节点 root 和一个值 key,删除二叉搜索 key 对应节点,并保证二叉搜索性质不变。返回二叉搜索(有可能被更新)根节点引用。...一个正确答案是 [5,4,6,2,null,null,7], 如下图所示。...5 / \ 2 6 \ \ 4 7 解题思路: 待删除节点在二叉三种情况有: 如果目标节点没有子节点,我们可以直接移除该目标节点。...另外二叉搜索序遍历结果为从小到大顺序排列; 删除节点如果不是叶子节点时, 则应把该节点值替换为其右子树中最小一个节点值 (删除节点后驱节点); 删除节点如果不是叶子节点且无右子树时, 则应把该节点值替换为其左子树中最大一个节点值...(删除节点前驱节点), 并在子树递归删除刚刚替换节点 你会发现, 二叉搜索最小节点为该最左叶子; 最大节点为该最右叶子, 即: 如果 key > root.val,说明要删除节点在右子树

1.1K20

LeetCode96|二叉搜索搜索

1,问题简述 给定二叉搜索(BST)根节点和一个值。 你需要在BST中找到节点值等于给定值节点。 返回以该节点为根子树。 如果节点不存在,则返回 NULL。...2,示例 例如, 给定二叉搜索: 4 / \ 2 7 / \ 1 3 和值: 2 你应该返回如下子树: 2.../ \ 1 3 在上述示例,如果要找值是 5,但因为没有节点值为 5,我们应该返回 NULL。...3,题解思路 递归方法+二叉有序性 4,题解程序 public class SearchBSTTest { public static void main(String[] args) {...6,总结 这道题还是比较容易理解,理解二叉特点和数据有序性是非常有必要二叉遍历方式,二叉节点特点都是我们需要掌握

38240

二叉前序、序、后序和层次遍历 & 二叉搜索插入、查找操作

文章目录 建立 前序遍历 方法一:递归 方法二:使用栈 方法三:使用栈 序遍历 后序遍历 层次遍历 建立 首先,先建立起二叉类: public abstract class BinaryTree...if(root == null) return 0; return Math.max(height(root.left), height(root.right)) + 1; } } 然后是二叉搜索类...这个思路比较不好理解,但是却比较通用,下面序、后序遍历都可以使用这个思路,只需要把访问节点代码换个位置就可以。...方法跟前序遍历方法一、三类似,只不过在方法三,这里改为在出栈时才访问节点。...= null) { queue.offer(top.right); } } } 以上前序、序、后序遍历其实就是深度优先搜索; 层次遍历就是宽度(广度)优先搜索

28930

基于序有序二叉搜索

什么是二叉搜索 二叉搜索是普通二叉升级,普通二叉除了存储数据以外好像没有别的优势了,但是二叉搜索不同,如果对搜索采用序遍历得到结果是一串有序数字。...因为序遍历得到结果是一串有序数字列,所以对于二叉搜索而言中序遍历才是王道。...在一棵二叉搜索搜索一个元素,最坏结果也就是O(N),但如果这个搜索一个接近完全二叉情况,则只需要查找高度次。...false : true; } 二叉搜索插入搜索插入不能破坏搜索结构,所以不能插入和树种元素相同值 非递归 //二叉搜索序遍历结果是有序数列,不允许往其中插入相同值,插入删除不允许破坏结构...主要还是因为这一层root是上一层root->left或者root->right别名 二叉搜索删除 删除操作是二叉搜索树种最难一个,因为它涉及到情况相对比较多 1.如果这个要被删除节点有一个子树是空

17530

二叉搜索众数是多少?

501.二叉搜索众数 题目链接:https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/solution 给定一个有相同值二叉搜索...首先如果不是二叉搜索的话,应该怎么解题,是二叉搜索,又应该如何解题,两种方式做一个比较,可以加深大家对二叉理解。...递归法 如果不是二叉搜索 如果不是二叉搜索,最直观方法一定是把这个都遍历了,用map统计频率,把频率排个序,最后取前面高频元素集合。...是二叉搜索 既然是搜索,它序遍历就是有序。...在递归遍历二叉搜索过程,我还介绍了一个统计最高出现频率元素集合技巧, 要不然就要遍历两次二叉搜索才能把这个最高出现频率元素集合求出来。 为什么没有这个技巧一定要遍历两次呢?

60760

力扣 每日一题 删除二叉搜索节点(中等题)

一、题目描述: 给定一个二叉搜索根节点 root 和一个值 key,删除二叉搜索 key 对应节点,并保证二叉搜索性质不变。返回二叉搜索(有可能被更新)根节点引用。...一般来说,删除节点可分为两个步骤: 首先找到需要删除节点;如果找到了,删除它。说明:要求算法时间复杂度为 O(h),h 为高度。...一个正确答案是 [5,4,6,2,null,null,7], 如下图所示。 另一个正确答案是 [5,2,6,null,4,null,7]。...而找到该节点是非常简单,因为这棵二叉搜索,而二叉搜索特性,左节点值一定小于该节点值,右节点值一定大于该节点值,所以直接搜索就可以找到该值。...3.对于都有的情况,为了保证二叉搜索结构,我们 ① :可以用该节点左节点最右节点值代替该节点;②:也可以用该节点右节点最左节点值代替该节点。

39510
领券