二叉查找树实现(C)

本来今天想连平衡二叉查找树一起写掉的，结果删除结点这里卡着了...

二叉查找树介绍

• 二叉查找树是一种特殊的二叉树，英文名为Binary Search Tree。
• 结构至少包括左子树、右子树、key，三个部分。
• 树中每个结点都是独特的。
• 一般来说，一个结点与其子树的key值的分布如下：
  • 左子树 < 根 < 右子树。
• 个人认为顺序颠倒也没问题，不过没见过顺序颠倒的树。

结构体

typedef struct BSTNode {
    struct BSTNode* lChild;
    struct BSTNode* rChild;
    int key;
}BSTNode;

结点初始化

BSTNode* initializeBinarySearchTree(int key) {
    //  初始化二叉查找树结点。
    BSTNode* BST = malloc(sizeof(BSTNode));
    BST->key = key;
    BST->lChild = BST->rChild = NULL;
    return BST;
}

添加结点

int addKey(BSTNode* t, int key) {
    //  添加新结点。
    //  返回1则表示添加成功，-1则表示二叉查找树已存在该值，插入失败。
    if (t->key == key) return -1;
    else if (t->key > key) {
        if (t->lChild) return addKey(t->lChild, key);
        else t->lChild = initializeBinarySearchTree(key);
    }
    else if (t->key < key) {
        if (t->rChild) return addKey(t->rChild, key);
        else t->rChild = initializeBinarySearchTree(key);
    }
    return 1;
}

删除结点

BSTNode* deleteKey(BSTNode* t, int key) {
    //  这个代码参考了Hopeton.J的这篇：https://blog.csdn.net/weixin_42426841/article/details/107348458
    //  我自己写了几种，都不能完全满足要求。
    //      一个比较成功的方法是不删除结点，而是将结点的值置为其直接后继的值，
    //      然后再递归删除直接后继。
    //      在前面的结点都很正常，但删除叶子结点的时候，因为我没有修改其父结点的值，
    //      导致父节点还是会指向这个被释放掉的地址，就导致每次遍历到这个结点就会报错。
    //      我试过直接借助父节点来删除，但删除根节点的时候又会出现麻烦的问题。
    //      个人想到的比较好的处理方法就是不删除结点，而是设置标志位表示该结点为空。
    //  最后还是网上参考了一下这篇，很厉害的解法。
    BSTNode* temp;
    if (!t) return t;
    if (t->key == key) {
        if (!t->lChild) return t->rChild;
        else if (!t->rChild) return t->lChild;
        else {
            //左右子树非空，找到其右子树的最左结点，即直接后继successor。
            //将待删除的结点内容置为successor结点的内容。
            //再删除successor树里的successor结点。
            temp = t->rChild;
            while (temp->lChild) temp = temp->lChild;
            temp->lChild = t->lChild;
            return t->rChild;
        }
    }
    else if (t->key > key) t->lChild = deleteKey(t->lChild, key);
    else if (t->key < key) t->rChild = deleteKey(t->rChild, key);
    return t;
}

输出树

void printTree(BSTNode* t) {
    //  打印树。
    if (!t) return;
    if (t->lChild) printTree(t->lChild);
    if (t) printf("%d", t->key);
    if (t->rChild) printTree(t->rChild);
}

查找结点

BSTNode* findKey(BSTNode* t, int key) {
    //  找到key为key的结点。
    if (!t) return NULL;
    else if (t->key == key) return t;
    else if (t->key > key) return findKey(t->lChild, key);
    else if (t->key < key) return findKey(t->rChild, key);
    return NULL;
}

完整代码（附测试）

• 注，main函数里面没有findKey函数的使用，但能用。

#include <stdio.h>
#include <stdlib.h>

typedef struct BSTNode {
    struct BSTNode* lChild;
    struct BSTNode* rChild;
    int key;
}BSTNode;

BSTNode* initializeBinarySearchTree(int key);
int addKey(BSTNode* t, int key);
void printTree(BSTNode* t);
BSTNode* findKey(BSTNode* t, int key);
BSTNode* deleteKey(BSTNode* t, int key);

int main() {
    BSTNode* t = initializeBinarySearchTree(0);
    for (int i = 1; i < 12; i += 3) {
        addKey(t, i);
    }
    for (int i = 2; i < 12; i += 3) {
        addKey(t, i);
    }
    for (int i = 3; i < 12; i += 3) {
        addKey(t, i);
    }
    printTree(t);
    puts("");
    t = deleteKey(t, 11);
    printTree(t);
    puts("");

    system("PAUSE");
    return 0;
}

BSTNode *initializeBinarySearchTree(int key) {
    //  初始化二叉查找树结点。
    BSTNode* BST = malloc(sizeof(BSTNode));
    BST->key = key;
    BST->lChild = BST->rChild = NULL;
    return BST;
}

int addKey(BSTNode* t, int key) {
    //  添加新结点。
    //  返回1则表示添加成功，-1则表示二叉查找树已存在该值，插入失败。
    if (t->key == key) return -1;
    else if (t->key > key) {
        if (t->lChild) return addKey(t->lChild, key);
        else t->lChild = initializeBinarySearchTree(key);
    }
    else if (t->key < key) {
        if (t->rChild) return addKey(t->rChild, key);
        else t->rChild = initializeBinarySearchTree(key);
    }
    return 1;
}

void printTree(BSTNode* t) {
    //  打印树。
    if (!t) return;
    if (t->lChild) printTree(t->lChild);
    if (t) printf("%d ", t->key);
    if (t->rChild) printTree(t->rChild);
}

BSTNode* findKey(BSTNode* t, int key) {
    //  找到key为key的结点。
    if (!t) return NULL;
    else if (t->key == key) return t;
    else if (t->key > key) return findKey(t->lChild, key);
    else if (t->key < key) return findKey(t->rChild, key);
    return NULL;
}

BSTNode* deleteKey(BSTNode* t, int key) {
    //  这个代码参考了Hopeton.J的这篇：https://blog.csdn.net/weixin_42426841/article/details/107348458
    //  我自己写了几种，都不能完全满足要求。
    //      一个比较成功的方法是不删除结点，而是将结点的值置为其直接后继的值，
    //      然后再递归删除直接后继。
    //      在前面的结点都很正常，但删除叶子结点的时候，因为我没有修改其父结点的值，
    //      导致父节点还是会指向这个被释放掉的地址，就导致每次遍历到这个结点就会报错。
    //      我试过直接借助父节点来删除，但删除根节点的时候又会出现麻烦的问题。
    //      个人想到的比较好的处理方法就是不删除结点，而是设置标志位表示该结点为空。
    //  最后还是网上参考了一下这篇，很厉害的解法。
    BSTNode* temp;
    if (!t) return t;
    if (t->key == key) {
        if (!t->lChild) return t->rChild;
        else if (!t->rChild) return t->lChild;
        else {
            //左右子树非空，找到其右子树的最左结点，即直接后继successor。
            //将待删除的结点内容置为successor结点的内容。
            //再删除successor树里的successor结点。
            temp = t->rChild;
            while (temp->lChild) temp = temp->lChild;
            temp->lChild = t->lChild;
            return t->rChild;
        }
    }
    else if (t->key > key) t->lChild = deleteKey(t->lChild, key);
    else if (t->key < key) t->rChild = deleteKey(t->rChild, key);
    return t;
}