C++生成二叉树实现遍历,先序遍历采用递归算法,层次遍历采用非递归算法并给出实例
时间: 2024-03-24 15:38:36 浏览: 96
好的,下面是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
```
希望能够帮到你!
阅读全文