学步园

/*
第 16  题：
题目（微软）： 
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
		8
      /  \
	 6   10
	/ \  / \
   5  7 9  11
打印出来：8 6 10 5 7 9 11

BFS广度优先搜索 
*/ 

#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);
	}
}

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);	
	}
}

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("打印结果：\n");
	BFS(tree);printf("\n");
	
	return 0;
}