编写一个程序prac3-2.cpp，实现二叉树的先序遍历、中序遍历和后序遍历的递归算法，以及中序遍历的非递归算法。并对图1所示的二叉树b给出求解结果。

首先，我会给你一个基本的概念和代码示例来实现二叉树的遍历。在C++中，我们可以创建一个简单的二叉树节点结构，并分别编写递归和非递归版本的遍历函数。 ```cpp #include<iostream> using namespace std; // 定义二叉树节点结构 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; // 递归遍历函数 - 先序（根-左-右） void preorderTraversal(TreeNode* root) { if (root != NULL) { cout << root->val << " "; preorderTraversal(root->left); preorderTraversal(root->right); } } // 递归遍历函数 - 中序（左-根-右） void inorderTraversal(TreeNode* root) { if (root != NULL) { inorderTraversal(root->left); cout << root->val << " "; inorderTraversal(root->right); } } // 递归遍历函数 - 后序（左-右-根） void postorderTraversal(TreeNode* root) { if (root != NULL) { postorderTraversal(root->left); postorderTraversal(root->right); cout << root->val << " "; } } // 非递归遍历函数 - 中序（辅助栈实现） void inorderTraversalNonRecursive(TreeNode* root) { stack<TreeNode*> s; TreeNode* curr = root; while (curr || !s.empty()) { while (curr) { s.push(curr); curr = curr->left; } curr = s.top(); s.pop(); cout << curr->val << " "; curr = curr->right; } } // 图1所示二叉树的数据，假设为如下的形式 TreeNode* b = new TreeNode(1); b->left = new TreeNode(2); b->right = new TreeNode(3); b->left->left = new TreeNode(4); b->left->right = new TreeNode(5); int main() { // 打印先序遍历 cout << "Preorder Traversal: "; preorderTraversal(b); cout << endl; // 打印中序遍历 cout << "Inorder Traversal: "; inorderTraversal(b); cout << endl; // 打印后序遍历 cout << "Postorder Traversal: "; postorderTraversal(b); cout << endl; // 使用非递归中序遍历 cout << "Inorder Traversal Non-Recursive: "; inorderTraversalNonRecursive(b); cout << endl; return 0; } ``` 这段代码首先定义了二叉树节点结构，然后实现了四种遍历方法：递归的先序、中序和后序遍历，以及非递归的中序遍历。最后，在`main()`函数中创建了一个简单的二叉树实例并打印了所有遍历的结果。