void creat(BiTree &Tree)//构建二叉树 void PostOrder(BiTree Tree)//输出后缀表达式
时间: 2024-01-14 20:04:27 浏览: 206
前缀和后缀表达式建二叉树
5星 · 资源好评率100%
好的,我可以为你提供一个C++的实现。
首先,我们需要定义二叉树的节点结构体。
```cpp
struct TreeNode {
char val; // 节点的值,这里假设是字符类型
TreeNode* left; // 左子节点
TreeNode* right; // 右子节点
TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};
```
然后,我们可以按照前缀表达式的顺序构建二叉树。
```cpp
void creat(TreeNode* &Tree) {
char val;
cin >> val;
if (val == '#') { // 如果输入的是 #,表示这个节点是空节点
Tree = nullptr;
} else {
Tree = new TreeNode(val); // 创建一个新的节点
creat(Tree->left); // 构建左子树
creat(Tree->right); // 构建右子树
}
}
```
最后,我们可以按照后序遍历的顺序输出后缀表达式。
```cpp
void PostOrder(TreeNode* Tree) {
if (Tree == nullptr) {
return;
}
PostOrder(Tree->left); // 输出左子树的后缀表达式
PostOrder(Tree->right); // 输出右子树的后缀表达式
cout << Tree->val << " "; // 输出根节点的值
}
```
完整的代码如下:
```cpp
#include <iostream>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};
void creat(TreeNode* &Tree) {
char val;
cin >> val;
if (val == '#') {
Tree = nullptr;
} else {
Tree = new TreeNode(val);
creat(Tree->left);
creat(Tree->right);
}
}
void PostOrder(TreeNode* Tree) {
if (Tree == nullptr) {
return;
}
PostOrder(Tree->left);
PostOrder(Tree->right);
cout << Tree->val << " ";
}
int main() {
TreeNode* root;
creat(root);
PostOrder(root);
return 0;
}
```
当你输入前缀表达式并按回车键后,程序会输出后缀表达式。注意,输入的表达式中操作数必须是单个字符,操作符可以是加减乘除等常见的运算符,但是不支持括号。
阅读全文