完整代碼

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

typedef struct binode
{
    int data;
    struct binode *lchild,*rchild;
}BiTNode,*BiTree;

//查找函數(shù)
//f指向T的parent,查找成功p指向該結(jié)點(diǎn)；不成功，返回訪問的最后一個(gè)結(jié)點(diǎn)
int searchBST(BiTree T,int key, BiTree f, BiTree *p)
{
    if(T==NULL)
    {
        *p= f;
        return 0;
    }
    else if(key == T->data)
    {
        *p=T;
        return 1;
    }
    else if(key < T ->data)
    {
        return searchBST(T->lchild, key, T,p);
    }
    else{
        return searchBST(T->rchild, key, T,p);
    }
}

//插入節(jié)點(diǎn)（創(chuàng)建樹）
int insertBST(BiTree *T,int key)
{
    BiTree p,s;
    if(searchBST(*T,key,NULL,&p)==0)   //查找不成功，不存在相等的結(jié)點(diǎn)
    {
        s=(BiTree)malloc(sizeof(BiTNode));
        s->data=key;
        s->lchild=s->rchild=NULL;
        if(!p)
            *T=s;   //樹為空，則s為根節(jié)點(diǎn)
        else if(key < p->data)
            p->lchild=s;
        else
            p->rchild=s;
        return 1;
    }
    else
        return 0;
}

//刪除
int Delete(BiTree *p)
{
    BiTree q,s;
    if((*p)->rchild ==NULL)  //只有左子樹
    {
        q=*p;
        *p=(*p)->lchild;
        free(q);
    }
    else if((*p)->lchild == NULL)   //只有右子樹
    {
        q=*p;
        *p=(*p)->rchild;
        free(q);
    }
    else   //左右子樹均不為空
    {
        q=*p;  s=(*p)->lchild;
        while (s->rchild)   //找到被刪結(jié)點(diǎn)的左子樹的最右結(jié)點(diǎn)
        {
            q=s; s=s->rchild;
        }
        (*p)->data = s->data;    //此時(shí)s為被刪結(jié)點(diǎn)的左子樹的最右結(jié)點(diǎn)
        if(q != *p)           //q為s 的父親結(jié)點(diǎn),此時(shí)q不重合p，也就是s不是p的右孩子
            q->rchild=s->lchild;
        else                         //此時(shí)q和p重合，s為p的右孩子
            q->lchild=s->lchild;
        free(s);
    }
    return 1;
}
//遞歸找到結(jié)點(diǎn)
int deleteBST(BiTree *T, int key)
{
    if(*T==NULL)
        return 0;
    else
    {
        if(key == (*T)->data)
        {
            Delete(T);
            return 1;
        }
        else if(key <(*T)->data)
            return deleteBST(&(*T)->lchild,key);
        else
            return deleteBST(&(*T)->rchild,key);
    }
}

void pre(BiTree T)
{
    if(T)
    {
        printf("%d ",T->data);
        pre(T->lchild);
        pre(T->rchild);
    }
}
int main()
{
    BiTree T=NULL;
    int a[15]={3,6,1,8,2,7,4,5,66};
    int i=0;
    while(a[i]!='\0')
    {
        insertBST(&T,a[i++]);
    }
    pre(T);
    printf("\n1.插入節(jié)點(diǎn) 2.刪除結(jié)點(diǎn)\n");
    int f;int key;
    scanf("%d",&f);
    if(f==1)
    {
        printf("請(qǐng)輸入插入的數(shù)字\n");
        scanf("%d",&key);
        insertBST(&T,key);
        pre(T);
    }
    else
    {
        printf("請(qǐng)輸入刪除的數(shù)字\n");
        scanf("%d",&key);
        deleteBST(&T,key);
        pre(T);
    }
    
    return 0;
}

二叉查找樹的原理

1、若左子樹不為空，左子樹上所有節(jié)點(diǎn)值小于 它根節(jié)點(diǎn)的值
2、若右子樹不為空，右子樹上所有節(jié)點(diǎn)值大于 它根節(jié)點(diǎn)的值
3、每個(gè)節(jié)點(diǎn)的左右子樹也是二叉排序樹

目的：提高查找、插入、刪除關(guān)鍵字的速度（不是為了排序）
時(shí)間復(fù)雜度：由于查找性能取決于樹的形態(tài)，所以在O（log2n）（二叉樹的平均高度）~ O(n) （最壞情況：?jiǎn)捂湵恚┲g。
二叉排序樹的深度、性能不穩(wěn)定
改進(jìn)：AVL樹（不斷的修改樹的形態(tài)） 鏈接: 二叉平衡樹（AVL樹）

插入

查找不成功（不重復(fù)） -> 插入

刪除

分為三種情況：
（1）為葉子結(jié)點(diǎn) ：直接刪除
（2）無(wú)左、右子樹：刪除結(jié)點(diǎn)，接上孩子即可
（3）左、右子樹都有：找需要?jiǎng)h除結(jié)點(diǎn)的左子樹的最右結(jié)點(diǎn)（或右子樹的最左結(jié)點(diǎn)）替換此節(jié)點(diǎn)。因?yàn)樽笞訕涞淖钣医Y(jié)點(diǎn)和右子樹的最左結(jié)點(diǎn)最接近根節(jié)點(diǎn)，所以用它替換。再把此節(jié)點(diǎn)的右或左子樹接到此節(jié)點(diǎn)的父親結(jié)點(diǎn)上。

查找

通過遞歸的方式比較找到結(jié)點(diǎn)
查找需要為插入做準(zhǔn)備，因此函數(shù)變量里有個(gè)指針。

參考資料：《大話數(shù)據(jù)結(jié)構(gòu)》
如果文章有問題，請(qǐng)給我留言哦，謝謝！文章來源地址http://www.zghlxwxcb.cn/news/detail-490096.html

到了這里，關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)二叉排序樹的建立、插入、刪除、查找操作（原理+完整代碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！