题目描述
给定一颗二叉树,要求输出二叉树的深度以及先序遍历二叉树得到的序列。本题假设二叉树的结点数不超过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
参考代码
#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;
}
解析
暂无