BUPT OJ100 二叉树的层数

本文主要是介绍BUPT OJ100 二叉树的层数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

老师有一个问题想考考mabo，但是mabo不会，所以想请你来帮帮忙。

问题如下：

给一个二叉树

请把这个棵二叉树按层来打印。如果为相同层，需要从左到右打印。一个节点是先添加左节点后添加右节点，即添加顺序与输入顺序一致。

输入格式

首先输入一个整数T，表示一共有T组数据 0<T<=10

再输入两个整数N,M(0<=N,M<=100)

表示下面有N行，这个树有M个节点(1号节点是这棵树的根节点)

每一行两个整数a,b(1<=a,b<=M)

表示节点a的父亲是节点b

输出格式

对于每组

先输出一行 "Qi:"表示第i个问题

然后接下来输出每个问题二叉树每层的节点，在同一层的节点用空格分开，同一层输出在一行（每一行末尾没有空格），不同的层输出在不同行（入下面Sample Ouput所示）

输入样例

输出样例

判断二叉树的同一层可由深度depth实现, *lnext, *rnext保存的分别是左子节点和右子节点的地址

P.S. 前面最后的输出部分也可以由C++的STL queue内pop(), push()来实现

/*
USER_ID: test#birdstorm
PROBLEM: 100
SUBMISSION_TIME: 2014-03-02 11:54:13
*/
#include <stdio.h>
#include <stdlib.h>
#define For(i,m,n) for(i=m;i<n;i++)
#define MAXN 105typedef struct tree{int depth, name;struct tree *lnext, *rnext;
}tree;main()
{int i, j, T, t, n, m, x, y, flag;int c[MAXN];struct tree d[MAXN];scanf("%d",&T);For(t,1,T+1){scanf("%d%d",&n,&m);For(i,0,m+1){d[i].depth=0;d[i].lnext=d[i].rnext=NULL;}d[1].depth=1;For(i,0,n){scanf("%d%d",&x,&y);d[x].name=x;d[y].name=y;if(d[y].lnext==NULL) d[y].lnext=&d[x];else d[y].rnext=&d[x];d[x].depth=d[y].depth+1;}printf("Q%d:\n",t);i=j=c[1]=1; flag=1;while(i<=j){if(d[c[i]].lnext!=NULL) c[++j]=(*d[c[i]].lnext).name;if(d[c[i]].rnext!=NULL) c[++j]=(*d[c[i]].rnext).name;if(i>1) putchar(d[c[i]].depth!=flag?'\n':' ');printf("%d",d[c[i]].name);flag=d[c[i]].depth;i++;}puts("");}return 0;
}

这篇关于BUPT OJ100 二叉树的层数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！