当前位置：首页 > news >正文

数据结构第十六天（二叉树层序遍历/广度优先搜索（BFS）/队列使用)

news 2025/7/9 2:02:01

前言

概述

接口

源码

测试函数

运行结果

往期精彩内容

前言

从前的日色变得慢，车，马，邮件都慢，一生,只够爱一个人。

概述

二叉树的层序遍历可以使用广度优先搜索（BFS）来实现。具体步骤如下：

创建一个队列 queue，并将根节点入队。
当队列不为空时，重复执行以下步骤：

a. 弹出队头元素，并访问该节点。

b. 如果该节点有左子节点，则将其左子节点入队。

c. 如果该节点有右子节点，则将其右子节点入队。
当队列为空时，说明已经遍历完整个二叉树。

以上是层序遍历的基本思想。

现在有二叉树如下：

创建一个空的队列：根节点入队：弹出队头元素（弹出即代表访问，对该元素的操作，根据实际需求编写即可），访问该节点，此节点有两个孩子，那么B,C两个孩子入队，

入队之后，继续弹出一个元素B，访问该节点，B节点只有一个左孩子，没有右孩子，左孩子D入队，右孩子没有，不入队。

又一次弹出元素，访问此节点，若有左右节点，则入队，否则不入队。直到队列为空，广度优先搜索（BFS）结束。

接口

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;
}

测试函数

#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;
}