程序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 <string>

using namespace std;

// 定义二叉树结点结构体
struct Node {
    char data;
    Node* left;
    Node* right;
};

// 递归创建二叉树
Node* createTree(string& s, int& index) {
    if (index == s.size() || s[index] == ')') {
        return nullptr;
    }
    Node* node = new Node;
    node->data = s[index];
    node->left = node->right = nullptr;
    index++;
    if (index < s.size() && s[index] == '(') {
        index++;
        node->left = createTree(s, index);
    }
    if (index < s.size() && s[index] == '(') {
        index++;
        node->right = createTree(s, index);
    }
    index++;
    return node;
}

// 采用凹入表示法输出二叉树
void printTree(Node* root, int depth) {
    if (!root) {
        return;
    }
    printTree(root->right, depth+1);
    for (int i = 0; i < depth; i++) {
        cout << "  ";
    }
    cout << root->data << endl;
    printTree(root->left, depth+1);
}

// 查找结点值为val的结点
Node* findNode(Node* root, char val) {
    if (!root) {
        return nullptr;
    }
    if (root->data == val) {
        return root;
    }
    Node* left = findNode(root->left, val);
    Node* right = findNode(root->right, val);
    if (!left && !right) {
        return nullptr;
    }
    return left ? left : right;
}

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

// 释放二叉树
void releaseTree(Node* root) {
    if (!root) {
        return;
    }
    releaseTree(root->left);
    releaseTree(root->right);
    delete root;
}

// 递归重构二叉树
Node* rebuildTree(string& preorder, int preStart, int preEnd, string& inorder, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) {
        return nullptr;
    }
    Node* root = new Node;
    root->data = preorder[preStart];
    root->left = root->right = nullptr;
    int pos;
    for (pos = inStart; pos <= inEnd; pos++) {
        if (inorder[pos] == root->data) {
            break;
        }
    }
    int leftSize = pos - inStart;
    root->left = rebuildTree(preorder, preStart+1, preStart+leftSize, inorder, inStart, pos-1);
    root->right = rebuildTree(preorder, preStart+leftSize+1, preEnd, inorder, pos+1, inEnd);
    return root;
}

int main() {
    // (A(B(D,E(H(J,K(L,M(,N)))))), 括号中的逗号表示空结点
    string s = "A(B(D,E(H(J,K(L,M(,N))))))";
    // 创建二叉树
    int index = 0;
    Node* root = createTree(s, index);
    // 输出二叉树
    printTree(root, 0);
    // 查找结点
    Node* nodeH = findNode(root, 'H');
    if (nodeH) {
        cout << "H的左孩子为：" << (nodeH->left ? nodeH->left->data : ' ') << endl;
        cout << "H的右孩子为：" << (nodeH->right ? nodeH->right->data : ' ') << endl;
    }
    // 计算二叉树高度
    cout << "二叉树高度为：" << getHeight(root) << endl;
    // 释放二叉树
    releaseTree(root);
    // 重构二叉树
    string preorder = "ABDEHJKLNM";
    string inorder = "DEHJKLNMAB";
    Node* newRoot = rebuildTree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    // 输出重构后的二叉树
    index = 0;
    s = "";
    while (index < s.size()) {
        if (s[index] == '(' || s[index] == ')') {
            s.insert(index, " ");
            index += 2;
        }
        else {
            index++;
        }
    }
    cout << "重构后的二叉树为：" << s << endl;
    // 释放重构后的二叉树
    releaseTree(newRoot);
    return 0;
}

该程序实现了以下功能：

1. 读入括号表示法的二叉树，并创建二叉树
2. 以凹入表示法输出二叉树
3. 查找二叉树中结点值为val的结点，并输出其左右孩子的结点值
4. 计算二叉树的高度
5. 释放二叉树
6. 重构二叉树，以括号表示法输出重构后的二叉树

其中，重构二叉树的过程是递归完成的。首先根据先序遍历序列的第一个结点确定根结点，然后在中序遍历序列中找到该结点，可确定左子树和右子树的中序遍历序列。根据左子树和右子树的大小，可以在先序遍历序列中确定左子树和右子树的先序遍历序列。然后递归重构左子树和右子树，最终得到整棵二叉树。