层次遍历的非递归算法
时间: 2024-05-20 22:08:04 浏览: 12
层次遍历是一种广度优先搜索的算法,用于遍历树或图的节点。非递归的层次遍历算法可以通过使用队列来实现。以下是层次遍历的非递归算法步骤:
1. 创建一个空队列,并将根节点入队。
2. 循环执行以下步骤,直到队列为空:
a. 出队一个节点,并访问该节点。
b. 将该节点的所有子节点依次入队。
3. 遍历结束。
这个算法通过队列的先进先出特性,保证了按层次遍历节点。每次出队一个节点时,将其子节点按顺序入队,这样可以保证下一层的节点在队列中的顺序。
相关问题
C++生成二叉树实现遍历,先序遍历采用递归算法,层次遍历采用非递归算法
好的,下面是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 createTree(TreeNode*& root) {
int val;
cin >> val;
if (val == -1) {
root = NULL;
return;
}
root = new TreeNode(val);
createTree(root->left);
createTree(root->right);
}
// 先序遍历(递归)
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 层次遍历(非递归)
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}
int main() {
TreeNode* root;
createTree(root);
cout << "先序遍历结果:";
preorderTraversal(root);
cout << endl;
cout << "层次遍历结果:";
levelOrderTraversal(root);
cout << endl;
return 0;
}
```
我已经完成了你的要求,请问还有其他问题吗?
C++生成二叉树实现遍历,先序遍历采用递归算法,层次遍历采用非递归算法并给出实例
好的,下面是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 createTree(TreeNode*& root) {
int val;
cin >> val;
if (val == -1) {
root = NULL;
return;
}
root = new TreeNode(val);
createTree(root->left);
createTree(root->right);
}
// 先序遍历(递归)
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 层次遍历(非递归)
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}
int main() {
TreeNode* root;
cout << "请输入二叉树节点的值,-1表示该节点为空:" << endl;
createTree(root);
cout << "先序遍历结果:";
preorderTraversal(root);
cout << endl;
cout << "层次遍历结果:";
levelOrderTraversal(root);
cout << endl;
return 0;
}
```
例子:
输入:
```
请输入二叉树节点的值,-1表示该节点为空:
1 2 4 -1 -1 5 -1 -1 3 -1 6 7 -1 -1 -1
```
输出:
```
先序遍历结果:1 2 4 5 3 6 7
层次遍历结果:1 2 3 4 5 6 7
```
希望能够帮到你!