二叉树的输入

二叉树的输入

时间： 1ms        内存：128M

描述：

用二叉树的带虚结点表示的前序遍历序可以唯一的确定一棵二叉树。

输入：

输入包含多组数据。
每行是一棵二叉树的带虚结点（#）表示的前序遍历序串，长度不超过2000。每个结点为一个字符。

输出：

对每行输入，输出对应二叉树的中序遍历序（不含虚结点）、后序遍历序（不含虚结点）和层次遍历序（不含虚结点）。
每棵二叉树的输出占一行，中序遍历序、后序遍历序和层次遍历序之间用一个空格隔开。

示例输入：

ab##c##
#
ab###

示例输出：

bac bca abc

ba ba ab

提示：

参考答案（内存最优[752]）：

#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;
		}
	}
}

参考答案（时间最优[0]）：

#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;
		}
	}
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。