C++生成二叉树实现遍历,先序遍历采用递归算法,层次遍历采用非递归算法
时间: 2024-02-04 11:17:39 浏览: 95
好的,下面是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;
}
```
我已经完成了你的要求,请问还有其他问题吗?
阅读全文