二叉树的广度优先遍历
广度优先遍历：又称按层次遍历，也就是先遍历二叉树的第一层节点，然后遍历第二层节点……最后遍历最下层节点。而对每一层的遍历是按照从左至右的方式进行的。
基本思想：按照广度优先遍历的方式，上一层中先被访问的节点，它的下层孩子也必然先被访问，因此在算法实现时，需要使用一个队列。在遍历进行之前先把二叉树的根结点的存储地址入队，然后依次从队列中出队结点的存储地址，每出队一个结点的存储地址则对该结点进行访问，然后依次将该结点的左孩子和右孩子的存储地址入队，如此反复，直到队空为止。
具体算法如下：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define maxsize 20
typedef int datatype;
typedef struct node
{
datatype data;
struct node *lchild,*rchild;
}bitree;
void Layer(bitree *p);
bitree* CreatBitree(int* arrayA,int n);
int countleaf(bitree *p);
int treedepth(bitree*p,int l);
void main()
{
int arrayA[10]={0,1,2,3,4,5,6,7,8,9};//第一个节点没有用于存储数据
int n=sizeof(arrayA)/sizeof(int);
int l=0;//二叉树的深度
bitree *head=NULL;
head=CreatBitree(arrayA,n);
printf("按广度优先搜索遍历的结果为：");
Layer(head);
printf("\n");
}
/**************************************************\
函数功能：二叉树的广度优先遍历
输入：二叉树的根节点
输出：无
\**************************************************/
void Layer(bitree *p)
{
bitree* queue[maxsize];//queue数组用于存储节点地址
bitree* s;
int rear=0; //队列尾指针
int front=0; //队列头指针
if(p!=NULL)//输入的树不为空
{
rear=1; //初始化
front=0;
queue[rear]=p;
while(front<rear)//判断队列是否为空
{
front++;
s=queue[front];
printf("%d ",s->data);
if(s->lchild!=NULL) //存储左右子节点
{
rear++;
queue[rear]=s->lchild;
}
if(s->rchild!=NULL)
{
rear++;
queue[rear]=s->rchild;
}
}
}
}
/*************************************************\
函数功能：建立二叉树（按照顺序方式）
输入： 原始数组
输出： 二叉树的头结点
\*************************************************/
bitree* CreatBitree(int* arrayA,int n)//顺序存储 建立二叉树
{
bitree *root;
bitree *queue[maxsize];
bitree *p;
int front,rear;
front=1;rear=0;
root=NULL;
for(int i=1;i<n;i++)
{
p=(bitree*)malloc(sizeof(bitree));
p->data=arrayA[i];
p->lchild=NULL;
p->rchild=NULL;
rear++;
queue[rear]=p;
if(rear==1)
root=p;
else
{
if(i%2==0)
queue[front]->lchild=p;
else
{
queue[front]->rchild=p;
front=front+1;
}
}
}
return root;
}注：如果程序出错，可能是使用的开发平台版本不同，请点击如下链接：
解释说明
