题目描述
给定一颗二叉树,要求输出二叉树的深度以及后序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000
输入
输入数据分为多组,第一行是测试数据的组数n,下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数,数据为0代表当前结点为空,数据为-1代表二叉树数据输入结束,-1不作处理。二叉树的构造按照层次顺序(即第1层1个整数,第2层2个,第3层4个,第4层有8个……,如果某个结点不存在以0代替)。
输出
输出每棵二叉树的深度以及后序遍历二叉树得到的序列。
样例输入
2
1 -1
1 2 0 3 4 -1
样例输出
1 1
3 3 4 2 1
参考代码
#include<stdio.h>
#include<stdlib.h>
#define maxsize 20
typedef struct node
{
int ltag,rtag;
int data;
struct node *lch,*rch;
}
btnode;
btnode *Q[maxsize];
int flag;
btnode *creat()
{
int c;
int front,rear;
btnode *T,*S;
T=NULL;
front=1;
rear=0;
scanf("%d",&c);
while(c!=-1)
{
S=NULL;
if(c!=0)
{
S=(btnode *)malloc(sizeof(btnode));
S->data=c;
S->lch=NULL;
S->rch=NULL;
S->rtag=0;
S->ltag=0;
}
rear++;
Q[rear]=S;
if(rear==1) T=S; else
{
if(S!=NULL && Q[front]!=NULL)
if(rear%2==0) Q[front]->lch=S; else Q[front]->rch=S;
if(rear%2==1) front++;
}
scanf("%d",&c);
}
return T;
}
void pre(btnode *T)
{
if(T)
{
if(T->ltag!=1) pre(T->lch);
if(T->rtag!=1) pre(T->rch);
if(flag)
{
printf(" ");
}
flag=1;
printf("%d",T->data);
}
}
int depth(btnode *bt)
{
int m,n;
if(bt==NULL)
return 0;
m=depth(bt->lch);
n=depth(bt->rch);
if(m>n)
return m+1; else
return n+1;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
flag=0;
btnode *bt;
bt=creat();
printf("%d ",depth(bt));
pre(bt);
printf("n");
}
return 0;
}
解析
暂无