数据结构，树自用
#include<stdio.h>#include<stdlib.h>
#include<string.h>
#include<conio.h>
#define maxsize 100
typedef struct node
{
char ch;
struct node *fch,*xd;
}node,*tree;
typedef struct queue
{
int queuesize;
int rear;
int front;
tree data;
}queue;
typedef struct
{
char s;
}elemtype;
typedef struct stack
{
int top;
elemtype data;
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=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+1)%Q->queuesize;
}//出队
int gettop(queue Q,tree *s)
{
if(Q.front==Q.rear)
return 0;
*s=Q.data;
}//得到队头
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,ch;
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,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,ch;
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,char ch)
{
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.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,e);
return 1;
}
} //进栈
voidpathtree(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,b;
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);
}
}
}
页:
[1]