二叉树层次遍历（利用队列）

#include <iostream>
#include <string>
using namespace std;
// 二叉树
typedef struct BiTNode
{
    string data;
    BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

// 初始化二叉树
BiTree tree;
tree = new BiTNode;
tree->data = "A";

BiTNode *p;

p = new BiTNode;
p->data="B";
p->lchild=NULL;
p->rchild=NULL;
tree->lchild=p;

p = new BiTNode;
p->data="C";
p->lchild=NULL;
p->rchild=NULL;
tree->rchild=p;


p = new BiTNode;
p->data="D";
p->lchild=NULL;
p->rchild=NULL;
tree->lchild->lchild=p;

p = new BiTNode;
p->data="E";
p->lchild=NULL;
p->rchild=NULL;
tree->lchild->rchild=p;

p = new BiTNode;
p->data="F";
p->lchild=NULL;
p->rchild=NULL;
tree->rchild->lchild=p;

p = new BiTNode;
p->data="G";
p->lchild=NULL;
p->rchild=NULL;
tree->rchild->rchild=p;

p = new BiTNode;
p->data="H";
p->lchild=NULL;
p->rchild=NULL;
tree->rchild->lchild->lchild=p;


p = new BiTNode;
p->data="I";
p->lchild=NULL;
p->rchild=NULL;
tree->rchild->lchild->rchild=p;

typedef struct LinkNode{
    BiTree data;
    LinkNode *next;
}LinkNode;

typedef struct
{
    LinkNode *front, *rear;
}LinkQueue;

void InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=new LinkNode;
    Q.front->next=NULL;
}
//从队尾插入
void EnQueue(LinkQueue &Q, BiTree x)
{
    LinkNode *s;
//     s =(LinkNode*)malloc(sizeof(LinkNode));
    s = new LinkNode;
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

void DeQueue(LinkQueue &Q, BiTree &x)
{
    LinkNode *p=Q.front->next;
    x = p->data;
    Q.front->next=p->next;
    if(Q.front->next==NULL)
        Q.rear=Q.front;//注意不能写成Q.front=Q.rear;
    free(p);
}

bool QueueEmpty(LinkQueue Q)
{
    if(Q.front==Q.rear)
        return true;
    else
        return false;
}

void LevelOrder(BiTree T)
{
    LinkQueue q;
    BiTree t;
    InitQueue(q);
    EnQueue(q, T);
    while(!QueueEmpty(q))
    {
        DeQueue(q, t);
        cout<<t->data;
        if(t->lchild)
            EnQueue(q,t->lchild);
        if(t->rchild)
            EnQueue(q, t->rchild);
    }
}

LevelOrder(tree)

/*
输出：
ABCDEFGHI
*/