C++二叉树（嵌套括号表示字符串法）代码

在C++中，我们可以使用二叉树来解析嵌套括号表示的字符串，比如常用的表达式"()"、"()"等。这通常涉及到先序遍历（Preorder Traversal）的概念，因为我们需要对每个操作符进行处理后访问其操作数。下面是一个简单的示例，使用递归结构实现一个二叉树节点以及相关的解析函数：

#include <string>
#include <stack>

// 二叉树节点定义
struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c) : val(c), left(nullptr), right(nullptr) {}
};

// 解析嵌套括号的辅助函数
bool isValid(std::string s) {
    std::stack<char> st;
    for (char ch : s) {
        if (ch == '(') {
            st.push(ch);
        } else if (ch == ')') {
            if (st.empty()) return false; // 如果栈为空，直接返回false
            st.pop();
        }
    }
    return st.empty(); // 检查栈是否为空，如果为空则有效
}

// 二叉树构建函数
TreeNode* buildTree(std::string s, int i) {
    if (i >= s.length() || !isValid(s.substr(i))) return nullptr;
    TreeNode* root = new TreeNode(s[i]);
    int j = i + 1;
    while (j < s.length() && isValid(s.substr(i, j - i))) { // 找到下一个右括号的位置
        TreeNode* left = buildTree(s, ++j); // 递归创建左子树
        TreeNode* right = buildTree(s, j); // 同理创建右子树
        if (!left || !right) return nullptr; // 子树无效，返回空指针
        root->left = left;
        root->right = right;
        j++; // 更新当前索引
    }
    return root;
}

// 示例用法
int main() {
    std::string expression = "(()())";
    TreeNode* root = buildTree(expression, 0);
    // ... 进行后续的操作，例如先序遍历展示或计算表达式结果
}