二叉樹層序遍歷的實現

我們可以很容易的使用隊列來實現二叉樹的層序遍歷，代碼如下：

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