二叉树层次遍历

        二叉树层次遍历的实现思想是：通过队列数据结构，从树的根结点开始，依次将其左孩子和右孩子入队；而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层次遍历的最终结果

图1 二叉树

以上图 1 为例，层次遍历的过程如下：

1. 首先，根结点 1 入队
2. 根结点 1 出队，出队的同时，将左孩子 2 和右孩子 3 分别入队
3. 队头结点 2 出队，出队的同时，将结点 2 的左孩子 4 和右孩子 5 依次入队
4. 队头结点 3 出队，出队的同时，将结点 3 的左孩子 6 和右孩子 7 依次入队
5. 不断地循环，直至队列内为空

因此，图 1 中二叉树采用层次遍历得到的序列为：

二叉树层次遍历代码实现

#include <stdio.h>
#include <stdlib.h>

typedef struct MyBiTNode{
    int data;  // 数据域
    struct MyBiTNode *lchild, *rchild;  // 左右孩子指针
} BiTNode;

BiTNode *CreateBiTree(BiTNode *T){
	// 结点 1 
    T = (BiTNode*)malloc(sizeof(BiTNode));
    T->data = 1;
    // 结点 2
	T->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->data = 2;
	// 结点 3
	T->rchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->rchild->data = 3;
	// 结点 4 
	T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->lchild->data = 4;
	T->lchild->lchild->lchild = NULL;
	T->lchild->lchild->rchild = NULL;
	// 结点 5
	T->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->rchild->data = 5;
	T->lchild->rchild->lchild = NULL;
	T->lchild->rchild->rchild = NULL;
	// 结点 6
	T->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->rchild->lchild->data = 6;
	T->rchild->lchild->lchild = NULL;
	T->rchild->lchild->rchild = NULL;
	// 结点 7
	T->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->rchild->rchild->data = 7; 
	T->rchild->rchild->lchild = NULL;
	T->rchild->rchild->rchild = NULL;
	return T;
}
 
// 初始化队头和队尾指针开始时都为 0
int front = 0, rear = 0;

// 入队函数
void EnQueue(BiTNode **a, BiTNode *node){
    a[rear++] = node;
    // a[0] = Tree; rear = 1
    // a[1] = Tree->lchild; rear = 2
    // a[2] = Tree->rchild; rear = 3
    // a[3] = Tree->lchild->lchild; rear = 4
    // a[4] = Tree->lchild->rchild; rear = 5
    // a[5] = Tree->rchild->lchild; rear = 6
    // a[6] = Tree->rchild->rchild; rear = 7
}

// 出队函数 
BiTNode *DeQueue(BiTNode **a){
    return a[front++];
    // a[0]; front = 1 
    // a[1]; front = 2
    // a[2]; front = 3
}

//输出函数 
void displayNode(BiTNode *node){
    printf("%d ", node->data);
}

// 层次遍历函数
void LevelOrderTraverse(BiTNode *Tree){
	// 采用顺序队列，初始化创建队列数组
    BiTNode *a[20];
    // 创建临时指针 
    BiTNode *p;
    // 根结点入队
    EnQueue(a, Tree);
    // 当队头和队尾相等时，表示队列为空
    while(front < rear){
        // 队头结点出队
        p = DeQueue(a);  // Tree;Tree->lchild;Tree->rchild
        displayNode(p);  // 1 2 3
        // 将队头结点的左右孩子依次入队
        if(p->lchild != NULL) {
            EnQueue(a, p->lchild);
        }
        if (p->rchild != NULL) {
            EnQueue(a, p->rchild);
        }
    }
}

int main() {
    BiTNode *Tree = NULL;  // 结构体指针指向空 
    Tree = CreateBiTree(Tree);  // 传入结构体指针 
    
    LevelOrderTraverse(Tree);  // 层次遍历 
    return 0;
}