数据结构，树自用

guhusf

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#define maxsize 100

typedef struct node
{
        char ch[20];
        struct node *fch,*xd;

}node,*tree;

typedef struct queue
{
        int queuesize;
        int rear;
        int front;
        tree data[maxsize];
}queue;

typedef struct 
{

 char s[20];

}elemtype;

typedef struct stack
{
        int top;
        elemtype data[maxsize];
        int stacksize;        
        
}stack;



int initqueue(queue *Q)
{
        Q->front=Q->rear=0;
        Q->queuesize=maxsize;        
        
}//初始化队列 

int enqueue(queue *Q,tree e)
{
        if((Q->rear+1)%Q->queuesize==Q->front)
        return 0;
        Q->data[Q->rear]=e;
        Q->rear=(Q->rear+1)%Q->queuesize;
        
}//进队 

int dequeue(queue *Q,tree *e)
{
        if(Q->front==Q->rear)
        return 0;
        *e=Q->data[Q->front];
        Q->front=(Q->front+1)%Q->queuesize;
        
}//出队 

int gettop(queue Q,tree *s)
{
        if(Q.front==Q.rear)
        return 0;
        *s=Q.data[Q.front];

}//得到队头 


int menu()
{
        int i;
        while(1)
        {
                system("cls");
                printf("**********************欢迎进入树的基本操作!*********************\n");
                printf ("1.读边法孩子兄弟链表创建树\n2.通过给定值查找结点，返回指针\n");
                printf("3.插入结点到指定位置\n4.删除以某节点为根的子树\n");
                printf("5.凹入表法输出树\n6.输出根到叶子结点的路径\n");
                printf("7.退出\n");
                scanf("%d",&i);
                getchar();
                if(i<1||i>7)
                {
                        printf("输入有误！\n");
                        getch();
                }
                else
                {
                return i;
                }
        }

        
}//菜单 

int creat(tree *T)
{
        char fa[20],ch[20];
        queue Q;
        tree p,s,r;
        initqueue(&Q);
        *T=NULL;
        printf("请输入双亲元素:\n");                
        scanf("%s",fa);
        printf("孩子元素:\n");
    scanf("%s",ch);
        while(strcmp(ch,"#")!=0)
        {
                p=(tree)malloc(sizeof(node));
                strcpy(p->ch,ch);
                p->fch=p->xd=NULL;
                enqueue(&Q,p);
                if(strcmp(fa,"#")==0)
                *T=p;
                else
                {
                        gettop(Q,&s);
                        while(strcmp(s->ch,fa)!=0)
                        {
                                dequeue(&Q,&s);
                                gettop(Q,&s);
                        }
                        if(s->fch==NULL)
                        {
                                s->fch=p;
                                r=p;
                        }
                        else
                        {
                                r->xd=p;
                                r=p;
                        }
                        
                }
                printf("请输入双亲元素:\n");                
                scanf("%s",fa);
                printf("孩子元素:\n");
            scanf("%s",ch);
        }
        
}


tree cz(tree T,char a[20],tree *p)
{
        if(T)
        {
                if(strcmp(a,T->ch)==0)
                {
                        *p=T;
                        return *p;
                }
                cz(T->fch,a,p);
                cz(T->xd,a,p);
                
        }
        
}//树的结点查找 


int insert(tree *T)
{
        char fa[20],ch[20];
        tree p=NULL,q,s;
        printf("请输入你想要插入的结点的双亲元素:\n");
        scanf("%s",fa);
        printf("孩子元素:\n");
        scanf("%s",ch);
        cz(*T,fa,&p);
        if(p)
        {
                s=(tree)malloc(sizeof(node));
                strcpy(s->ch,ch);
                s->fch=s->xd=NULL;
                if(p->fch==NULL)
                p->fch=s;
                else
                {
                        q=p->fch;
                        while(q->xd!=NULL)
                        q=q->xd;
                        q->xd=s;
                 } 
                return 1;
        }
        
}//树的插入 


void postdeltree(tree T)
{
        if(T)
        {
                postdeltree(T->fch);
                postdeltree(T->xd);
                free(T);
                
        } 
        
        
}



void Delete(tree p,tree f)
{
        
        if(f->fch==p)
        {
                f->fch=p->xd;
                p->xd=NULL;
                postdeltree(p);
        }
        if(f->xd==p)
        {
                f->xd=p->xd;
                p->xd=NULL;
                postdeltree(p);        
        }
        
        
}



