c语言实现二叉树查找、增加、删除代码

代码语言:c

所属分类:算法

代码描述:c语言实现二叉树查找、增加、删除代码

代码标签: 二叉树 查找 增加 删除

下面为部分代码预览,完整代码请点击下载或在bfwstudio webide中打开

#include"stdio.h"
#include"malloc.h"

typedef int elemtype;
typedef struct btnode
{
    elemtype data;/*关键字域*/
    struct btnode *lchild,*rchild;
}
btnode,*bitree;
int searchBST(bitree t, elemtype key, bitree f,bitree *p)
/*递归查找二叉排序树t是否存在key,指针f指向t的双亲,其初始调用值为NULL,若查找成功,
则指针p指向该数据元素结点并返回1,否则指针p指向查找路径上访问的最后一个结点并返回0*/
{
    if (!t){ *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, elemtype key)
/*当二叉排序树T中不存在关键字等于key的数据元素时,插入key返回二叉排序树的根结点。*/
{
    bitree p,s;
    if (!searchBST(*t,key,NULL,&p))                         /*查找不成功*/
    {
        s=(bitree)malloc(sizeof(btnode));
        s->data=key;
        s->lchild = s->rchild = NULL;
        if (!p) *t=s;        /*插入s为新的根结点*/
        else  if ( key< p->data)
            p->lchild=s;     /*插入s为左孩子*/
        else
            p->rchild=s;     /*插入s为右孩子*/
        return 1;
      }
    else
        return 0;
}
void inorder(bitree bt)   //中序遍历
{
    if(bt==NULL)return;
    else{
        inorder(bt->lchild);
        printf("%d ",bt->data);
        inorder(bt->rchild);
    }
}
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-&g.........完整代码请登录后点击上方下载按钮下载查看

网友评论0