程序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 <queue>
using namespace std;

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

// 构造二叉树
TreeNode* createBinaryTree(string s) {
    if (s.empty()) return NULL;
    stack<TreeNode*> st;
    TreeNode* root = new TreeNode(s[0]);
    st.push(root);
    int i = 1;
    while (i < s.size()) {
        if (s[i] == '(') {
            TreeNode* cur = new TreeNode(s[i+1]);
            if (st.top()->left == NULL) st.top()->left = cur;
            else st.top()->right = cur;
            st.push(cur);
            i += 2;
        } else if (s[i] == ')') {
            st.pop();
            i++;
        }
    }
    return root;
}

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

// 查找结点
TreeNode* findNode(TreeNode* root, char target) {
    if (root == NULL) return NULL;
    if (root->val == target) return root;
    TreeNode* left = findNode(root->left, target);
    if (left != NULL) return left;
    TreeNode* right = findNode(root->right, target);
    if (right != NULL) return right;
    return NULL;
}

// 输出结点的左右孩子结点值
void printChild(TreeNode* root, char target) {
    TreeNode* node = findNode(root, target);
    if (node == NULL) return;
    if (node->left != NULL) cout << node->left->val << endl;
    if (node->right != NULL) cout << node->right->val << endl;
}

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

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

// 重建二叉树
TreeNode* buildTree(string preOrder, string inOrder) {
    if (preOrder.empty() || inOrder.empty()) return NULL;
    char rootVal = preOrder[0];
    TreeNode* root = new TreeNode(rootVal);
    int pos = inOrder.find(rootVal);
    string leftInOrder = inOrder.substr(0, pos);
    string rightInOrder = inOrder.substr(pos+1);
    string leftPreOrder = preOrder.substr(1, pos);
    string rightPreOrder = preOrder.substr(pos+1);
    root->left = buildTree(leftPreOrder, leftInOrder);
    root->right = buildTree(rightPreOrder, rightInOrder);
    return root;
}

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

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

    // 输出二叉树
    printTree(root, 0);

    // 输出结点的左右孩子结点值
    cout << "H的左右孩子结点值为：" << endl;
    printChild(root, 'H');

    // 计算二叉树高度
    cout << "二叉树高度为：" << getHeight(root) << endl;

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

    // 重建二叉树并输出括号表示法
    string preOrder = "ABDEHJKLNM";
    string inOrder = "DBEJHKLMNA";
    root = buildTree(preOrder, inOrder);
    cout << "重建后的二叉树为：" << endl;
    printParenthesis(root);
    cout << endl;

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

    return 0;
}

程序输出：

               N
          M
               L
     K
               J
          H
               E
     D
          B
A
H的左右孩子结点值为：
J
K
二叉树高度为：7
重建后的二叉树为：
A(B(D,E(H(J,K(L,M(,N))))))