层序遍历二叉树（C语言＋循环队列）

在之前的多篇文章中，已经探讨过层序遍历二叉树了，本文稍作补充，讲述了借助循环队列来实现的情况。
具体实现如下：

#include <iostream>
using namespace std;
#define MAXSIZE 50

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


// 先序建立二叉树 （输入时，按先序次序输入二叉树中结点的值,以 # 字符表示空树）
BiTree createBiTree()
{
    BiTree T;

char c;
scanf("%c", &c);

if (c == '#')
        T = NULL;
else
    {
        T = new BiNode;  // 或 T = (BiTree)malloc(sizeof(BiNode));
        T->data = c;

        T->lchild = createBiTree();
        T->rchild = createBiTree();
    }

return T;

}


// 二叉树的层序遍历（顺序队列）
void levelOrder(BiTree T)
{
if (T == NULL)
return;

    BiTree s[MAXSIZE];

int front, rear;
    front = rear = -1; // 采用顺序队列，并假定不会发生溢出

    s[++rear] = T;

while (front != rear)
    {
        BiTree q = s[++front];
cout << q->data << endl;

if (q->lchild)
            s[++rear] = q->lchild;

if (q->rchild)
            s[++rear] = q->rchild;

    }
}


// 二叉树的层序遍历（循环队列）
void levelOrder2(BiTree T)
{
if (T == NULL)
return;

    BiTree s[MAXSIZE];

int front, rear;
    front = rear = -1; // 采用循环队列，节省内存开销，并且不会发生溢出

    s[++rear] = T; // 根指针入队

while (front != rear) // 当队列非空时
    {
        front = (front + 1) % MAXSIZE;
        BiTree q = s[front]; // 队列的队头元素出队
cout << q->data << endl;

if (q->lchild)
        {
            rear = (rear + 1) % MAXSIZE;
            s[rear] = q->lchild; // 若节点q存在左孩子，则将左孩子指针入队；
        }

if (q->rchild)
        {
            rear = (rear + 1) % MAXSIZE;
            s[rear] = q->rchild; // 若节点q存在右孩子，则将右孩子指针入队；
        }
    }
}


int main(int argc, const char * argv[]) {

    BiTree T = createBiTree(); // 建立

// levelOrder(T); // 二叉树的层序遍历（顺序队列）

    levelOrder2(T); // 二叉树的层序遍历（循环队列）

return 0;
}

备注：
（1）本文的MAXSIZE应该足够使用，而且又是循环队列，在有新元素入队的同时，也有元素出队，所以一般不会出现队满的情况，不需要另加判断。
（2）循环队列的队空和队满要区分开来
<1> 循环队列的判空操作只需判断front = rear 是否成立，若成立，则队列为空。
<2> 循环队列的判满操作只需判断 ( rear + 1) % QueueSize = front 是否成立，若成立，则队列为满。