C语言数据结构二叉排序树的建立、插入、删除、查找操作（原理+完整代码）-Toy模板网

这篇具有很好参考价值的文章主要介绍了C语言数据结构二叉排序树的建立、插入、删除、查找操作（原理+完整代码）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

完整代码

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

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

//查找函数
//f指向T的parent,查找成功p指向该结点；不成功，返回访问的最后一个结点
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);
    }
}

//插入节点（创建树）
int insertBST(BiTree *T,int key)
{
    BiTree p,s;
    if(searchBST(*T,key,NULL,&p)==0)   //查找不成功，不存在相等的结点
    {
        s=(BiTree)malloc(sizeof(BiTNode));
        s->data=key;
        s->lchild=s->rchild=NULL;
        if(!p)
            *T=s;   //树为空，则s为根节点
        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)   //找到被删结点的左子树的最右结点
        {
            q=s; s=s->rchild;
        }
        (*p)->data = s->data;    //此时s为被删结点的左子树的最右结点
        if(q != *p)           //q为s 的父亲结点,此时q不重合p，也就是s不是p的右孩子
            q->rchild=s->lchild;
        else                         //此时q和p重合，s为p的右孩子
            q->lchild=s->lchild;
        free(s);
    }
    return 1;
}
//递归找到结点
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.插入节点 2.删除结点\n");
    int f;int key;
    scanf("%d",&f);
    if(f==1)
    {
        printf("请输入插入的数字\n");
        scanf("%d",&key);
        insertBST(&T,key);
        pre(T);
    }
    else
    {
        printf("请输入删除的数字\n");
        scanf("%d",&key);
        deleteBST(&T,key);
        pre(T);
    }
    
    return 0;
}