数据结构代码实现

数据结构三要素：逻辑结构、存储结构、数据运算（增删改查）

所以呢以下代码实现也将从这三方面展开

二叉搜索树

存储结构：

typedef struct BSTNode{
    int data;
    struct BSTNode *lchild, *rchild;
}BSTNode;

二叉搜索树————查找

拿要找的数和根结点对比，如果要找的数大于根结点，就去右子树找，如果小于根结点，就去左子树找

如果要找的数等于根结点，就直接返回根结点

如果要找的数不存在，就返回空指针

BSTNode *RecSearch(BSTNode *root, int x){
    if (root == NULL)// if(!root)
        return NULL;
    else if(x < root->data)
        return RecSearch(root->lchild, x);
    else if(x > root->data)
        return RecSearch(root->rchild, x);
    else// x == root->data
        return root;
}

BSTNode *IterSearch(BSTNode *root, int x){
    while(root != NULL){// while(root)也可
        if(x < root->data)
            root = root->lchild;
        else if(x > root->data)
            root = root->rchild;    
        else// x == root->data
            break;
    }
    return root;
}

二叉搜索树————插入

查找到要插入的位置(通过root指针遍历)，即查找失败的位置

在该位置插入新的结点

void Insert(BSTNode *&root, int x){
    if(root == NULL){//查找失败的位置就是插入的位置
        root = (BSTNode *)malloc(sizeof(BSTNode));
        root->data = x;
        root->lchild = root->rchild = NULL;
    }
    else if(x < root->data)
        Insert(root->lchild, x);
    else if(x > root->data)
        Insert(root->rchild, x);
}

二叉搜索树————删除

查找到要删除的结点,删除该结点

注：root是以引用类型传递的，即可以修改；

在递归过程中，每次的root是某个结点的lchild或rchild，通过root = root->child保证了链表的完整性

//查找最小值
BSTNode *FinMin(BSTNode *p){
    while(p->lchild != NULL){//查找最小值，即最左下的结点
        p = p->lchild;
    }
    return p;
}

//查找最大值，如果是前驱的话，把Delete中的next改为pre并调用此函数即可
BSTNode *FinMax(BSTNode *p){
    while(p->rchild != NULL){//查找最大值，即最右下的结点
        p = p->rchild;
    }
    return p;
}

void Delete(BSTNode *&root, int x){
    if(root == NULL)
        return;//不存在要删除的结点
    if(x < root->data)//小了递归到左子树
        Delete(root->lchild, x);
    else if(x > root->data)//大了递归到右子树
        Delete(root->rchild, x);
    else{
        //左右子树均为空，直接删除
        if(root->lchild == NULL && root->rchild == NULL){
            free(root);
            root = NULL;
        }
        //左不空右空，左替代
        else if(root->lchild != NULL && root->rchild == NULL){
            BSTNode *temp = root;
            root = root->lchild;
            free(temp);
        }
        //左空右不空，右替代
        else if(root->lchild == NULL && root->rchild != NULL){
            BSTNode *temp = root;
            root = root->rchild;
            free(temp);
        }
        //左右子树均不空，前驱(左子树中最大，即最右下的结点)/后继(右子树中最小，即最左下的结点)值替代，删除原来的前驱/后继--中序遍历--左<根<右
        else{
            BSTNode *next = FinMin(root->rchild);
            root->data = next->data;
            Delete(root->rchild, next->data);//删除原来的后继结点
        }
    }
}

测试

AI写的测试代码：

//中序遍历--左<根<右
void InOrder(BSTNode *root){
    if(root){
        InOrder(root->lchild);
        std::cout << root->data << " ";
        InOrder(root->rchild);
    }
}

// ===================== 主函数：测试所有功能 =====================
int main(){
    // 1. 测试用数组
    int arr[] = {50, 30, 70, 20, 40, 60, 80};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 2. 创建二叉搜索树
    BSTNode *root = CreateBST(arr, n);
    printf("===== 初始构建的二叉搜索树（中序遍历）=====\n");
    InOrder(root);
    printf("\n\n");

    // 3. 测试【递归查找】和【迭代查找】
    int target1 = 40;  // 存在的节点
    int target2 = 90;  // 不存在的节点

    // 递归查找
    BSTNode *res1 = RecSearch(root, target1);
    BSTNode *res2 = RecSearch(root, target2);
    printf("===== 递归查找测试 =====\n");
    printf("查找 %d：%s\n", target1, res1 ? "找到" : "未找到");
    printf("查找 %d：%s\n\n", target2, res2 ? "找到" : "未找到");

    // 迭代查找
    BSTNode *res3 = IterSearch(root, target1);
    BSTNode *res4 = IterSearch(root, target2);
    printf("===== 迭代查找测试 =====\n");
    printf("查找 %d：%s\n", target1, res3 ? "找到" : "未找到");
    printf("查找 %d：%s\n\n", target2, res4 ? "找到" : "未找到");

    // 4. 测试【插入节点】
    int insertVal = 55;
    Insert(root, insertVal);
    printf("===== 插入 %d 后（中序遍历）=====\n", insertVal);
    InOrder(root);
    printf("\n\n");

    // 5. 测试【删除节点】（分3种情况测试）
    // 情况1：删除叶子节点 20
    int del1 = 20;
    Delete(root, del1);
    printf("===== 删除叶子节点 %d 后 =====\n", del1);
    InOrder(root);
    printf("\n");

    // 情况2：删除单孩子节点 70
    int del2 = 70;
    Delete(root, del2);
    printf("===== 删除单孩子节点 %d 后 =====\n", del2);
    InOrder(root);
    printf("\n");

    // 情况3：删除双孩子节点 50（根节点）
    int del3 = 50;
    Delete(root, del3);
    printf("===== 删除根节点 %d 后 =====\n", del3);
    InOrder(root);
    printf("\n");

    return 0;
}

运行结果：