c++优先队列层序遍历
时间: 2023-11-03 16:00:42 浏览: 46
优先队列是一种特殊的队列,它的元素按照一定的优先级进行排列。在C语言中,可以使用最小堆来实现优先队列。堆是一种完全二叉树,它的每个节点的值都小于等于其子节点的值。在实现优先队列的层序遍历时,首先将根节点入队,然后循环执行以下步骤:取出队首元素并输出,将其左右子节点入队。重复执行以上步骤直到队列为空。
相关问题
c++ 二叉树的层序遍历
二叉树的层序遍历可以通过广度优先搜索(BFS)实现。具体实现步骤如下:
1. 创建一个队列,将根节点入队。
2. 循环执行以下步骤,直到队列为空:
- 取出队首元素,输出该元素的值。
- 如果该元素有左子节点,将左子节点入队。
- 如果该元素有右子节点,将右子节点入队。
下面是 C++ 的实现代码:
```c++
#include <iostream>
#include <queue>
using namespace std;
// 二叉树节点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 层序遍历函数
void levelOrder(TreeNode* root) {
if (root == nullptr) return; // 处理空树的情况
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
cout << cur->val << " ";
if (cur->left != nullptr) q.push(cur->left);
if (cur->right != nullptr) q.push(cur->right);
}
}
// 测试
int main() {
// 创建一棵二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 层序遍历
levelOrder(root);
return 0;
}
```
输出结果为:1 2 3 4 5。
c++ 二叉树的层序遍历 输出每层的数据
二叉树的层序遍历可以使用 BFS(广度优先搜索)来实现,具体步骤如下:
1. 新建一个队列,将根节点加入队列中。
2. 当队列不为空时,依次取出队首的节点,访问该节点的值,并将其左右子节点加入队列中。
3. 记录当前队列的节点个数,即为当前层的节点个数,依次取出这些节点,将其值存储到当前层的数组中。
4. 将当前层的数组输出,重复步骤 2 和 3,直到队列为空。
下面是 C++ 代码实现:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 定义二叉树节点
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res; // 存储每层的结果
queue<TreeNode*> q; // 定义队列
if (root != NULL) {
q.push(root); // 将根节点加入队列
}
while (!q.empty()) { // 当队列不为空时
int n = q.size(); // 记录当前队列的节点个数,即为当前层的节点个数
vector<int> level; // 存储当前层的结果
for (int i = 0; i < n; i++) {
TreeNode* node = q.front(); // 取出队首节点
q.pop(); // 弹出队首节点
level.push_back(node->val); // 存储节点值到当前层的结果中
if (node->left != NULL) {
q.push(node->left); // 将左子节点加入队列中
}
if (node->right != NULL) {
q.push(node->right); // 将右子节点加入队列中
}
}
res.push_back(level); // 将当前层的结果存储到 res 中
}
return res;
}
int main() {
// 创建二叉树
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
// 输出每层的数据
vector<vector<int>> res = levelOrder(root);
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res[i].size(); j++) {
cout << res[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
输出结果为:
```
3
9 20
15 7
```