void deletetree(tree *T,char fa[20],char ch[20])
{
        tree pfa=NULL,pch=NULL;
        if(strcmp(fa,"#")==0)
        {
                postdeltree(*T);
                *T=NULL;
                return;
                
        }
        else
        {
        cz(*T,fa,&pfa);
        cz(*T,ch,&pch);
        if(pfa==NULL||pch==NULL)
        {
                printf("数据有误，不能删除!\n");
                return;
                
        }
        else
        {
                if(pfa->fch!=pch)
                {
                        pfa=pfa->fch;
                        while(pfa)
                        {
                                if(pfa->xd==pch)
                                break;
                                pfa=pfa->xd;
                        }
                        
                }
        Delete(pch,pfa);
                        
        }        
                
        }
        
}



void distree(tree T,int level)
{
        int len,i,n,k;
        if(T)
        {
                len=strlen(T->ch);
                for(i=0;i<level;i++)
                putchar(' ');
                printf("%s",T->ch);
                putchar('+');
                for(k=i+len;k<70;k++)
                putchar('-');
                putchar('\n');
                distree(T->fch,level+4);
                distree(T->xd,level);
                
        }
        
 }//凹入法 


int initstack(stack *S)
{
        S->top=-1;
        S->stacksize=maxsize;
    return 1;
                
}//初始化栈 

int printstack(stack *S)
{
        int k;
        if(S->top==-1)
        {
        printf("栈空!\n");
        return 0;
    }
        for(k=0;k<=S->top;k++)
        {
        printf("%s",S->data[k].s);
        printf(" ");
        }
        printf("\n");
        return 1;        
        
 } //遍历 

int pop(stack *S)
{
        if(S->top==-1)
        return 0;
        else
        S->top--;
        return 1;
        
}//出栈 

int push(stack *S,char e[])
{
        if(S->top==S->stacksize-1)
        {
        return 0;
    }
        else
        {
                S->top++;
                strcpy(S->data[S->top].s,e);
            return 1;
            
        }         
        
} //进栈 

void  pathtree(tree T,stack *S)
{
        while(T)
        {
                push(S,T->ch);
                if(!T->fch)
                printstack(S);
                else
                pathtree(T->fch,S);
                pop(S);
                T=T->xd;
        }
        
}//路径 



int main()
{
        int i;
        char a[20],b[20];
        tree T,p;
        stack S;
        while(1)
        {
                i=menu();
                switch(i)
                {
                        case 1:printf("欢迎进入读边法孩子兄弟链表创建树的操作\n");
                               creat(&T);
                               printf("操作成功!\n");
                                   printf("按任意键继续!\n");
                                   getch();
                                   break;
                                   
                        case 2:printf("欢迎进入通过给定值查找结点，返回指针操作\n");
                               printf("请输入你想要查找的结点的元素:\n");
                               scanf("%s",a);
                                   cz(T,a,&p);
                                   printf("该结点的孩子元素为:%s,兄弟元素为:%s\n",p->fch->ch,p->xd->ch);
                                   printf("操作成功!\n");
                                   printf("按任意键继续!\n");
                                   getch();
                                   break;
                                   
                        case 3:printf("欢迎进入插入结点到指定位置操作\n");
                               insert(&T);
                               printf("操作成功!\n");
                               printf("按任意键继续!\n");
                                   getch();
                                   break;
                                           
                        case 4:printf("欢迎进入删除以某节点为根的子树操作\n");
                               printf("请输入你想要删除的结点的双亲元素:\n");
                               scanf("%s",a);
                               printf("孩子元素:\n");
                               scanf("%s",b);
                               deletetree(&T,a,b);
                               printf("操作成功!\n");
                               printf("按任意键继续!\n");
                                   getch();
                                   break;
                                  
                        case 5:printf("欢迎进入凹入表法输出树的操作\n");
                               distree(T,1);
                               printf("操作成功!\n");
                               printf("按任意键继续!\n");
                                   getch();
                                   break;
                        
                        case 6:printf("欢迎进入输出根到叶子结点的路径\n");                              
                                    initstack(&S);
                                   pathtree(T,&S); 
                               printf("操作成功!\n");
                               printf("按任意键继续!\n");
                                   getch();
                                   break;
                                   
                    case 7:exit(7);                              
                                              
                                        
                }
        }
                
}