實現思路

我們來看看下圖的二叉鏈表 如何實現層序遍歷。

層序遍歷順序：ABECDG
A為B、E的雙親結點，遍歷順序是 根->左->右 是不是。
而且每個結點都是這樣的遍歷順序 有木有。那么我們完全可以采用隊列的數據結構唄。A入隊->然后出隊，出隊時將其左右孩子入隊，循環隊列進行出隊，每次出隊將其左右孩子入隊。當隊列為空時，整棵樹層序遍歷完畢。還沒明白請看下面過程。
A->出隊
隊列：E、B
B->出隊
隊列：D、C、E
E->出隊
隊列：G、D、C
C->出隊
隊列：G、D
D->出隊
隊列：G
G->出隊
隊列為空，層序遍歷完畢。

二叉樹層序遍歷算法代碼

層序遍歷函數

層序遍歷核心代碼，利用了一個自己底層封裝的順序隊列。如果想知道怎么實現的呢，請看線性表：順序隊列算法實現。

//一排一排的遍歷 利用隊列的特性喲，將根結點入隊列 然后然后出入隊列，出隊列后將其左右孩子結點入隊列 //直到隊列為空 void SeqTraverse(BiTree tree) {SeqQueue queue = Init_SeqQueue();Push_SeqQueue(queue, tree);while (!IsEmpty_SeqQueue(queue)){BiTree root = Pop_SeqQueue(queue);printf("%c ", root->data);if (root->lchild)Push_SeqQueue(queue, root->lchild);if(root->rchild)Push_SeqQueue(queue, root->rchild);}printf("\n"); }

完整代碼

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include "SeqQueue.h" typedef char ElemType; typedef struct BiNode {ElemType data;struct BiNode* lchild;struct BiNode* rchild; }BiNode, *BiTree;//創建二叉鏈表 void CreateBiTree(BiTree* tree) {char c;scanf("%c", &c);if (c == ' '){*tree = NULL;return;}*tree = malloc(sizeof(BiNode));(*tree)->data = c;CreateBiTree(&(*tree)->lchild);CreateBiTree(&(*tree)->rchild);return; } //二叉鏈表 遞歸前序遍歷 void PreTraverse(BiTree tree) {if (tree == NULL){return;}printf("%c ", tree->data);PreTraverse(tree->lchild);PreTraverse(tree->rchild); }//一排一排的遍歷 利用隊列的特性喲，將根結點入隊列 然后然后出入隊列，出隊列后將其左右孩子結點入隊列 //直到隊列為空 void SeqTraverse(BiTree tree) {SeqQueue queue = Init_SeqQueue();Push_SeqQueue(queue, tree);while (!IsEmpty_SeqQueue(queue)){BiTree root = Pop_SeqQueue(queue);printf("%c ", root->data);if (root->lchild)Push_SeqQueue(queue, root->lchild);if(root->rchild)Push_SeqQueue(queue, root->rchild);}printf("\n"); }int main(int argc, char *argv[]) {BiTree tree = NULL;printf("請前序遍歷輸入結點：");CreateBiTree(&tree);printf("前序遍歷：");PreTraverse(tree);printf("\n層序遍歷：");SeqTraverse(tree);return 0; }

代碼運行檢測

我們構建如下圖的二叉樹，注意創建二叉樹輸入序列為：ABC__D__E_G__，_代表一個空格喲。

運行結果

?

總結

以上是生活随笔為你收集整理的树：二叉树的层序遍历算法（超简洁实现及详细分析）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。