二叉树层次遍历

利用队列实现二叉树层次遍历

层次遍历用队列实现，不用递归方法，一边入队一边出队，终止条件是队列为空。

#include
#include
#include
#include
#include
#include
using namespace std;

typedef struct BiTNode{
    char data;
    BiTNode *lchild, *rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T)//建树
{
    char ch;
    scanf("%c",&ch);
    if(ch==' ')
    {
        T=NULL;
        return;
    }
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        if(!T)
            exit(1);
        T->data=ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
void LevelOrderTraverse(BiTree T)//层次遍历
{
    queue Queue;
    if(!T)
    {
        printf("空树！\n");
        return;
    }
    Queue.enqueue(T);
    while(!Queue.empty())
    {
        T=Queue.front();
        Queue.dequeue();
        printf("%c",T->data);
        if(T->lchild)
            Queue.enqueue(T->lchild);
        if(T->rchild)
            Queue.enqueue(T->rchild);
    }
}
void main()
{

    BiTree T;
    CreateBiTree(T);
    LevelOrderTraverse(T);
    printf("\n");
}