C++二叉树解决四则运算

对于使用C++实现二叉树来解决四则运算的问题，可以使用递归的方式来构建二叉树，并通过遍历二叉树进行四则运算的计算。

首先，定义一个二叉树节点类，包含操作符和操作数两个成员变量：

class TreeNode {
public:
    char op; // 操作符
    int val; // 操作数
    TreeNode* left; // 左子节点
    TreeNode* right; // 右子节点
};

然后，构建二叉树的函数可以通过递归的方式实现，根据四则运算表达式的特点，可以选择从右向左构建二叉树。例如，对于表达式 "3 + 4 * 5"，可以先构建一个节点表示乘法，然后将其右子节点设置为4，左子节点递归构建。

TreeNode* buildTree(string expr) {
    int n = expr.size();
    if (n == 0) {
        return nullptr;
    }
    
    TreeNode* root = new TreeNode();
    int idx = -1; // 记录操作符位置
    
    // 从右向左找到第一个加减法操作符的位置
    for (int i = n - 1; i >= 0; i--) {
        if (expr[i] == '+' || expr[i] == '-') {
            idx = i;
            break;
        }
    }
    
    // 如果找到了加减法操作符，将其作为根节点
    if (idx != -1) {
        root->op = expr[idx];
        root->left = buildTree(expr.substr(0, idx));
        root->right = buildTree(expr.substr(idx + 1));
        return root;
    }
    
    // 如果没有找到加减法操作符，再找乘除法操作符
    for (int i = n - 1; i >= 0; i--) {
        if (expr[i] == '*' || expr[i] == '/') {
            idx = i;
            break;
        }
    }
    
    // 如果找到了乘除法操作符，将其作为根节点
    if (idx != -1) {
        root->op = expr[idx];
        root->left = buildTree(expr.substr(0, idx));
        root->right = buildTree(expr.substr(idx + 1));
        return root;
    }
    
    // 如果没有找到操作符，说明是一个操作数，将其存入节点的val中
    root->op = '#';
    root->val = stoi(expr);
    return root;
}

最后，通过遍历二叉树来计算四则运算的结果，可以使用递归的方式实现：

int evaluateTree(TreeNode* root) {
    if (root->op == '#') {
        return root->val;
    }
    
    int leftVal = evaluateTree(root->left);
    int rightVal = evaluateTree(root->right);
    
    if (root->op == '+') {
        return leftVal + rightVal;
    } else if (root->op == '-') {
        return leftVal - rightVal;
    } else if (root->op == '*') {
        return leftVal * rightVal;
    } else if (root->op == '/') {
        return leftVal / rightVal;
    }
    
    return 0;
}

使用示例：

string expr = "3+4*5";
TreeNode* root = buildTree(expr);
int result = evaluateTree(root);
cout << "Result: " << result << endl; // 输出 23

通过以上的代码，可以使用二叉树来解决简单的四则运算问题。当然，对于复杂的表达式，可能需要更多的代码来处理。