题目描述
用二叉树的带虚结点表示的前序遍历序可以唯一的确定一棵二叉树。
输入
输入包含多组数据。
每行是一棵二叉树的带虚结点(#)表示的前序遍历序串,长度不超过2000。每个结点为一个字符。
输出
对每行输入,输出对应二叉树的中序遍历序(不含虚结点)、后序遍历序(不含虚结点)和层次遍历序(不含虚结点)。
每棵二叉树的输出占一行,中序遍历序、后序遍历序和层次遍历序之间用一个空格隔开。
样例输入
ab##c##
#
ab###
样例输出
bac bca abc
ba ba ab
参考代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tree
{
char n;
struct tree *lc, *rc;
}
bnode;
int flag;
int i;
char str[100];
bnode *Createtree();
void mid( bnode *b );
void last( bnode *b );
void LevleOrder(bnode *T);
int main()
{
bnode *p;
while( scanf("%s", str) != EOF )
{
i = 0;
p = Createtree();
if( p != NULL )
{
mid(p);
printf(" ");
last(p);
printf(" ");
LevleOrder(p);
memset(str,0, sizeof(str));
}
printf("n");
}
return 0;
}
bnode *Createtree()
{
bnode *p;
char data;
data = str[i++];
if( data == '#' )
{
p = NULL;
}
else
{
p = (bnode *)malloc( sizeof(bnode) );
p->n = data;
p->lc = Createtree();
p->rc = Createtree();
}
return p;
}
void mid( bnode *b )
{
if(b != NULL)
{
mid(b->lc);
printf("%c", b->n);
mid(b->rc);
}
}
void last( bnode *b )
{
if(b != NULL)
{
last(b->lc);
last(b->rc);
printf("%c", b->n);
}
}
void LevleOrder(bnode *T)
{
bnode* Queue[100],*b;
int front,rear;
front=rear=0;
if (T)
{
Queue[rear++]=T;
while (front!=rear)
{
b=Queue[front++];
printf("%c", b->n);
if (b->lc!=NULL) Queue[rear++]=b->lc;
if (b->rc!=NULL) Queue[rear++]=b->rc;
}
}
}
解析
暂无