先序遍历二叉树

先序遍历二叉树

时间: 1ms        内存:128M

描述:

给定一颗二叉树,要求输出二叉树的深度以及先序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。

输入:

输入数据分为多组,第一行是测试数据的组数n,下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数,数据为0代表当前结点为空,数据为-1代表二叉树数据输入结束,-1不作处理。二叉树的构造按照层次顺序(即第1层1个整数,第2层2个,第3层4个,第4层有8个......,如果某个结点不存在以0代替),比如输入:

1 2 0 3 4 -1得到的二叉树如下:

 

1

2 #

3 4

输出:

输出每棵二叉树的深度以及先序遍历二叉树得到的序列。

示例输入:

2
1 -1
1 2 0 3 4 -1

示例输出:

1 1
3 1 2 3 4

提示:

参考答案(内存最优[752]):

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	int data;
	struct node *lc, *rc;
}bnode;

bnode *CreateTree();

bnode *que[100];

bnode *CreateTree()
{
	int data;
	int front=1, rear=0;
	bnode *root, *s;
	root = NULL;
	
	scanf("%d", &data);
	while(data != -1)
	{
		s=NULL;
		if(data != 0)
		{
			s = (bnode *)malloc(sizeof(bnode));
			s->data = data;
			s->lc = NULL;
			s->rc = NULL;
		}
		rear++;
		
		que[rear] = s;
		
		if( rear == 1 )
		{
			root = s;
		}
		else
		{
			if( s&&que[front] )
			{
				if(rear%2 == 0)
				{
					que[front]->lc = s;
				}
				else
				{
					que[front]->rc = s;
				}
			}
			if( rear %2 == 1 )
			{
				front++;
			}
		}
		scanf("%d", &data);
	}
	return root;
}

void pre( bnode *p )
{
	if( p != NULL )
	{
		printf(" %d", p->data);
		pre(p->lc);
		pre(p->rc);
	}
}

int dep( bnode *p )
{
	int	lh,rh;
	if( p == NULL )
	{
		return 0;
	}
	else
	{
		lh = dep(p->lc);
		rh = dep(p->rc);
		if( lh > rh )
		{
			return lh+1;
		}
		return rh+1;
	}
	
	
}

int main()
{
	bnode *p;
	int t;
	
	scanf("%d", &t);
	while( t-- )
	{
		p = CreateTree();
		printf("%d", dep(p));
		pre(p);
		printf("\n");
	}
	return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	int data;
	struct node *lc, *rc;
}bnode;

bnode *CreateTree();

bnode *que[100];

bnode *CreateTree()
{
	int data;
	int front=1, rear=0;
	bnode *root, *s;
	root = NULL;
	
	scanf("%d", &data);
	while(data != -1)
	{
		s=NULL;
		if(data != 0)
		{
			s = (bnode *)malloc(sizeof(bnode));
			s->data = data;
			s->lc = NULL;
			s->rc = NULL;
		}
		rear++;
		
		que[rear] = s;
		
		if( rear == 1 )
		{
			root = s;
		}
		else
		{
			if( s&&que[front] )
			{
				if(rear%2 == 0)
				{
					que[front]->lc = s;
				}
				else
				{
					que[front]->rc = s;
				}
			}
			if( rear %2 == 1 )
			{
				front++;
			}
		}
		scanf("%d", &data);
	}
	return root;
}

void pre( bnode *p )
{
	if( p != NULL )
	{
		printf(" %d", p->data);
		pre(p->lc);
		pre(p->rc);
	}
}

int dep( bnode *p )
{
	int	lh,rh;
	if( p == NULL )
	{
		return 0;
	}
	else
	{
		lh = dep(p->lc);
		rh = dep(p->rc);
		if( lh > rh )
		{
			return lh+1;
		}
		return rh+1;
	}
	
	
}

int main()
{
	bnode *p;
	int t;
	
	scanf("%d", &t);
	while( t-- )
	{
		p = CreateTree();
		printf("%d", dep(p));
		pre(p);
		printf("\n");
	}
	return 0;
}

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

点赞