c++二叉树层次遍历
时间: 2024-05-10 08:12:46 浏览: 8
C++二叉树的层次遍历通常使用队列实现,具体步骤如下:
1. 将根节点放入队列中。
2. 当队列不为空时,取出队头元素并访问它。
3. 如果该节点有左子节点,则将其左子节点加入队列中。
4. 如果该节点有右子节点,则将其右子节点加入队列中。
5. 重复步骤2到步骤4,直到队列为空。
层次遍历可以保证输出结果的层次性,也是二叉树的一种重要遍历方式。下面是一个示例代码:
```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()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* cur = q.front();
q.pop();
cout << cur->val << " ";
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->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;
}
```