我们可以很容易的使用队列来实现二叉树的层序遍历，代码如下：
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
//二叉树存储结构定义
typedef char Item;
typedef struct node *link;
struct node {Item item; link l, r;};
int Create(link *tp);
void show(link h);
void tranverse(link h, void (*visit)(link));
//队列存储结构定义
typedef link QItem;
static QItem *q;
static int N, head, tail;
void QUEUEinit(int maxN);
int QUEUEempty();
void QUEUEput(QItem item);
QItem QUEUEget();
int main()
{
link tree;
Create(&tree);
tranverse(tree, show);
return 0;
}
void QUEUEinit(int maxN)
{
q = (QItem *)malloc(maxN * sizeof(QItem));
if (!q) return;
N = maxN + 1; head = N; tail = 0;
}
int QUEUEempty()
{
return head % N == tail;
}
void QUEUEput(QItem item)
{
q[tail++] = item;
tail = tail % N;
}
QItem QUEUEget()
{
head = head % N;
return q[head++];
}
int Create(link *tp)
{
//构造方法，或者说构造顺序：中序遍历构造
char x;
scanf("%c",&x);
if(x=='#')
{
*tp=NULL;//指针为空，树节点中的某个指针为空
return 0;
}
*tp=(link)malloc(sizeof(**tp));//将树节点中指针指向该地址空间
if(*tp==NULL)
return 0;
(*tp)->item=x;
Create(&((*tp)->l));
Create(&((*tp)->r));
return 1;
}
void show(link h)
{
printf(" %c ", h->item);
}
//层序遍历
void tranverse(link h, void (*visit)(link))
{
QUEUEinit(MAX); QUEUEput(h);
while (!QUEUEempty()){
(*visit)(h = QUEUEget());
if (h->l != NULL) QUEUEput(h->l);
if (h->r != NULL) QUEUEput(h->r);
}
}