双重指针实现二叉树层级遍历
时间: 2023-11-20 16:06:59 浏览: 42
二叉树的层级遍历可以使用广度优先搜索算法(BFS)来实现。BFS需要使用队列来存储待遍历的节点。对于当前节点,先将其左右子节点入队,然后弹出队首节点,继续遍历其左右子节点。直到队列为空为止。
双重指针可以用于在函数中修改指针的指向,从而实现对节点的修改。在层级遍历中,我们需要用双重指针来修改队列中待遍历的节点指向其左右子节点。
下面是基于双重指针的二叉树层级遍历代码实现:
```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 == NULL) return;
queue<TreeNode**> q;
q.push(&root);
while (!q.empty()) {
TreeNode** p = q.front();
q.pop();
if ((*p)->left) q.push(&((*p)->left));
if ((*p)->right) q.push(&((*p)->right));
cout << (*p)->val << " ";
}
}
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);
levelOrder(root);
return 0;
}
```
在这段代码中,我们使用了一个指向指针的指针(`TreeNode**`)作为队列中的元素类型。在每次取出队首元素时,我们使用指针的指针来修改节点指针的指向,从而将其左右子节点入队。最终输出的是每个节点的值。