广度优先遍历二叉树(BFS)-C++实现

旧城等待， 2022-04-01 12:52 152阅读 0赞

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 }