c++队列二叉树层次遍历
时间: 2023-11-03 08:07:08 浏览: 117
C++中的队列可以使用STL中的queue来实现,二叉树的层次遍历可以使用队列来实现。具体实现步骤如下:
1. 首先将根节点入队。
2. 当队列不为空时,取出队首元素,访问该节点。
3. 如果该节点有左子节点,则将左子节点入队。
4. 如果该节点有右子节点,则将右子节点入队。
5. 重复步骤2-4,直到队列为空。
以下是C++代码实现:
```c++
#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()) {
TreeNode* cur = q.front();
q.pop();
cout << cur->val << " ";
if (cur->left) q.push(cur->left);
if (cur->right) 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);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
levelOrder(root);
return 0;
}
```
输出结果为:1 2 3 4 5 6 7
阅读全文