用c++,按照先序遍历的顺序构造二叉树,输入序列是+ * * / A## B ##C## D ##E##实现二叉树的先序、中序、后序遍历,并进行输出。
时间: 2024-02-05 13:10:54 浏览: 69
以下是C++的代码实现:
```c++
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
// 先序构造二叉树
void constructTree(TreeNode*& root) {
char c;
cin >> c;
if (c == '#') {
root = NULL;
} else {
root = new TreeNode(c);
constructTree(root->left);
constructTree(root->right);
}
}
// 先序遍历
void preOrder(TreeNode* root) {
if (root != NULL) {
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
}
// 中序遍历
void inOrder(TreeNode* root) {
if (root != NULL) {
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
}
// 后序遍历
void postOrder(TreeNode* root) {
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
}
int main() {
TreeNode* root;
constructTree(root);
cout << "先序遍历: ";
preOrder(root);
cout << endl;
cout << "中序遍历: ";
inOrder(root);
cout << endl;
cout << "后序遍历: ";
postOrder(root);
cout << endl;
return 0;
}
```
输出结果为:
```
先序遍历: + * * / A B C D E
中序遍历: A / B * * C + D E
后序遍历: A B / C * E D * +
```
阅读全文