問題描述：

給你一個二叉樹，請你返回其按 層序遍歷 得到的節(jié)點值。 （即逐層地，從左到右訪問所有節(jié)點）。

示例：
二叉樹：[3,9,20,null,null,15,7]

返回其層次遍歷結(jié)果：

[
[3],
[9,20],
[15,7]
]
通過

來源：力扣（LeetCode）
二叉樹的層序遍歷

目錄

1.非遞歸用循環(huán)隊列
2.遞歸實現(xiàn)層次遍歷

在棧與隊列：匹配問題都是棧的強項中提到，「遞歸的實現(xiàn)就是：每一次遞歸調(diào)用都會把函數(shù)的局部變量、參數(shù)值和返回地址等壓入調(diào)用棧中」，然后遞歸返回的時候，從棧頂彈出上一次遞歸的各項參數(shù)，所以這就是遞歸為什么可以返回上一層位置的原因。

知識前提：循環(huán)隊列，二叉樹的基本運算

非遞歸用循環(huán)隊列

//思路
進(jìn)行層次遍歷時構(gòu)建一個輔助隊列，先將二叉樹根節(jié)點入隊，然后出隊，訪問出隊結(jié)點，若它有左子樹，將左子樹根節(jié)點入隊，然后出隊，訪問出隊結(jié)點…，右子樹也同樣如此，循環(huán)往復(fù)直到隊列為空

1.構(gòu)建好輔助隊列Q和二叉樹T；
2.首先將二叉樹的T（根節(jié)點）入隊列；
3.進(jìn)入while循環(huán)，退出條件 ：隊列為空；
4.循環(huán)內(nèi)部：首先將隊列中的隊首元素出棧，并且輸出他的值；
若隊首元素（剛剛出隊的元素）有左子樹，將其左子樹入隊
若隊首元素（剛剛出隊的元素）有右子樹，將其右子樹入隊
詳細(xì)代碼（可直接運行）

補充：如何讓輸出為一層一行

方法說起來很簡單，只要仔細(xì)想，應(yīng)該都能想出這種方法來。

定義兩個變量curLevelCount和nextLevelCount來分別保存當(dāng)前層和下一層的結(jié)點數(shù)。

顯然，curLevelCount的初始值為1，因為只有一個根結(jié)點，而nextLevelCount由于未知，故置為0.

思路：
1.輸出一行一行的與之前輸出為一行的代碼大體相似
2.構(gòu)建好輔助隊列Q和二叉樹T；
3.再定義兩個變量：curLevelCount用于記錄當(dāng)前層次結(jié)點個數(shù)，nextLevelCount用于記錄當(dāng)前層次的下一層結(jié)點的個數(shù)
4.將二叉樹的根節(jié)點入棧，同時curLevelCount=1，nextLevelCount=0；
5.進(jìn)入while循環(huán)，退出條件 ：隊列為空；
6.循環(huán)內(nèi)部：首先將隊列中的隊首元素出棧，并且輸出他的值；（與此同時，將curLevelCount–)；
若隊首元素（剛剛出隊的元素）有左子樹，將其左子樹入隊.(與此同時，將nextLevelCount++);
若隊首元素（剛剛出隊的元素）有右子樹，將其右子樹入隊.（與此同時，將nextLevelCount++);
若curLevelCount減到零：輸出一個換行符，將nextLevelCount賦值給curLevelCount，
nextLevelCount=0；
代碼：非遞歸用循環(huán)隊列

