1、层次遍历

按层次遍历二叉树的方式：按照“从上到下，从左到右”的顺序遍历二叉树，即先遍历二叉树的第一层的结点，然后是第二层的结点，直到最底层的结点，对每一层的遍历按照从左到右的次序进行。

2、层次遍历算法

要进行层次遍历，需要借助一个队列。先将二叉树的根结点入队，然后出队，访问该结点，若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队。然后出队，对出队结点访问，如初反复，直到队列为空。

void LevelOrder(BiTree T) {BiTree p=T;BiTree q;LinkQueue Q;InitQueue(Q);EnQueue(Q,*p);while(!IsEmpty(Q)){DeQueue(Q,*q);cout<<q->data;   //访问根结点 if(q->lchild) EnQueue(Q,*(q->lchild));//左子树入队 if(q->rchild) EnQueue(Q,*(q->rchild));//右子树入队 }}

3、完整代码

（1）本实验按照先序遍历的顺序建立二叉链表，用“#”表示空树。如图所示：

（2）以上图所示二叉树验证实验，完整代码如下：

#include<iostream>
#define OK 1
#define ERROR 0
using namespace std;typedef char TElemType;
typedef struct BiTNode{  //二叉树的存储结构TElemType   data;	// 数据域struct  BiTNode *lchild; //左孩子指针struct  BiTNode *rchild; //右孩子指针
}BiTNode, *BiTree;typedef BiTNode QElemType; 
typedef struct QNode{  //链队列结点存储结构 QElemType data;struct QNode *next;
}QNode, *QueuePtr;typedef struct{QueuePtr front; //队头指针QueuePtr rear; //队尾指针 
}LinkQueue;
//队列初始化 
int InitQueue(LinkQueue &Q){Q.front=Q.rear=new QNode;Q.front->next=NULL;
}
//队列判空操作 
bool IsEmpty(LinkQueue Q){if(Q.front==Q.rear)return true;elsereturn false;
}
//入队操作
int EnQueue(LinkQueue &Q, QElemType e){QueuePtr p;p = new QNode;p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;
} 
//出队操作
int DeQueue(LinkQueue &Q, QElemType &e) {if(Q.front==Q.rear)return ERROR;QueuePtr p;p=Q.front->next;Q.front->next=p->next;if(Q.rear==p) Q.rear=Q.front;e = p->data;delete p;return OK;}//以先序次序创建二叉树 
void CreateBiTree_PreOrder(BiTree &T){char ch; cin>>ch;if(ch=='#')T=NULL; else{T=new BiTNode;  //生成根结点T->data=ch; //根结点的数据域置为chCreateBiTree_PreOrder(T->lchild);//构造左子树CreateBiTree_PreOrder(T->rchild); //构造右子树}}
//层次遍历二叉树
void LevelOrder(BiTree T) {BiTree p=T;BiTree q;LinkQueue Q;InitQueue(Q);EnQueue(Q,*p);while(!IsEmpty(Q)){DeQueue(Q,*q);cout<<q->data;   //访问根结点 if(q->lchild) EnQueue(Q,*(q->lchild));//左子树入队 if(q->rchild) EnQueue(Q,*(q->rchild));//右子树入队 }}int main()
{BiTree T;cout<<"以先序次序创建二叉链表，以#表示空子树："<<endl;CreateBiTree_PreOrder(T);cout<<"层次遍历："; LevelOrder(T); return 0;
}

4、实验结果

5、结语

数据结构中对于二叉树的遍历方式，主要有4种，除了层次遍历，还有先序遍历、中序遍历和后序遍历。关于先序遍历、中序遍历和后序遍历的算法实现过程，可以参考二叉树的先序遍历、中序遍历和后序遍历
欢迎大家一起留言讨论~