1 // 广度优先遍历二叉树(BFS).cpp: 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 
  6 
  7 #include <iostream>
  8 #include <stdio.h>
  9 #include <malloc.h>
 10 #include <stdlib.h>
 11 
 12 using namespace std;
 13 
 14 #define QUEUE_INIT_SIZE 100
 15 typedef char ElemType;
 16 
 17 typedef struct BiNode
 18 {
 19     ElemType data;
 20     struct BiNode *lchild, *rchild;
 21 }BiNode, *BiPtr;
 22 
 23 typedef struct queue
 24 {
 25     int queuesize;   //数组的大小
 26     int head, tail;  //队列的头和尾下标
 27     BiPtr *q;        //数组头指针
 28 }Queue, *QueuePtr;
 29 
 30 int InitQueue(QueuePtr &Q)
 31 {
 32     Q->queuesize = QUEUE_INIT_SIZE;
 33     Q->q = (BiPtr *)malloc(sizeof(BiPtr) * Q->queuesize); //分配内存
 34     Q->tail = 0;//数组下标从0开始,tail始终指向队尾元素的下一个位置
 35     Q->head = 0;//队列非空时，head始终指向队列首元素
 36     return 0;
 37 }
 38 
 39 int EnQueue(QueuePtr Q, BiPtr key)
 40 {
 41     if((Q->tail + 1) % Q->queuesize == Q->head)//取余保证，当quil=queuesize-1时，再转回0,此时队列没有空间                    
 42     {
 43         cout << "队列已满，无法再添加元素！";
 44     }
 45     else
 46     {
 47         Q->q[Q->tail] = key;
 48         Q->tail = (Q->tail + 1) % Q->queuesize;
 49     }
 50     return 0;
 51 }
 52 
 53 BiPtr DeQueue(QueuePtr Q)
 54 {
 55     BiPtr temp;
 56     if (Q->tail == Q->head)     //判断队列不为空
 57     {
 58         cout << "队列为空，无法删除元素！";
 59     }
 60     else
 61     {
 62         temp = Q->q[Q->head];
 63         Q->head = (Q->head + 1) % Q->queuesize;
 64     }
 65     return temp;
 66 }
 67 
 68 int IsQueueEmpty(QueuePtr Q)
 69 {
 70     if (Q->head == Q->tail)//空
 71         return 1;
 72     else//非空
 73         return 0;
 74 }
 75 
 76 int IsQueueFull(QueuePtr Q)
 77 {
 78     if ((Q->tail + 1) % Q->queuesize == Q->head)
 79         return 1;
 80     else
 81         return 0;
 82 }
 83 
 84 //---------------------------------------------------
 85 
 86 int Create_BiTree(BiPtr& T)
 87 {
 88     ElemType c;
 89     //cout << "请输入当前节点元素值：" << endl;
 90     cin >> c;
 91     if (c == '#') T = NULL;
 92     else
 93     {
 94         T = new BiNode;
 95         T->data = c;
 96         Create_BiTree(T->lchild);
 97         Create_BiTree(T->rchild);
 98     }
 99     return 0;
100 }
101 
102 //层序遍历
103 int LevelOrderTraverse(BiPtr T)
104 {
105     QueuePtr Q = new Queue;
106     BiPtr p = NULL;
107     InitQueue(Q);
108 
109     EnQueue(Q, T);//根结点入队
110     while (!IsQueueEmpty(Q))
111     {
112         p = DeQueue(Q);
113         cout << p->data << " ";
114         if (p->lchild)//如果p有左孩子,则左孩子入队
115             EnQueue(Q, p->lchild);
116         if (p->rchild)//如果p有右孩子,则左孩子入队
117             EnQueue(Q, p->rchild);
118     }
119     return 0;
120 }
121 
122 int main()
123 {
124     freopen("input2.txt", "r", stdin);//从input.txt中读取输入数据
125     BiPtr T;
126     Create_BiTree(T);
127     LevelOrderTraverse(T);
128     fclose(stdin);
129     return 0;
130 }