#include<stdio.h>typedef int Status; #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OK 1 #include<malloc.h> #include<stdlib.h> #include<stdio.h> #include<bits/stdc++.h> typedef char TElemType; typedef int status; typedef struct BiNode {TElemType data;struct BiNode *lchild;struct BiNode *rchild; }BiNode,*BiTree; typedef BiTree ElemType; typedef BiTree QElemType; //----------循環(huán)隊列 --順序存儲結(jié)構(gòu)----------------------- #define MAXQSIZE 100 // 最大隊列長度+1 typedef struct {ElemType *base; // 初始化的動態(tài)分配存儲空間int front; // 頭指針，若隊列不空，指向隊列頭元素int rear; // 尾指針，若隊列不空，指向隊列尾元素的下一個位置 } SqQueue; void InitQueue(SqQueue &Q) { // 構(gòu)造一個空隊列QQ.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));if(!Q.base) // 存儲分配失敗exit(0);Q.front = Q.rear = 0; } void DestroyQueue(SqQueue &Q) { // 銷毀隊列Q，Q不再存在if(Q.base)free(Q.base);Q.base = NULL;Q.front = Q.rear = 0; } int QueueLength(SqQueue &Q) {return ((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE); } Status EnQueue(SqQueue &Q, QElemType e) { // 插入元素e為Q的新的隊尾元素if((Q.rear + 1) % MAXQSIZE == Q.front) // 隊列滿return ERROR;Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXQSIZE;return OK; } Status DeQueue(SqQueue &Q, QElemType &e) { // 若隊列不空，則刪除Q的隊頭元素，用e返回其值，// 并返回OK；否則返回ERRORif(Q.front == Q.rear) // 隊列空return ERROR;e = Q.base[Q.front];Q.front = (Q.front + 1) % MAXQSIZE;return OK; } Status GetHead(SqQueue Q, QElemType &e) { // 若隊列不空，則用e返回Q的隊頭元素，并返回OK；// 否則返回ERRORif(Q.front == Q.rear) // 隊列空return ERROR;e = Q.base[Q.front];return OK; } Status QueueEmpty(SqQueue Q) {// 若隊列Q為空隊列，則返回TRUE；否則返回FALSEif(Q.front == Q.rear) // 隊列空的標(biāo)志return TRUE;elsereturn FALSE; } void traverse(SqQueue &Q) {int x;x=Q.front;int num=QueueLength(Q);for(int i=0;i<num;i++){printf("%d--",Q.base[(x++)%MAXQSIZE]);} }void CreateBiTree(BiTree &T)//二叉樹的先序創(chuàng)建 {TElemType ch;scanf("%c",&ch);if(ch=='#')T=NULL;else {T=(BiNode*)malloc(sizeof(BiNode));if(!T)exit(-1);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);} }void DestroyBiTree(BiTree &T)//二叉樹的銷毀算法 {if(T==NULL)exit(-1);else{DestroyBiTree(T->lchild);DestroyBiTree(T->rchild);free(T);} }int preorderTraverse(BiTree T)//二叉樹的先序遞歸遍歷算法 {if(T==NULL)return 0;else {printf("%c ",T->data);preorderTraverse(T->lchild);preorderTraverse(T->rchild);}} int InorderTraverse(BiTree T)//二叉樹的中序遞歸遍歷算法 {if(T==NULL)return 0;else {InorderTraverse(T->lchild);printf("%c ",T->data);InorderTraverse(T->rchild);}}int PostorderTraverse(BiTree T)//二叉樹的后序遞歸遍歷算法 {if(T==NULL)return 0;else {PostorderTraverse(T->lchild);PostorderTraverse(T->rchild);printf("%c ",T->data);}}void BiTree_level_traversal1(BiTree T)//按層輸出一行 {SqQueue Q;InitQueue(Q);EnQueue(Q,T);BiTree temp;while(!QueueEmpty(Q)){DeQueue(Q, temp);printf("%c ",temp->data);if(temp->lchild!=NULL)EnQueue(Q,temp->lchild);if(temp->rchild!=NULL)EnQueue(Q,temp->rchild);}} void BiTree_level_traversal(BiTree T)// 層次遍歷輸入一層一層的 {SqQueue Q;InitQueue(Q);EnQueue(Q,T);BiTree temp;int curLevelCount=1,nextLevelCount=0; while(!QueueEmpty(Q)){DeQueue(Q, temp);printf("%c ",temp->data);curLevelCount--;if(temp->lchild!=NULL){EnQueue(Q,temp->lchild);nextLevelCount++;}if(temp->rchild!=NULL){EnQueue(Q,temp->rchild);nextLevelCount++;}if(curLevelCount==0){printf("\n"); curLevelCount = nextLevelCount;nextLevelCount=0;}}} int main() {BiTree T;printf("創(chuàng)建樹輸入樹T的先序序列(其中使用#代表空節(jié)點)\n");CreateBiTree(T);printf("先序遍歷算法");preorderTraverse(T);printf("\n中序遍歷算法");InorderTraverse(T);printf("\n后序遍歷算法");PostorderTraverse(T);printf("\n遍歷結(jié)果為：\n");BiTree_level_traversal1(T);printf("\n一層一層的輸出\n"); BiTree_level_traversal(T); }

