3tree.c

c语言实现的数据结构中二叉树的应用,包括二叉树结点的插入,删除,查询等

#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <conio.h>
#include <bios.h>
#define maxlength 100
typedef struct Btree{
    int data;
    struct Btree *lchild;
    struct Btree *rchild;
}Bnode;
Bnode *T;
int i=1,j;
int Create_Btree(Bnode *T)
{
    int e;
    char ch;
    printf("input data:\n");
    scanf("%d",&e);
    T->lchild=NULL;
    T->rchild=NULL;
    T->data=e;       /*生成根结点*/
    printf("%d want a left child?yes or no?\n",i);
    ch=getch();
    if(ch!='n'&&ch!='N')
    {
        i=2*i;
        T->lchild=(Bnode*)malloc(sizeof(Bnode));
        Create_Btree(T->lchild); /*创建左子树*/
    }
    printf("%d want a right child?yes or no?\n",i);
    ch=getch();
    if(ch!='n'&&ch!='N')
    {
        i=2*i+1;
        T->rchild=(Bnode*)malloc(sizeof(Bnode));
        Create_Btree(T->rchild); /*创建右子树*/
    }
    else
    {
        if(i%2) i=i/4;
        else    i=i/2;
    }
    return (1);
}
/*------------------------CreateCreate_Btree---------------*/

int Depth_Btree(Bnode *T)
{
    int e,d;
    if(!T)  e=d=0;
    else
    {
        e=Depth_Btree(T->lchild);
        d=Depth_Btree(T->rchild);
    }
    if(e<d)e=d;
    return (e+1);
}
/*------------------------Depth_Btree----------------*/

int Pre_order(Bnode *T)
{
    if(T)
    {
        printf("%d\n",T->data);
        Pre_order(T->lchild);
        Pre_order(T->rchild);
    }
    return (1);
}
/*--------------------Pre_order-----------------------*/



int In_order(Bnode *T)
{
    if(T)
    {
        In_order(T->lchild);
        printf("%d\n",T->data);
        In_order(T->rchild);
    }
    return (1);

}
/*-------------------------In_order-----------*/
int Post_order(Bnode *T)
{
    if(T)
    {
        Post_order(T->lchild);
        Post_order(T->rchild);
        printf("%d\n",T->data);
    }
    return(1);
}
/*--------------------------Post_order-------------------*/
int leaf0(Bnode *T)
{
    int e;
    if(!T)  return(0);
    if(!T->lchild&&!T->rchild)  e=1;
    else
    {
        e=leaf0(T->lchild);
        e+=leaf0(T->rchild);
    }
    return (e);
}
/*------------------------leaf0-------------------*/
int leaf1(Bnode *T)
{
    int e;
    if(!T) return(0);
    if((!T->lchild&&T->rchild)||(T->lchild&&!T->rchild))  e=1;
    else e=0;
    e+=leaf1(T->lchild);
    e+=leaf1(T->rchild);
    return (e);
}
/*------------------leaf1--------------------------*/
int leaf2(Bnode *T)
{
    int e;
    if(!T)  return(0);
    if(T->lchild&&T->rchild)  e=1;
    else e=0;
    e+=leaf2(T->lchild);
    e+=leaf2(T->rchild);
    return (e);
}
/*------------------------leaf2---------------------------*/
void Midorder(Bnode *T)
{
    Bnode *st[maxlength+1];
    int top=0;
    do            
    {
        while(T)
        {
             if(top==maxlength) exit(-1);
             st[++top]=T;
             T=T->lchild;
        }

        if (top)
        {
            T=st[top--];
            printf("%d\n",T->data);
            T=T->rchild;
        }
   }while(top||T);
 }

/*----------------------midorder---------------------*/
void preorder1(Bnode *T)
{
    Bnode *st[maxlength+1];
    int top=0;
    do
    {
        while(T)
        {
            if(top==maxlength) exit(-1);
            st[++top]=T;
            printf("%d\n",T->data);
            T=T->lchild;
        }
        if(top)
        {
            T=st[top--];
            T=T->rchild;
        }
    }while(top||T);
}
/*----------------------- preorder1(Bnode *T)---------------------------*/

    
void postorder1(Bnode *T)
{
    Bnode *st[maxlength+1];
    Bnode *st1[maxlength+1];
    Bnode *s,*q;
    int top=0;
    int top1=0;
    s=NULL;
    do
    {
        while(T)
        {
            if(top==maxlength) exit(-1);
            st[++top]=T;
            T=T->lchild;
        }
        if(top)
        {
            T=st[top--];
            if(T->rchild==NULL) printf("%d\n",T->data);
            else
            {
                st1[++top1]=T;
                s=T;
            }
            if(T==s->rchild)
            {
                printf("%d\n",s->data);
                s=st1[--top1];
            }
    

            T=T->rchild;
        }
    }while(top||T);
    while(top1!=0)
    {
        printf("%d\n",s->data);
        s=st1[--top1];
    }
    
}
/*----------------------- postorder1(Bnode *T)---------------------------*/
    

