二叉树的操作

//二叉树的一些操作


#include
#include

typedef struct link
{
    unsigned char item;
    struct link *l,*r;
}LINK;

static LINK *mknode(unsigned char item)//生成结点
{
    LINK *p=malloc(sizeof *p);
    p->item=item;
    p->l=p->r=NULL;
    return p;
}

LINK *init(unsigned char VLR[],unsigned char LVR[],int n)//根据前序和中序生成二叉树
{
    LINK *t;
    int k;
    if(n<=0)
    {
        return NULL;
    }

    for(k=0;VLR[0]!=LVR[k];k++);
    t=mknode(VLR[0]);
    t->l=init(VLR+1,LVR,k);
    t->r=init(VLR+1+k,LVR+1+k,n-k-1);

    return t;
}

LINK *init1(unsigned char LRV[],unsigned char LVR[],int n)//根据中序和后序生成而二叉树
{
    LINK *t;
    int k;
    if(n<=0)
    {
        return NULL;
    }
    
    for(k=0;LRV[n-1]!=LVR[k];k++);
    t=mknode(LRV[n-1]);
    t->l=init1(LRV,LVR,k);
    t->r=init1(LRV+k,LVR+k+1,n-k-1);

    return t;

}

void pre_order(LINK *t)//前序
{
    if(!t)
    {
        return ;
    }
    printf("%d ",t->item);

    pre_order(t->l);
    pre_order(t->r);

}

void in_order(LINK *t)//中序
{
    if(!t)
    {
        return ;
    }

    in_order(t->l);
    printf("%d ",t->item);
    in_order(t->r);
}

void post_order(LINK *t)//后序
{
    if(!t)
    {
        return ;
    }

    post_order(t->l);
    post_order(t->r);
    printf("%d ",t->item);
}

LINK *search(LINK *t,unsigned char item)//查找
{
    if(!t)
    {
        return NULL;

    }
    if(t->item==item)
    {
        return t;
    }
    else if(t->item>item)
    {
        return search(t->l,item);
    }
    else if(t->item     {
        return search(t->r,item);
    }
}

LINK *insert(LINK *t,unsigned char item)//插入
{
    if(t==NULL)
    {
        return mknode(item);
    }
    if(t->item==item)
    {
        printf("node %d exit\n",item);
    }
    else if(t->item>item)
    {
        t->l=insert(t->l,item);
    }
    else if(t->item     {
        t->r=insert(t->r,item);
    }

    return t;
}

LINK *insert1(LINK **t,unsigned char item)//另一种插入
{
    if(*t==NULL)
    {
        *t=mknode(item);
    }
    if((*t)->item==item)
    {
        printf("node %d exit\n",item);
    }
    else if((*t)->item>item)
    {
        insert1(&((*t)->l),item);
    }
    else if((*t)->item     {
        insert1(&((*t)->r),item);
    }
}

LINK *delete(LINK *t,unsigned char key)//删除
{
    LINK *p;
    if(!t)
    {
        return NULL;
    }
    if(t->item>key)
    {
        t->l=delete(t->l,key);
    }
    else if(t->item     {
        t->r=delete(t->r,key);
    }
    else
    {
        if(t->l==NULL&&t->r==NULL)
        {
            free(t);
            t=NULL;
        }
        else if(t->l)
        {
            for(p=t->l;p->r;p=p->r);
            t->item=p->item;
            t->l=delete(t->l,t->item);
        }
        else if(t->r)
        {
            for(p=t->r;p->l;p=p->l);
            t->item=p->item;
            t->r=delete(t->r,t->item);
        }
    }

    return t;

}

LINK *delete1(LINK **t,unsigned char item)//先是左支极右，如果没有左支就右之极左
{
    LINK *p,*q=NULL;
    if(*t==NULL)
    {
        return ;
    }
    if((*t)->item>item)
    {
        delete1(&((*t)->l),item);
    }
    else if((*t)->item     {
        delete1(&((*t)->r),item);
    }
    else if((*t)->item==item)
    {
        if((*t)->l==NULL&&(*t)->r==NULL)
        {
            free(*t);
            *t=NULL;
            return ;
        }
        else if((*t)->l)
        {
            for(q=*t,p=(*t)->l;p->r;q=p,p=p->r);
            (*t)->item=p->item;
            if(q==*t)
            {
                delete1(&((*t)->l),(*t)->item);
            }
            else
            {
                delete1(&(q->r),p->item);
            }
        }
        else if((*t)->r)


        {
            for(q=*t,p=(*t)->r;p->l;q=p,p=p->l);
            (*t)->item=p->item;
            if(q==*t)
            {
                delete1(&((*t)->r),(*t)->item);
            }
            else
            {
                delete1(&(q->l),p->item);
            }
        }
    }

}
int depth(LINK *t)//层数
{
    int dl,dr;
    if(!t)
    {
        return 0;
    }

    dl=depth(t->l);
    dr=depth(t->r);

    return 1+(dl>dr?dl:dr);
}

int count(LINK *t)//结点数
{
    if(!t)
    {
        return 0;
    }

    return 1+count(t->l)+count(t->r);
}

void destory(LINK *t)//
{
    if(!t)
    {
        return;
    }

    destory(t->l);
    destory(t->r);
    free(t);
}
int main(void)
{
    LINK *p;

    unsigned char pre_seq[]={4,2,1,3,5,6};
    unsigned char in_seq[]={1,2,3,4,5,6};
    unsigned char post_seq[]={1,3,2,6,5,4};
#if 0
    LINK *root=init(pre_seq,in_seq,6);
    post_order(root);
    putchar('\n');
#endif
    LINK *root=init1(post_seq,in_seq,6);
    p=delete(root,5);
    pre_order(root);
    putchar('\n');

    p=insert(root,7);
    in_order(root);
    putchar('\n');

    p=search(root,3);
    printf("%d\n",p->item);

    printf("%d %d\n",count(root),depth(root));

    destory(root);
    
    return 0;

}