c++层次遍历二叉树算法
时间: 2024-04-30 10:15:10 浏览: 34
C++层次遍历二叉树算法是一种广度优先搜索(BFS)的算法,用于按层次顺序遍历二叉树的节点。以下是C++实现层次遍历二叉树的算法步骤:
1. 首先,创建一个队列(可以使用STL中的queue容器)来存储待访问的节点。
2. 将根节点入队。
3. 进入循环,直到队列为空:
- 从队列中取出一个节点,并访问该节点。
- 将该节点的左子节点和右子节点(如果存在)依次入队。
4. 重复步骤3,直到队列为空,即完成了层次遍历。
下面是一个示例代码实现:
```cpp
#include <iostream>
#include <queue>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr)};
void levelOrderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
std::cout << node->val << " ";
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->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);
// 层次遍历二叉树
levelOrderTraversal(root);
return 0;
}
```
输出结果为:1 2 3 4 5,表示按层次顺序遍历二叉树的节点值。