用C++写一个程序btree.cpp,实现二叉树的运算（1）括号串A(B(D,E(H(J,K(L,M(,N))))),(2)输出二叉树b(采用凹入表示法）（3）输出‘H’结点的左，右孩子的结点值（4）输出二叉树b的高度（5）释放二叉树b（6）利用先序序列和中序序列重新构造二叉树，并以括号表示法输出该二叉树

以下是 btree.cpp 的代码实现：

#include <iostream>
#include <stack>
#include <cstring>

using namespace std;

// 二叉树结构体
struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};

// 根据括号串构建二叉树
TreeNode* buildTree(string s) {
    stack<TreeNode*> st;
    TreeNode* root = NULL;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            continue;
        } else if (s[i] == ')') {
            st.pop();
        } else {
            TreeNode* node = new TreeNode(s[i]);
            if (root == NULL) {
                root = node;
            } else {
                TreeNode* parent = st.top();
                if (parent->left == NULL) {
                    parent->left = node;
                } else {
                    parent->right = node;
                }
            }
            st.push(node);
        }
    }
    return root;
}

// 输出二叉树（凹入表示法）
void printTree(TreeNode* root, int depth) {
    if (root == NULL) {
        return;
    }
    printTree(root->right, depth+1);
    for (int i = 0; i < depth; i++) {
        cout << "    ";
    }
    cout << root->val << endl;
    printTree(root->left, depth+1);
}

// 查找节点
void findNode(TreeNode* root, char target, char& leftChild, char& rightChild) {
    if (root == NULL) {
        return;
    }
    if (root->val == target) {
        if (root->left != NULL) {
            leftChild = root->left->val;
        }
        if (root->right != NULL) {
            rightChild = root->right->val;
        }
    } else {
        findNode(root->left, target, leftChild, rightChild);
        findNode(root->right, target, leftChild, rightChild);
    }
}

// 计算二叉树高度
int treeHeight(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

// 释放二叉树内存
void freeTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

// 根据先序序列和中序序列构建二叉树
TreeNode* buildTreeFromPreAndIn(string preOrder, string inOrder) {
    if (preOrder.empty() || inOrder.empty()) {
        return NULL;
    }
    TreeNode* root = new TreeNode(preOrder[0]);
    int pos = inOrder.find(preOrder[0]);
    root->left = buildTreeFromPreAndIn(preOrder.substr(1, pos), inOrder.substr(0, pos));
    root->right = buildTreeFromPreAndIn(preOrder.substr(pos+1), inOrder.substr(pos+1));
    return root;
}

// 输出二叉树括号表示法
void printTreeParenthesis(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->val;
    if (root->left != NULL || root->right != NULL) {
        cout << "(";
        printTreeParenthesis(root->left);
        cout << ",";
        printTreeParenthesis(root->right);
        cout << ")";
    }
}

int main() {
    // 构建二叉树
    string s = "A(B(D,E(H(J,K(L,M(,N))))))";
    TreeNode* root = buildTree(s);

    // 输出二叉树
    cout << "二叉树: " << endl;
    printTree(root, 0);

    // 查找节点
    char leftChild = '-';
    char rightChild = '-';
    findNode(root, 'H', leftChild, rightChild);
    cout << "H节点的左孩子: " << leftChild << endl;
    cout << "H节点的右孩子: " << rightChild << endl;

    // 计算二叉树高度
    int height = treeHeight(root);
    cout << "二叉树高度: " << height << endl;

    // 释放二叉树内存
    freeTree(root);

    // 构建二叉树并输出括号表示法
    string preOrder = "ABDEHJKLNM";
    string inOrder = "DBEJHKLMNA";
    root = buildTreeFromPreAndIn(preOrder, inOrder);
    cout << "重构后的二叉树: " << endl;
    printTreeParenthesis(root);
    cout << endl;

    // 释放内存
    freeTree(root);

    return 0;
}

以上代码实现了以下功能：

1. 根据括号串构建二叉树。
2. 输出二叉树（凹入表示法）。
3. 查找节点并输出其左孩子和右孩子的值。
4. 计算二叉树的高度。
5. 释放二叉树内存。
6. 根据先序序列和中序序列构建二叉树，并以括号表示法输出该二叉树。