以三元组(F,C,L/R)的形式输入一颗二叉树的诸边,其中F表示双亲结点,C为孩子节点,L/R表示C为F的左孩子或右孩子,且输入的三元组序列中,c是按层次顺序出现。
节点为字符类型,且当F=^时C为根节点,若C也为^,表示输入结束。
输出为该二叉树的广义表达式。
#include <stdio.h>
#include <malloc.h>
#define maxsize 50
typedef struct Bnode
{
char data;
struct Bnode *Lchild, *Rchild;
}BTnode, *BTptr;
typedef struct
{
BTptr code[maxsize];
int front,rear,last;
}squeue, *squlink;
int PrintBT(BTptr T)
{
if(T!=NULL)
{
printf("%c",T->data);
if(T->Lchild==NULL && T->Rchild==NULL)
return 0;
else
{
printf("(");
PrintBT(T->Lchild);
printf(",");
PrintBT(T->Rchild);
printf(")");
}
}
else
return 0;
}
int main()
{
BTptr bt,p,q;
squlink sq;
bt=(BTptr)malloc(sizeof(BTnode));
sq=(squlink)malloc(sizeof(squeue));
bt->Lchild=NULL;
bt->Rchild=NULL;
sq->front=0;
sq->rear=0;
sq->last=0;
char F, C, LR;
scanf("%c%c%c",&F,&C,&LR);
if(F=='^')
bt->data=C;
else
return 0;
sq->code[sq->rear]=bt;
sq->rear++;
sq->last++;
scanf("%c%c%c",&F,&C,&LR);
int i;
while(C>='A' && C<='Z')
{
p=(BTptr)malloc(sizeof(BTnode));
p->data=C;
p->Lchild=NULL;
p->Rchild=NULL;
for(i=sq->front;i<=sq->rear;i++)
{
if(sq->code[i]->data==C)
break;
}
if(i<=sq->rear)
{
q=sq->code[i];
sq->code[++(sq->last)]=p;
if(LR=='L')
q->Lchild=p;
else
q->Rchild=p;
}
else
{
sq->front=sq->rear+1;
sq->rear=sq->last;
for(i=sq->front;i<=sq->rear;i++)
{
if(sq->code[i]->data==C)
break;
}
if(i<=sq->rear)
{
q=sq->code[i];
sq->code[++(sq->last)]=p;
if(LR=='L')
q->Lchild=p;
else
q->Rchild=p;
}
else
return 0;
}
scanf("%c%c%c",&F,&C,&LR);
}
PrintBT(bt);
}