某表达式用一棵二叉链表存储,编写算法输出该表达式的中缀形式,加上必要的括号。
时间: 2024-03-24 10:37:38 浏览: 64
可以使用递归算法来实现该功能,具体步骤如下:
1. 如果当前节点是叶子节点,则直接输出该节点的值;
2. 如果当前节点是运算符节点:
- 如果该运算符是加号或减号,则需要给其左右子树加上括号;
- 如果该运算符是乘号或除号,则只有当其左子树是运算符节点时才需要加括号,否则不需要加括号;
3. 递归输出左子树;
4. 输出当前节点的运算符;
5. 递归输出右子树。
下面是该算法的实现代码(假设二叉链表的节点结构如下):
```c++
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char v): val(v), left(nullptr), right(nullptr) {}
};
void inorder(TreeNode* root) {
if (root == nullptr) {
return;
}
if (root->left != nullptr && (root->val == '+' || root->val == '-')) {
cout << '(';
}
inorder(root->left);
cout << root->val;
if (root->right != nullptr && (root->val == '+' || root->val == '-' || (root->val == '*' || root->val == '/') && (root->left->val == '+' || root->left->val == '-'))) {
cout << '(';
}
inorder(root->right);
if (root->right != nullptr && (root->val == '+' || root->val == '-' || (root->val == '*' || root->val == '/') && (root->left->val == '+' || root->left->val == '-'))) {
cout << ')';
}
if (root->left != nullptr && (root->val == '*' || root->val == '/')) {
cout << '(';
}
}
```
其中,inorder函数即为中序遍历函数,root表示当前节点,val表示节点的值,left和right分别表示左子树和右子树。在函数中,我们首先判断当前节点是否为叶子节点,如果是,则直接输出节点的值;否则,我们根据节点的值和左右子树是否为运算符节点来决定是否需要加括号,并递归输出左子树和右子树。在输出右子树后,如果当前节点是乘号或除号且左子树是运算符节点,则还需要加上右括号。完整代码如下:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char v): val(v), left(nullptr), right(nullptr) {}
};
void inorder(TreeNode* root) {
if (root == nullptr) {
return;
}
if (root->left != nullptr && (root->val == '+' || root->val == '-')) {
cout << '(';
}
inorder(root->left);
cout << root->val;
if (root->right != nullptr && (root->val == '+' || root->val == '-' || (root->val == '*' || root->val == '/') && (root->left->val == '+' || root->left->val == '-'))) {
cout << '(';
}
inorder(root->right);
if (root->right != nullptr && (root->val == '+' || root->val == '-' || (root->val == '*' || root->val == '/') && (root->left->val == '+' || root->left->val == '-'))) {
cout << ')';
}
if (root->left != nullptr && (root->val == '*' || root->val == '/')) {
cout << '(';
}
}
int main() {
// 构造二叉链表,这里假设表达式为:a+b*c-(d/e+f)*g
TreeNode* root = new TreeNode('-');
root->left = new TreeNode('+');
root->right = new TreeNode('*');
root->left->left = new TreeNode('a');
root->left->right = new TreeNode('*');
root->left->right->left = new TreeNode('b');
root->left->right->right = new TreeNode('c');
root->right->left = new TreeNode('-');
root->right->right = new TreeNode('g');
root->right->left->left = new TreeNode('/');
root->right->left->right = new TreeNode('+');
root->right->left->left->left = new TreeNode('d');
root->right->left->left->right = new TreeNode('e');
root->right->left->right->left = new TreeNode('f');
// 输出中缀表达式
inorder(root);
cout << endl;
return 0;
}
```
输出结果为:
```
((a+(b*c))-((d/e)+f)*g)
```
阅读全文