void levorder(Bnode *T)
{
    Bnode *sq[maxlength+1];
    int head=0,tail=0;
    if(T!=NULL)
    {
        sq[++tail]=T;
        printf("%d\n",T->data);
    }
    else exit(0);
    while(head!=tail)
    {
        if(tail==maxlength) exit(-1);
        T=sq[++head];
        if(T->lchild!=NULL)
        {
            printf("%d\n",T->lchild->data);
            sq[++tail]=T->lchild;
        }
        if(T->rchild!=NULL)
        {
            printf("%d\n",T->rchild->data);
            sq[++tail]=T->rchild;
        }
    }
}
/*-------------------lelorder----------------------*/


int xchange(Bnode *T)
{
    Bnode *s;
    if(!T) return (0);
    if(!T->lchild&&!T->rchild) return (1);
   else
    {
        s=T->lchild;
        T->lchild=T->rchild;
        T->rchild=s;
        xchange(T->lchild);
        xchange(T->rchild);
    }
    return (1);
}
/*---------------------xchange--------------------*/



int leaf_0(Bnode *T)
{
    Bnode *st[maxlength+1];
    int top=0,k=0;
    do            
    {
        while(T)
        {
             if(top==maxlength) exit(-1);
             st[++top]=T;
             T=T->lchild;
        }

        if (top)
        {
            T=st[top--];
            if(!T->rchild&&!T->lchild)
                k++;
            T=T->rchild;
        }
   }while(top||T);
   return (k);
 }
/*----------------------leaf_0---------------------*/

int leaf_1(Bnode *T)
{
    Bnode *st[maxlength+1];
    int top=0,k=0;
    do            
    {
        while(T)
        {
             if(top==maxlength) exit(-1);
             st[++top]=T;
             T=T->lchild;
        }

        if (top)
        {
            T=st[top--];
            if((T->rchild&&!T->lchild)||(!T->rchild&&T->lchild))
                k++;
            T=T->rchild;
        }
   }while(top||T);
   return (k);
 }
/*----------------------leaf_1---------------------*/

int leaf_2(Bnode *T)
{
    Bnode *st[maxlength+1];
    int top=0,k=0;
    do            
    {
        while(T)
        {
             if(top==maxlength) exit(-1);
             st[++top]=T;
             T=T->lchild;
        }

        if (top)
        {
            T=st[top--];
            if(T->rchild&&T->lchild)
                k++;
            T=T->rchild;
        }
   }while(top||T);
   return (k);
 }
/*----------------------leaf_2---------------------*/



int nodes(Bnode *T)
{
    int e;
    if(!T)  return(0);
    if(!T->rchild&&!T->lchild)  e=1;
    else
    {
        e=nodes(T->lchild)+1;
        e+=nodes(T->rchild);
    }
    return (e);
}
/*----------------------nodes-----------------------*/

void full()
{
    int e;
    if(nodes(T)==((2<<(Depth_Btree(T)-2))-1))
        printf("Yes,it is a full tree\n");
    else
        printf("No,it is not a full tree\n");
    getch();
}
/*-----------------------full---------------------------*/
void savetree(Bnode *T)
{
    FILE *fp;
    char fname[20];
    Bnode *st[maxlength+1];
    int top=0;
    if(T==NULL)
    {   clrscr();
        printf("There is no tree for save!exit");
        getch();
        return;
    }
    printf("please input the file name you want to save :\n");
    scanf("%s",fname);
    if((fp=fopen(fname,"wb"))==NULL)
    {
        printf("Can not save the file!\n");
        return;
    }
    printf("\nsaving file...\n");
    do
    {
        while(T)
        {
            if(top==maxlength) exit(-1);
            st[++top]=T;
            fwrite(T,sizeof(Bnode),1,fp);
            T=T->lchild;
        }
        if(top)
        {
            T=st[top--];
            T=T->rchild;
        }
    }while(top||T);
    fclose(fp);
    printf("the tree have been saved in the file ,press any key to  contune.\n");
    getch();
}
/*----------------------------savetree--------------------------*/


Bnode **loadtree(void)
{   
    FILE *fp;
    char fname[20];
    Bnode *t;
    Bnode *st[maxlength+1];
    Bnode *sq[maxlength+1];
    int top=0;
    int top1=0;
    t=(Bnode*)malloc(sizeof(Bnode));
    printf("Please input the file name you want to load:\n");
    scanf("%s",fname);
    if((fp=fopen(fname,"rb"))==NULL)
    {
        printf("Can not open the file!Pleade choose again!\n");
        getch();
        return NULL;
    }
    printf("\nloading...\n");

    while(!feof(fp))
    {
        if(1!=fread(t,sizeof(Bnode),1,fp)) break;
        if(top==maxlength) exit(-1);
        st[++top]=t;
        sq[++top1]=t;
        while((t->lchild!=NULL)&&(!feof(fp)))
        {
            t->lchild=(Bnode*)malloc(sizeof(Bnode));
            t=t->lchild;
            if(1!=fread(t,sizeof(Bnode),1,fp)) break;
            if(top==maxlength) exit(-1);
            st[++top]=t;
            sq[++top1]=t;
        }
       if(top)
        {
            t=st[top--];
            while((t->rchild==NULL)&&top!=0)
                t=st[top--];
            if(t->rchild!=NULL)
            {
                t->rchild=(Bnode*)malloc(sizeof(Bnode));
                t=t->rchild;
            }
            else t->rchild=NULL;
        }
    }
    fclose(fp);
    printf("the tree has been load,press any key to return!\n");
    getch();
    return(sq[1]);
}
/*-----------------------------load--------------------------*/

