层次遍历二叉树c++
时间: 2024-05-25 16:07:35 浏览: 118
层次遍历二叉树是一种基于广度优先搜索的遍历方式,它从二叉树的根节点开始,逐层遍历整个二叉树。在遍历每一层时,我们首先访问该层的所有节点,然后再依次访问下一层的节点。这种遍历方式可以帮助我们更好地理解二叉树的结构,同时也非常适合解决某些二叉树问题,如查找二叉树的最大深度等。
以下是C++实现层次遍历二叉树的代码:
```cpp
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void levelOrder(TreeNode* root) {
if (!root) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
cout << endl;
}
}
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);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
levelOrder(root);
return 0;
}
```
以上代码中,我们使用了队列来辅助实现层次遍历。我们首先将根节点入队,然后在每一层节点遍历完后,将其所有子节点入队,直到遍历完整个二叉树。
阅读全文