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

小明 2025-05-07 23:51:44 10

���录

前言

概述

接口

源码

测试函数

运行结果

往期精彩内容

前言

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

概述

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

  1. 创建一个队列 queue，并将根节点入队。

  2. 当队列不为空时，重复执行以下步骤：

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

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

    c. 如果该节点有右子节点，则将其右子节点入队。

  3. 当队列为空时，说明已经遍历完整个二叉树。

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

现在有二叉树如下：

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

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

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

接口

void ergodic();

源码

#include 
#include
#include
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 data lChild != nullptr)
			{
				push(nodePtr->lChild);
			}
			if (nodePtr->rChild != nullptr)
			{
				push(nodePtr->rChild);
			}
		}
	}
	return;
}

测试函数

#include

#include

using namespace std;

#include"BINARYTREE.h"

#include

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;

}

运行结果

往期精彩内容

数据结构第十二天（队列）

The End

标签：

微信