建立二叉树,并实现二叉树的遍历,先序遍历采用递归算法实现,层次遍历用非递归算法来实现。
时间: 2024-01-29 13:04:13 浏览: 25
好的,下面是C++实现的代码:
```cpp
#include <iostream>
#include <queue>
using namespace std;
// 二叉树结点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 先序遍历二叉树(递归算法)
void preOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
// 层次遍历二叉树(非递归算法)
void levelOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
}
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);
// 先序遍历二叉树
cout << "先序遍历结果:" << endl;
preOrder(root);
cout << endl;
// 层次遍历二叉树
cout << "层次遍历结果:" << endl;
levelOrder(root);
cout << endl;
return 0;
}
```
这段代码中,我们定义了一个 `TreeNode` 结构体,表示二叉树结点。然后实现了先序遍历和层次遍历两个函数。其中,先序遍历采用递归算法,层次遍历采用非递归算法,需要借助队列来实现。在 `main` 函数中,我们建立了一个二叉树,并依次调用先序遍历和层次遍历函数,输出遍历结果。