按層次遍歷二叉樹是一種基於廣度優先搜索思想的二叉樹遍歷演算法。 不同于深度優先搜索的先序、中序和後序遍歷， 它的遍歷次序是針對二叉樹的每一層進行的。 若二叉樹非空， 則先訪問二叉樹第一層的結點。 然後再依次訪問第二層的結點， 第三層的結點， ……直到訪問了二叉樹最下面一層的結點為止。 對二叉樹中每一層結點的訪問都是按照從左至右的順序進行的。
在進行二叉樹的按層次遍歷時， 需要一個佇列結構輔助（二叉樹的深度優先遍歷的非遞迴呼叫實現需要使用一個棧來輔助）。
① 把二叉樹的根結點的指針入隊；
② 獲取隊首元素並出隊， 訪問該指標指向的結點；然後依次把該結點的左孩子結點（如果存在）和右孩子結點（如果存在）的指針入隊；
③ 重複②的操作，
直到佇列為空。
運行效果：
按層次遍歷二叉樹的訪問結點次序及佇列狀態：
代碼：
附源碼：
#include "stdio.h"
#include
#include
using namespace std;
typedef struct BiTNode{
char data;/*結點的資料欄*/
struct BiTNode *lchild , *rchild; /*指向左孩子和右孩子*/
} BiTNode , *BiTree;
void CreatBiTree(BiTree *T){/*按先序遍歷的思想創建一棵二叉樹*/
char c;
scanf("%c",&c);
if(c == ' ') *T = NULL;
else{
*T = (BiTNode * )malloc(sizeof(BiTNode)); /*創建根結點*/
(*T)->data = c;/*向根結點中輸入資料*/
CreatBiTree(&((*T)->lchild));/*遞迴地創建左子樹*/
CreatBiTree(&((*T)->rchild));/*遞迴地創建右子樹*/
}
}
void PreOrderTraverse(BiTree T ){/*先序遍歷二叉樹*/
if(T){/*遞迴結束條件， T為空*/
printf("%3c",T->data);/*訪問根結點,將根結點內容輸出*/
PreOrderTraverse(T->lchild);/*先序遍歷T的左子樹*/
PreOrderTraverse(T->rchild);/*先序遍歷T的右子數*/
}
}
void visit(BiTree p) {
printf("%3c",p->data);
}
void layerOrderTraverse(BiTree T)//按層遍歷
{
BiTree queue[20],p;
int front,rear;
if(T!=NULL)
{
queue[0] = T;/*將根結點的指標（位址）入佇列*/
front = -1;
rear = 0;
while(front { p = queue[++front];/*取出隊頭元素*/ visit(p); /*訪問p指向的結點元素*/ if(p->lchild!=NULL)/*將p結點的左孩子結點指標入佇列*/ queue[++rear] = p->lchild; if(p->rchild!=NULL)/*將p結點的右孩子結點指標入佇列*/ queue[++rear] = p->rchild; } } } void layerOrderTraverse2(BiTree T)//按層遍歷，
使用queue { BiTree p; queue if(T!=NULL) { q.push(T);/*將根結點的指標（位址）入佇列*/ while(! q.empty())/*當佇列不為空時進入迴圈*/ { p = q.front(); q.pop();/*取出隊頭元素*/ visit(p); /*訪問p指向的結點元素*/ if(p->lchild!=NULL)/*將p結點的左孩子結點指標入佇列*/ q.push(p->lchild); if(p->rchild!=NULL)/*將p結點的右孩子結點指標入佇列*/ q.push(p->rchild); } } } main() { BiTree T = NULL; /*最開始T指向空*/ printf("需要創建和遍歷的二叉樹： "); printf(" A "); printf(" / "); printf(" B E "); printf(" / "); printf(" C D F "); printf("Input some characters to create a binary tree "); printf("（按先序序列建立） "); printf("例如，
ABC##D##E#F##↙，
#表示空格,↙表示回車 "); printf("Input some characters to create a binary tree: "); CreatBiTree(&T); /*創建二叉樹*/ printf(" The squence of layerorder traversaling binary tree: "); layerOrderTraverse(T); printf(" The squence of PreOrder traversaling binary tree: "); PreOrderTraverse(T); layerOrderTraverse2(T); getchar(); getchar(); } －End－