目錄
前言
概述
接口
源碼
測試函數(shù)
運行結(jié)果
往期精彩內(nèi)容
前言
從前的日色變得慢，車，馬，郵件都慢，一生,只夠愛一個人。
概述
二叉樹的層序遍歷可以使用廣度優(yōu)先搜索（BFS）來實現(xiàn)。具體步驟如下：
-
創(chuàng)建一個隊列 queue，并將根節(jié)點入隊。
-
當(dāng)隊列不為空時，重復(fù)執(zhí)行以下步驟：
a. 彈出隊頭元素，并訪問該節(jié)點。
b. 如果該節(jié)點有左子節(jié)點，則將其左子節(jié)點入隊。
c. 如果該節(jié)點有右子節(jié)點，則將其右子節(jié)點入隊。
-
當(dāng)隊列為空時，說明已經(jīng)遍歷完整個二叉樹。
?以上是層序遍歷的基本思想。
現(xiàn)在有二叉樹如下：
創(chuàng)建一個空的隊列：
根節(jié)點入隊：
彈出隊頭元素（彈出即代表訪問，對該元素的操作，根據(jù)實際需求編寫即可），訪問該節(jié)點，此節(jié)點有兩個孩子，那么B,C兩個孩子入隊，?
入隊之后，繼續(xù)彈出一個元素B，?訪問該節(jié)點，B節(jié)點只有一個左孩子，沒有右孩子，左孩子D入隊，右孩子沒有，不入隊。
又一次彈出元素，訪問此節(jié)點，若有左右節(jié)點，則入隊，否則不入隊。直到隊列為空，?廣度優(yōu)先搜索（BFS）結(jié)束。
接口
void ergodic();源碼
#include <malloc.h>
#include<string.h>
#include<iostream>
using namespace std;
class BINARYTREE
{
protected:
struct NODESTRUCT
{
char data[15];
struct NODESTRUCT* lChild;
struct NODESTRUCT* rChild;
};
struct NODESTRUCT* treeRoot=nullptr;
protected:
struct data
{
struct NODESTRUCT* nodePtr;
struct data* pre, *bk;
};
struct data* top, *button;
private:
struct NODESTRUCT* getPtrOfDataNode(char* data);
private:
void push(struct NODESTRUCT* nodePtr);
struct NODESTRUCT* pop();
public:
BINARYTREE()
{
//隊列初始化
top = button = new struct data;
button->pre = nullptr;
button->bk = nullptr;
}
void ergodic();
};
void BINARYTREE::ergodic(){
NODESTRUCT* nodePtr = nullptr;
if (treeRoot != nullptr)
{
push(treeRoot);
while (true)
{
nodePtr = pop();
if (nodePtr == nullptr)
{
break;
}
cout << nodePtr->data << endl;
if (nodePtr->lChild != nullptr)
{
push(nodePtr->lChild);
}
if (nodePtr->rChild != nullptr)
{
push(nodePtr->rChild);
}
}
}
return;
}測試函數(shù)
#include<stdio.h>
#include<iostream>
using namespace std;
#include"BINARYTREE.h"
#include<windows.h>
int main()
{BINARYTREE binaryTree;
binaryTree.initTree();
binaryTree.addLChild("A", "B");
binaryTree.addRChild("A", "C");
binaryTree.addLChild("B", "D");
binaryTree.addLChild("C", "E");
binaryTree.addRChild("C", "F");
binaryTree.ergodic();system("pause");
?? ?return 0;
}
運行結(jié)果
文章來源：http://www.zghlxwxcb.cn/news/detail-834505.html
往期精彩內(nèi)容
數(shù)據(jù)結(jié)構(gòu)第十二天（隊列）文章來源地址http://www.zghlxwxcb.cn/news/detail-834505.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)第十六天（二叉樹層序遍歷/廣度優(yōu)先搜索（BFS）/隊列使用)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
