3.10 分层遍历二叉树

问题描述： 

1、给定一棵二叉树，要求按分层遍历该二叉树，
即从上到下按层次访问该二叉树(每一层将单独输出一行)，
每一层要求访问的顺序为从左到右，
并将节点依次编号。下面是一个例子:
8 
      /  \ 
     6   10 
    / \  / \ 
   5  7 9  11 
打印出来：
8 
6 10 
5 7 9 11 
2、写另外一个函数，打印二叉树中某层次的节点（从左到右），其中根节点为第0层，；

分析与解法

方法一：

输出二叉树某一层结点（从左到右）
           递归实现，把输出二叉树第K层结点转换成：分别输出"以该二叉树根结点的左右子树为根的两棵子树"中第K-1层结点。 

void PrintNodeAtLevel(Node *root , int level)
{
    if(!root || level < 0)
        return ;
    if(level == 0)
    {
        printf("%c", root->chValue);
    }
    PrintNodeAtLevel(root->lChild , level - 1);
    PrintNodeAtLevel(root->rChild , level - 1);
}

以上输出某一层节点，若知道深度n，只需调用n次即可； 

void printNodeByLevel(Node *root,int depth)
{
	for(int level=0;level<depth;level++)
	{
		printNodeAtLevel(root,level);
		cout<<endl;
	}
} 

方法二

按层从上到下遍历二叉树，每一层单独一行且从左往右输出，BFS，用队列实现 ，具体实现见后面代码

扩展问题

1、依然是按层遍历二叉树，只是要求从下往上访问，并且每一层中结点的访问顺序为从左向右
       类似扩展问题2，输出时处理下 ，具体见后面实现

2、依然是按层遍历二叉树，只是要求从下往上访问，并且每一层中结点的访问顺序为从右向左

分析：只要层与层之间加入哑元素（NULL），然后逆序输出队列Q即可
第一步：给每一层之间添加哑元素NULL
第二步：逆序输出队列Q

代码实现

/*
		8 
      /  \ 
     6   10 
    / \  / \ 
   5  7 9  11 */
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue> 
using namespace std;
#define MAX 20

struct BTreeNode{
	int data;
	BTreeNode *left,*right;
}; 

//建立二叉树 
BTreeNode * CreateTree(int data[],int pos,int len)
{
	BTreeNode *tree;
	if(pos>=len) 
	{
		return NULL;
	}
	else
	{
		tree=(BTreeNode *)malloc(sizeof(BTreeNode));
		tree->data=data[pos];
		tree->left=CreateTree(data,2*pos+1,len);//数组坐标 
		tree->right=CreateTree(data,2*pos+2,len);
		return tree;
	}
}

//中序遍历 
void InOrder(BTreeNode *tree)
{
	if(tree!=NULL)
	{
		InOrder(tree->left);
		printf("%d ",tree->data);
		InOrder(tree->right);
	}
}

// BFS层次遍历 
void BFS(BTreeNode *root)
{
	BTreeNode *temp,*start;
	queue<BTreeNode *> q;
	
	q.push(root);
	while(!q.empty())
	{
		start=q.front();
		q.pop();
		
		if(start->left!=NULL)
			q.push(start->left);
		
		if(start->right!=NULL)
			q.push(start->right);
		printf("%d ",start->data);	
	}
}

//方法二：用数组模拟 队列；方便实现扩展问题 
void BFS1(BTreeNode *root)
{
	BTreeNode *p;
	BTreeNode *Q[200];
	int front,rear,last; 
	if(!root)
		return ;
	front=rear=0;
	
	Q[rear++]=root;
	Q[rear++]=NULL;
	while(front<rear-1)
	{
		last=rear-1;
		while(front<last)
		{
			p=Q[front++];
			if(p->left!=NULL)
				Q[rear++]=p->left;
			if(p->right!=NULL)
				Q[rear++]=p->right;
		}
		Q[rear++]=NULL;
		front=last+1;
	}
	
	printf("\n层次遍历 打印结果：\n");
	for(int i=0;i<=rear-2;i++)
	{
	    if(Q[i]==NULL)
	        printf("\n");
	    else
	        printf("%d ", Q[i]->data);
	}
	
	printf("\n扩展问题1 打印结果：\n");
	int j,k;
	for(int i=rear-2;i>=0;i--)
	{
	    if(Q[i]==NULL)
	    {
	    	printf("\n");
	    	for(j=i-1;j>=0;j--)
	    		if(Q[j]==NULL)
	    			break;
	    	for(k=j+1;k<i;k++)
	    		printf("%d ", Q[k]->data);
	    	i=j+1;
	    } 
	}
	
	printf("\n扩展问题2 打印结果：\n");
	for(int i=rear-2;i>=0;i--)
	{
	    if(Q[i]==NULL)
	        printf("\n");
	    else
	        printf("%d ", Q[i]->data);
	}
}

int main(){
	
	int data[]={8,6,10,5,7,9,11};
	int len=sizeof(data)/sizeof(int);
	
	BTreeNode *tree=CreateTree(data,0,len);

	printf("中序遍历：\n");//左根右 
	InOrder(tree);printf("\n");
	printf("BFS层次遍历 打印结果：\n");
	BFS(tree);printf("\n");
	
	BFS1(tree);
	return 0;
}

         8 
      /   \ 
     6    10 
    / \    /    \ 
   5  7 9  11