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

#include#includetypedef 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;
}

1、若左子树不为空，左子树上所有节点值小于 它根节点的值
2、若右子树不为空，右子树上所有节点值大于 它根节点的值
3、每个节点的左右子树也是二叉排序树

目的：提高查找、插入、删除关键字的速度（不是为了排序）
时间复杂度：由于查找性能取决于树的形态，所以在O（log2n）（二叉树的平均高度）~ O(n) （最坏情况：单链表）之间。
改进：AVL树（不断的修改树的形态） 链接: 二叉平衡树（AVL树）

查找不成功（不重复） ->插入

分为三种情况：
（1）为叶子结点 ：直接删除
（2）无左、右子树：删除结点，接上孩子即可
（3）左、右子树都有：找需要删除结点的左子树的最右结点（或右子树的最左结点）替换此节点。因为左子树的最右结点和右子树的最左结点最接近根节点，所以用它替换。再把此节点的右或左子树接到此节点的父亲结点上。

通过递归的方式比较找到结点
查找需要为插入做准备，因此函数变量里有个指针。

参考资料：《大话数据结构》
如果文章有问题，请给我留言哦，谢谢！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