前缀后缀表达式二叉树C++
时间: 2024-05-25 12:08:49 浏览: 16
前缀表达式和后缀表达式都是一种不含括号的数学表达式,它们可以通过二叉树来表示,这种二叉树就是前缀/后缀表达式二叉树。
前缀表达式二叉树的构建方法是从右往左扫描前缀表达式,将操作数和操作符依次入栈,遇到操作符时从栈中弹出两个操作数作为该操作符的左右子节点,并将新的表达式入栈,直到扫描完整个前缀表达式。
后缀表达式二叉树的构建方法与前缀表达式二叉树类似,只不过是从左往右扫描后缀表达式。
以下是一个实现前缀表达式二叉树的C++代码示例:
```c++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
// 定义二叉树结构体
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char c) : val(c), left(nullptr), right(nullptr) {}
};
// 构建前缀表达式二叉树
TreeNode* buildTree(string& s) {
stack<TreeNode*> stk;
for (int i = s.size() - 1; i >= 0; i--) {
char c = s[i];
if (isdigit(c)) { // 操作数入栈
stk.push(new TreeNode(c));
} else { // 操作符出栈,构建新的表达式节点
TreeNode* node = new TreeNode(c);
node->left = stk.top();
stk.pop();
node->right = stk.top();
stk.pop();
stk.push(node);
}
}
return stk.top();
}
// 前序遍历输出二叉树
void preOrder(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
int main() {
string s = "+*1234";
TreeNode* root = buildTree(s);
preOrder(root); // 输出:+ * 1 2 3 4
return 0;
}
```