遞歸實現(xiàn)層次遍歷

思路：
1.先利用BiTree_height1(BiTree T)求二叉樹高度算法，求得高度
2.levelOrder( BiTree T)層次遍歷遞歸算法（這個函數(shù)僅一個for循環(huán)），用for（）將二叉樹一層一層的輸出，每一層輸出完，再輸出一個換行符。
3.printNodeAtLevel(BiTree T,int level)（真正的遞歸遍歷輸出函數(shù)）。
若level==0，輸入此時的T->data;

int BiTree_height1(BiTree T)//求樹的深度算法1 {if(T==NULL)return 0;else{if(BiTree_height1(T->lchild)>BiTree_height1(T->rchild))return 1+BiTree_height1(T->lchild);elsereturn 1+BiTree_height1(T->rchild);}} void printNodeAtLevel(BiTree T,int level) { if(T==NULL||level<0) return; if(level==0) { printf("%c ",T->data);return; } // 左子樹的 level - 1 級 printNodeAtLevel(T->lchild,level-1); // 右子樹的 level - 1 級 printNodeAtLevel(T->rchild,level-1); }void levelOrder(const BiTree T) {if(T==NULL)return;int totalLevel = BiTree_height1(T);for(int i = 0; i< totalLevel; i++){printNodeAtLevel(T, i);printf("\n");//打印完一層，換行} }

代碼：遞歸實現(xiàn)（全部代碼）

#include<stdio.h> #include<bits/stdc++.h> typedef char TElemType; typedef int status; typedef struct BiNode {TElemType data;struct BiNode *lchild;struct BiNode *rchild; }BiNode,*BiTree; void CreateBiTree(BiTree &T)//二叉樹的先序創(chuàng)建 {TElemType ch;scanf("%c",&ch);if(ch=='#')T=NULL;else {T=(BiNode*)malloc(sizeof(BiNode));if(!T)exit(-1);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);} }void DestroyBiTree(BiTree &T)//二叉樹的銷毀算法 {if(T==NULL)exit(-1);else{DestroyBiTree(T->lchild);DestroyBiTree(T->rchild);free(T);} }int preorderTraverse(BiTree T)//二叉樹的先序遞歸遍歷算法 {if(T==NULL)return 0;else {printf("%c ",T->data);preorderTraverse(T->lchild);preorderTraverse(T->rchild);}} int InorderTraverse(BiTree T)//二叉樹的中序遞歸遍歷算法 {if(T==NULL)return 0;else {InorderTraverse(T->lchild);printf("%c ",T->data);InorderTraverse(T->rchild);}}int PostorderTraverse(BiTree T)//二叉樹的后序遞歸遍歷算法 {if(T==NULL)return 0;else {PostorderTraverse(T->lchild);PostorderTraverse(T->rchild);printf("%c ",T->data);}}int BiTree_height1(BiTree T)//求樹的深度算法1 {if(T==NULL)return 0;else{if(BiTree_height1(T->lchild)>BiTree_height1(T->rchild))return 1+BiTree_height1(T->lchild);elsereturn 1+BiTree_height1(T->rchild);}} void printNodeAtLevel(BiTree T,int level) { if(T==NULL||level<0) return; if(level==0) { printf("%c ",T->data);return; } // 左子樹的 level - 1 級 printNodeAtLevel(T->lchild,level-1); // 右子樹的 level - 1 級 printNodeAtLevel(T->rchild,level-1); }void levelOrder(const BiTree T) {if(T==NULL)return;int totalLevel = BiTree_height1(T);for(int i = 0; i< totalLevel; i++){printNodeAtLevel(T, i);printf("\n");//打印完一層，換行} } int main() {BiTree T;printf("創(chuàng)建樹輸入樹T的先序序列(其中使用#代表空節(jié)點)\n");CreateBiTree(T);printf("先序遍歷算法");preorderTraverse(T);printf("\n中序遍歷算法");InorderTraverse(T);printf("\n后序遍歷算法");PostorderTraverse(T);printf("\n二叉樹層次遍歷算法\n");levelOrder(T);}

總結(jié)

以上是生活随笔為你收集整理的数据结构——二叉树的层次遍历的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。