数据结构 树【二叉树的广度优先搜索:层序遍历】

2022-07-15 09:35:57

前言-新方法尝试

以前学完知识或写完算法题后,直接就写博客记录下来。

然而因为记录完博客后,以为知识都记住了,就没有再管。

但过了不久,知识和算法就只记得五成了,典型的掌握不牢固。

所以今天试一试新的方法,在学完知识或做完题后,不要急着记下来,而是每天晚上抽一段时间,重新做一遍题,想一遍知识,再将今天学到的知识或解题思路总结成博客。

每过三五天,再回头看一遍博客来加深印象,慢慢吃透。

过一段时间和大家反馈效果。

今天分享一个经典算法:二叉树的广度优先搜索:层序遍历。

【这道题同时也是牛客网的NC15,有兴趣的朋友可以搜题号】

一、层序遍历

设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,

首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,

以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

如下面这棵树:

其层序遍历的结果即为:3,9,20,15,7。

二、思路

对于二叉树的层序遍历,我们需要用到队列这个数据结构:

进行判空操作,如果根节点为NULL,则直接return。

创建一个vector容器,存放最终的结果。

再创建一个queue容器,用队列存储结点。

首先,根节点入队:

然后,进行一个大的while循环,循环条件是当前队列不为空。

建立一个临时vector<int>容器,存放当前层结点的值;

然后创建一个number,记录当前队列中的元素个数,也就是当前层的元素个数。

进行一个for循环,次数为当前层的元素个数。

每一次循环,都将该元素先用一个临时指针记录,出队;

然后再将利用临时指针,将该元素的值写进本层vector中。

再依次让其左右孩子入队。

这样for循环一轮后,本层的元素全部出队,并按顺序记录到了最终的结果集中;

而下一层的元素全部入队。

直到总队列为空,代表所有元素已遍历完成。

最后用迭代器输出一下结果集容器即可。

三、代码

//层序遍历
void levelOrder(Tree t)
{
	if (t == NULL)
	{
		return;
	}
	//向量容器,存放层序遍历结果
	vector<int> result;
	//用队列存储结点
	queue<Node*> q;
	//根节点入队
	q.push(t);
	//只要当前队列不为空
	while (!q.empty())
	{
		//用于存储当前遍历这一层的结点
		vector<int> temp;
		//记录当前队列内的元素个数
		int n = q.size();
		//开始循环,依次将本层的元素出队,
		//并且让本层元素的左右孩子入队。
		for (int i = 0; i < n; i++)
		{
			//临时结点,用来存放本层的各元素
			Node* cur = q.front();
			//本层第i+1个元素出队
			q.pop();
			//本层第i+1个元素的值存进temp中
			temp.push_back(cur->data);
			//左右孩子入队
			if (cur->left != NULL)
			{
				q.push(cur->left);
			}
			if (cur->right != NULL)
			{
				q.push(cur->right);
			}
		}
		//将本层结果保存到结果向量容器中
		for (vector<int>::iterator it = temp.begin(); it != temp.end(); it++)
		{
			result.push_back(*it);
		}
	}
	for (vector<int>::iterator it = result.begin(); it != result.end(); it++)
	{
		cout << *it << " ";
	}
}

四、测试

测试代码:

int main()
{
	Tree t = NULL;
	Tree* tt = &t;
	insert(tt, 5);
	insert(tt, 3);
	insert(tt, 4);
	insert(tt, 8);
	insert(tt, 9);
	insert(tt, 1);
	levelOrder(t);
	releaseTree(t);
	return 0;
}

运行截图:

  • 作者:Kukeoo
  • 原文链接:https://blog.csdn.net/Kukeoo/article/details/114378616
    更新时间:2022-07-15 09:35:57