二叉树的输入

二叉树的输入

时间: 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;
		}
	}
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注