二叉树的层次遍历（相当于广度遍历） SJTU OJ 题目 1040二叉树层次遍历

  

1040. 二叉树层次遍历

       Description

给出一棵二叉树，求它的层次遍历结果。

[二叉树的遍历问题是一种精神，务必领会]

Input Format

第一行，N<1000000，表示二叉树节点数。

默认序号为0的节点为树根。接下来共N-1行，依次表示序号为1，...，N-1的节点的父亲节点序号。

如果一个节点有两个孩子节点，左孩子节点序号总是小于右孩子节点序号。

Output Format

仅一行，二叉树的层次遍历结果。节点序号间用空格隔开。

Hint

Sample Input

6
0
1
1
0
4

Sample Output

0 1 4 2 3 5

 

 

 

 

 分析：一开始我想到直接建一个二维数组，tree[num][2]; 

  行标为根结点，每一行第一个为左子树，第二个为右子树；

 

 

 

然后从o结点开始遍历，遍历完两个子树，然后从左子树开始遍历，遍历左子树两个子树，但是很难确定什么时候当前节点的堂兄弟是否都已经遍历，

后来问问女朋友，她说我肯定是没看它的博客，我到她的新浪博客找找看，结果找到了二叉树遍历问题，下面看看是怎么实现的层次遍历

建立一个队列 queue <int >Q;  (头文件#include<queue>),

1.首先将根节点0入队，

2.将队首元素的两个子树入队，

3.将队首元素输出，出队，然后重复步骤2，直到队列为空（或者直到所有元素输出）

 

代码：

 

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



using namespace std;

int tree[1000002][2];//注意题目中的N<1000000;额这里我一开始设置的小了，提交一直RUN TIME ERROR 
int cnt=0;

queue < int> Q;

void Traverse(int n)
{
	cnt++;
	if(cnt>n) return ;
	//将对头元素的两个子树入队 
	if(tree[Q.front()][0]!=-1) Q.push(tree[Q.front()][0]);
	if(tree[Q.front()][1]!=-1) Q.push(tree[Q.front()][1]);
	
	printf("%d",Q.front());
	if(cnt<n) printf(" ");
	Q.pop();
	Traverse(n);
}
int main()
{
	int i,n,parent;
	scanf("%d",&n);
	
	cnt=0;
//	while( !Q.empty() ) Q.pop();
	for(i=0;i<n;i++) 
		tree[i][0] = tree[i][1] = -1;
	
	for(i=1;i<n;i++)
	{
		scanf("%d",&parent);
		if(tree[parent][0]!=-1 )  //0位置有元素
		{
			if(tree[parent][0]>i)//比较xiao的放到0位置， 
			{
				tree[parent][1] = tree[parent][0]; 
				tree[parent][0]	= i; 
			}
			else tree[parent][1] = i; 
		}
		else tree[parent][0]=i;
	}	
	Q.push(0);
//	for(i=0;i<n;i++)printf("%4d %4d\n",tree[i][0],tree[i][1]);
	Traverse(n);
	printf("\n");
	
	return 0;
}