用 C++ 代码实现 二叉树层序遍历
时间: 2023-06-25 11:04:23 浏览: 67
下面是用 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 == NULL) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; 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(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
levelOrder(root);
return 0;
}
```
在这个代码中,我们使用了一个队列来实现层序遍历。首先将根节点加入到队列中,然后开始循环处理队列中的节点。每次循环开始时,我们先记录下当前队列的大小 $n$,然后对于队列中的前 $n$ 个节点,依次取出来,打印它们的值,并将它们的左右子节点加入到队列中。这样,我们就完成了一层的遍历。接下来继续循环处理队列中的节点,直到队列为空为止。