|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- #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);
-
-
- }
- }
-
- }
复制代码 |
|