首页
学习
活动
专区
工具
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语言中的二叉搜索树中正确插入和删除节点。请注意,这些代码示例仅用于演示目的,实际应用中可能需要进行更多的错误检查和内存管理。

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

相关·内容

没有搜到相关的合辑

领券