C++ 二叉树括号表达式解析：构建与输出

本文将详细讲解如何使用 C++ 二叉链表存储给定括号表达式表示的二叉树，并利用递归算法输出其括号表达式。

1. 二叉链表存储二叉树

首先，我们定义二叉树节点的结构：

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};

接下来，实现一个函数 buildTree，根据给定的括号表达式构建二叉树：

TreeNode* buildTree(string s) {
    if(s.empty()) return nullptr;
    stack<TreeNode*> stk;
    TreeNode* root = new TreeNode(s[0]);
    stk.push(root);
    int i = 1;
    while(i < s.size()) {
        if(s[i] == '(') {
            i++;
            TreeNode* node = new TreeNode(s[i]);
            if(stk.top()->left == nullptr) stk.top()->left = node;
            else stk.top()->right = node;
            stk.push(node);
        } else if(s[i] == ')') {
            stk.pop();
        } 
        i++;
    }
    return root;
}

2. 递归输出括号表达式

最后，实现一个函数 printTree，递归输出二叉树的括号表达式：

void printTree(TreeNode* root) {
    if(root == nullptr) return;
    cout << root->val;
    if(root->left != nullptr || root->right != nullptr) {
        cout << '(';
        printTree(root->left);
        if(root->right != nullptr) cout << ',';
        printTree(root->right);
        cout << ')';
    }
}

通过以上代码，我们可以成功实现将括号表达式表示的二叉树存储为二叉链表，并递归输出其括号表达式。