广度优先搜索BFS之二叉树的构造及遍历

二叉树采用二叉链表作存储结构，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：中序、后序以及层次遍历序列，分别输出结点的遍历序列；3. 求二叉树的深度/叶结点数目。

/*输入二叉树的先序序列例如："abc  de g f   "       ---------------*/ #include<iostream>#include<cstdio>#include<cstdlib>#include<queue>#include<stack>using namespace std; #define OVERFLOW -2#defineSTACK_INIT_SIZE 50#define STACKINTCREMENT10typedef structBiTNode{    char data;    struct BiTNode *lchild,*rchild;}BiTNode,*BiTree; intCreateBiTree(BiTree &t){    char ch;    scanf("%c",&ch);    if(ch==' ') t=NULL;    else    {        if(!(t=(BiTNode*)malloc(sizeof(BiTNode))))            exit(OVERFLOW);        t->data=ch;        CreateBiTree(t->lchild);        CreateBiTree(t->rchild);    }    return 0;} intInOrderTraverse(BiTree t){    if(t)    {        InOrderTraverse(t->lchild);        PRintf("%c",t->data);        InOrderTraverse(t->rchild);    }    return 0;} intPostorderTraverse(BiTree t){    if(t)    {        PostorderTraverse(t->lchild);        PostorderTraverse(t->rchild);        printf("%c",t->data);    }    return 0;} queue <BiTNode*>que; void bfs(BiTree t){    if(t)    {        que.push(t);        while(!que.empty())        {            BiTree c=que.front();            que.pop();            printf("%c",c->data);            if(c->lchild &&c->data) que.push(c->lchild);            if(c->rchild &&c->data) que.push(c->rchild);        }    }    printf("/n");} int main(){    BiTree t;    printf("请输入二叉树的先序序列/n");    CreateBiTree(t);    printf("二叉树的中序序列/n");    InOrderTraverse(t);    printf("/n");    printf("二叉树的后序序列/n");    PostorderTraverse(t);    printf("/n");    printf("二叉树的层次遍历序列/n");    bfs(t);    printf("/n");    return 0;}