编写一个程序exp4.cpp,实现二叉树的先序遍历、中序遍历和后序遍历的递归和非递归算法,以及层次遍历的算法,并对下图所示的二叉树给出求解结果。
时间: 2023-03-19 20:27:45 浏览: 167
很抱歉,我是AI语言模型,无法看到您提供的图片。但是,我可以为您提供二叉树遍历的代码示例:
```c++
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
// 二叉树结点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 递归实现先序遍历
void preorderRecursive(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " ";
preorderRecursive(root->left);
preorderRecursive(root->right);
}
// 非递归实现先序遍历
void preorderNonRecursive(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
cout << node->val << " ";
if (node->right != NULL) s.push(node->right);
if (node->left != NULL) s.push(node->left);
}
}
// 递归实现中序遍历
void inorderRecursive(TreeNode* root) {
if (root == NULL) return;
inorderRecursive(root->left);
cout << root->val << " ";
inorderRecursive(root->right);
}
// 非递归实现中序遍历
void inorderNonRecursive(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> s;
TreeNode* node = root;
while (node != NULL || !s.empty()) {
while (node != NULL) {
s.push(node);
node = node->left;
}
node = s.top();
s.pop();
cout << node->val << " ";
node = node->right;
}
}
// 递归实现后序遍历
void postorderRecursive(TreeNode* root) {
if (root == NULL) return;
postorderRecursive(root->left);
postorderRecursive(root->right);
cout << root->val << " ";
}
// 非递归实现后序遍历
void postorderNonRecursive(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode* node = s1.top();
s1.pop();
s2.push(node);
if (node->left != NULL) s1.push(node->left);
if (node->right != NULL) s1.push(node->right);
}
while (!s2.empty()) {
TreeNode* node = s2.top();
s2.pop();
cout << node->val << " ";
}
}
// 层次遍历
void levelorder(TreeNode* root) {
if (root == NULL) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = ; i < size; i++) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != NULL) q.push(node->left);
if (node->right != NULL) 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);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
// 先序遍历
cout << "Preorder (recursive): ";
preorderRecursive(root);
cout << endl;
cout << "Preorder (non-recursive): ";
preorderNonRecursive(root);
cout << endl;
// 中序遍历
cout << "Inorder (recursive): ";
inorderRecursive(root);
cout << endl;
cout << "Inorder (non-recursive): ";
inorderNonRecursive(root);
cout << endl;
// 后序遍历
cout << "Postorder (recursive): ";
postorderRecursive(root);
cout << endl;
cout << "Postorder (non-recursive): ";
postorderNonRecursive(root);
cout << endl;
// 层次遍历
cout << "Levelorder: ";
levelorder(root);
cout << endl;
return ;
}
```
您可以根据需要选择递归或非递归算法进行遍历。