二叉樹層序遍歷的實現

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

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