void mainmenu()
{
    window(1,1,80,25);
    clrscr();
    printf("Create a tree --1!\r\n");
    cprintf("Recursive preorder --2!\r\n");
    cprintf("Recursive midorder --3!\r\n");
    cprintf("Recursive postorder --4!\r\n");
    cprintf("Normal preorder --5!\r\n");
    cprintf("Normal midorder --6!\r\n");
    cprintf("Normal postorder --7!\r\n");
    cprintf("Recursive count 0-degree leaves --8!\r\n");
    cprintf("Recursive count 1-degree leaves --9!\r\n");
    cprintf("Recursive count 2-degrees leaves --10!\r\n");
    cprintf("Normal count 0-degree leaves --11!\r\n");
    cprintf("Normal count 1-degree leaves --12!\r\n");
    cprintf("Normal count 2-degrees leaves --13!\r\n");
    cprintf("All over the tree by levels --14!\r\n");
    cprintf("Depth of the tree --15!\r\n");
    cprintf("Jadge if the tree is full  --16!\r\n");
    cprintf("Xchange the lchild and rchild --17!\r\n");
    cprintf("Midorder after the xchange  --18!\r\n");
    cprintf("Save the tree  --19!\r\n");
    cprintf("Load the tree  --20!\r\n");
    cprintf("-----------------Choose the operation with the number----------\r\n");
    cprintf("---------------------------press 0 to exit !-------------------\r\n");
}

void main()
{
    int a;
    T=(Bnode*)malloc(sizeof(Bnode));
    mainmenu();
    scanf("%d",&a);
    clrscr();
    while(a!=0)
    {

        switch(a)
        {
            case 1:Create_Btree(T);i=1;printf("\ncreate over!\n");getch();mainmenu();break;
            case 2:Pre_order(T);printf("\nRecursive pre_order over!\n");getch();mainmenu();break;
            case 3:In_order(T);printf("\nRecursive in_order over!\n");getch();mainmenu();break;
            case 4:Post_order(T);printf("\nRecursive post_order over!\n");getch();mainmenu();break;
            case 5:preorder1(T);printf("\nNormal preorder over!\n");getch();mainmenu();break;
            case 6:Midorder(T);printf("\nNormal midorder over!\n");getch();mainmenu();break;
            case 7:postorder1(T);printf("\nNormal postorder over!\n");getch();mainmenu();break;
            case 8:clrscr();printf("\nRecursive count 0-degree leaves over!\n");
                    printf("\nthe number of the 0-leaf-nodes is %d\n",leaf0(T));getch();mainmenu();break;
            case 9:clrscr();printf("\nRecursive count 1-degree leaves over!\n");
                    printf("\nthe number of the 1-leaf-nodes is %d\n",leaf1(T));getch();mainmenu();break;
            case 10:leaf2(T);printf("\nRecursive count 2-degree leaves over!\n");
                    printf("\nthe number of the 2-leaves-nodes is %d\n",leaf2(T));getch();mainmenu();break;
            case 11:clrscr();printf("\nNormal count 0-degree leaves over!\n");
                    printf("\nthe number of the 0-leaf-nodes is %d\n",leaf_0(T));getch();mainmenu();break;
            case 12:clrscr();printf("\nNormal count 1-degree leaves over!\n");
                    printf("\nthe number of the 1-leaf-nodes is %d\n",leaf_1(T));getch();mainmenu();break;
            case 13:clrscr();printf("\nNormal count 2-degree leaves over!\n");
                    printf("\nthe number of the 2-leaves-nodes is %d\n",leaf_2(T));getch();mainmenu();break;
            case 14:levorder(T);printf("\nLevle order tree over!\n");getch();mainmenu();break;
            case 16:full();mainmenu();break;
            case 15:printf("\nthe depth of the tree is %d\n",(Depth_Btree(T)-1));getch();mainmenu();break;
            case 17:xchange(T);printf("\nXchange the lchild and rchild over!\n");getch();mainmenu();break;
            case 18:In_order(T);printf("\nMidorder after the xchange over!\n");getch();mainmenu();break;
            case 19:savetree(T);mainmenu();break;
            case 20:T=loadtree();mainmenu();break;
            default:break;
        }
        scanf("%d",&a);
        clrscr();
    }
}