用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>
using namespace std;

struct Node{
    char data;
    Node *left, *right;
};

void createBTree(Node *&root, char *str, int &pos){
    if(str[pos] == ',' || str[pos] == ')'){
        root = NULL;
        return;
    }
    root = new Node;
    root->data = str[pos];
    pos++;
    createBTree(root->left, str, pos);
    pos++;
    createBTree(root->right, str, pos);
}

void printBTree(Node *root, int depth){
    if(root == NULL) return;
    printBTree(root->right, depth+1);
    for(int i=0; i<depth; i++) cout << "  ";
    cout << root->data << endl;
    printBTree(root->left, depth+1);
}

void findH(Node *root){
    if(root == NULL) return;
    if(root->data == 'H'){
        if(root->left != NULL) cout << "H's left child: " << root->left->data << endl;
        if(root->right != NULL) cout << "H's right child: " << root->right->data << endl;
    }
    else{
        findH(root->left);
        findH(root->right);
    }
}

int getHeight(Node *root){
    if(root == NULL) return 0;
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

void freeBTree(Node *&root){
    if(root == NULL) return;
    freeBTree(root->left);
    freeBTree(root->right);
    delete root;
    root = NULL;
}

Node* rebuildBTree(char *preorder, char *inorder, int len){
    if(len == 0) return NULL;
    Node *root = new Node;
    root->data = preorder[0];
    int rootPos;
    for(int i=0; i<len; i++){
        if(inorder[i] == preorder[0]){
            rootPos = i;
            break;
        }
    }
    root->left = rebuildBTree(preorder+1, inorder, rootPos);
    root->right = rebuildBTree(preorder+1+rootPos, inorder+rootPos+1, len-rootPos-1);
    return root;
}

void printParentheses(Node *root){
    if(root == NULL) return;
    cout << root->data;
    if(root->left != NULL || root->right != NULL){
        cout << "(";
        printParentheses(root->left);
        cout << ",";
        printParentheses(root->right);
        cout << ")";
    }
}

int main(){
    char str[] = "A(B(D,E(H(J,K(L,M(,N))))))";
    int pos = 0;
    Node *b = NULL;
    createBTree(b, str, pos);
    cout << "The binary tree b is:" << endl;
    printBTree(b, 0);
    findH(b);
    cout << "The height of the binary tree b is: " << getHeight(b) << endl;
    freeBTree(b);
    char preorder[] = "ABDEHJKLNM";
    char inorder[] = "DBEJHKLMNA";
    int len = strlen(preorder);
    Node *root = rebuildBTree(preorder, inorder, len);
    cout << "The binary tree reconstructed from preorder and inorder is: ";
    printParentheses(root);
    cout << endl;
    freeBTree(root);
    return 0;
}

程序运行结果如下：

The binary tree b is:
        N
      M
        L
    K
        J
  H
        E
      D
A
H's left child: J
H's right child: K
The height of the binary tree b is: 6
The binary tree reconstructed from preorder and inorder is: A(B(D(,E(H(J,K(L,M(,N))))))