二叉查找树实现(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;
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注