二叉排序树 C语言源码插入查找删除

深碍√TFBOYSˉ_ 2022-05-09 15:00 166阅读 0赞

二叉排序树，详细概念略过，参考数据结构书籍；详细代码如下：（以下代码，均可直接运行）

## 存储结构：二叉链表 ##

typedef struct SOSTree {
        int data;
        struct SOSTree *LChild, *RChild;
    } SOSTree;

## 插入： ##

bool InsertBST(SOSTree **T, int elem) {
        // 二级指针，这样一来T可以在主函数中初始化为NULL，也能正常访问
        SOSTree **p, *s;
        p = (SOSTree **) malloc(sizeof(SOSTree *));
        if (!SearchBST(*T, elem, NULL, p)) {
            s = (SOSTree *) malloc(sizeof(SOSTree));
            s->data = elem;
            s->RChild = s->LChild = NULL;
            if (!*T) *T = s;
            else if (LTI(elem, (**p).data)) (**p).LChild = s;
            else (**p).RChild = s;
            return true;
        }
        return false;
    }

## 查找： ##

bool SearchBST(SOSTree *T, int key, SOSTree *S, SOSTree **p) {
        // p 用与在函数之间传递指针变量，因此使用二级指针
        // 默认没有两个相同的元素
        if (!T) {
            *p = S;
            return false;
        } else if (EQI(key, T->data)) {
            *p = T;
            return true;
        } else if (LTI(key, T->data)) return SearchBST(T->LChild, key, T, p);
        else return SearchBST(T->RChild, key, T, p);
    }

## 删除： ##

bool DelBST(SOSTree **T, SOSTree *P, int elem) {
        if (!*T) return false;
        if (EQI(elem, (**T).data)) {
            // 删除叶子结点
            if (!(**T).RChild && !(**T).LChild) {
            // 处理原二叉树只含有根节点的情况
                if (!P) *T = NULL;
                else if (P->LChild == *T) P->LChild = NULL;
                else if (P->RChild == *T) P->RChild = NULL;
                return true;
            }
            return DelBSTNode(T);
        } else if (LTI(elem, (**T).data)) return DelBST(&(**T).LChild, *T, elem);
        else return DelBST(&(**T).RChild, *T, elem);
    }
    
    bool DelBSTNode(SOSTree **p) {
        // 删除非叶子结点
        // 直接使用二级指针，直接对地址进行操作
        SOSTree *q, *s;
        if (!(*p)->RChild) {
            *p = (*p)->LChild;
            return true;
        } else if (!(*p)->LChild) {
            *p = (*p)->RChild;
            return true;
        } else {
            q = *p;
            s = (*p)->LChild;
            while (s->RChild) {
                q = s;
                s = s->RChild;
            }
            (*p)->data = s->data;
            if (q != *p) q->RChild = s->LChild;
            else q->LChild = s->LChild;
            return true;
        }
    }

## 主函数： ##

int main() {
        SOSTree *T;
        int data1[10] = {0, 7, 1, 2, 17, 13, 9, 4, 3, 5};
        int i;
        T = NULL;
        for (i = 0; i < 10; i++)
            InsertBST(&T, data1[i]);
        DelBST(&T, NULL, 4);
        free(T);
        return 0;