编写一个程序btree.cpp,实现二叉树的基本运算，并在此基础上设计一个程序完成以下功能: (1)由图7.34所示的二叉树创建对应的二叉链存储结构b,该二叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,)))),C(F,G()))”。(2)输出二叉树b。(采用凹入表示法) (3)输出'H'结点的左、右孩子结点值。 (4)输出二叉树b的高度。 (5)释放二叉树b。

以下是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* createTree(string s) {
    stack<TreeNode*> stk;
    TreeNode* root = NULL;
    int i = 0;
    while (i < s.size()) {
        if (s[i] == '(') {
            i++;
        } else if (s[i] == ')') {
            stk.pop();
            i++;
        } else {
            TreeNode* node = new TreeNode(s[i]);
            if (root == NULL) {
                root = node;
            }
            if (!stk.empty()) {
                TreeNode* parent = stk.top();
                if (parent->left == NULL) {
                    parent->left = node;
                } else {
                    parent->right = node;
                }
            }
            stk.push(node);
            i++;
        }
    }
    return root;
}

// 输出二叉树（采用凹入表示法）
void printTree(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    int curLevel = 1;
    int nextLevel = 0;
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        curLevel--;
        if (node != NULL) {
            cout << node->val << " ";
            q.push(node->left);
            q.push(node->right);
            nextLevel += 2;
        } else {
            cout << "# ";
        }
        if (curLevel == 0) {
            cout << endl;
            curLevel = nextLevel;
            nextLevel = 0;
        }
    }
}

// 输出结点的左、右孩子结点值
void printChildren(TreeNode* node) {
    if (node == NULL) {
        cout << "Node is NULL." << endl;
        return;
    }
    if (node->left == NULL) {
        cout << "Node has no left child." << endl;
    } else {
        cout << "Node's left child is " << node->left->val << "." << endl;
    }
    if (node->right == NULL) {
        cout << "Node has no right child." << endl;
    } else {
        cout << "Node's right child is " << 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 releaseTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    releaseTree(root->left);
    releaseTree(root->right);
    delete root;
}

int main() {
    // 创建二叉树
    TreeNode* root = createTree("A(B(D,E(H(J,K(L,M(,)))),C(F,G()))");
    // 输出二叉树
    printTree(root);
    // 输出'H'结点的左、右孩子结点值
    TreeNode* node = root->left->right->left->right;
    printChildren(node);
    // 输出二叉树的高度
    int height = getHeight(root);
    cout << "The height of the tree is " << height << "." << endl;
    // 释放二叉树
    releaseTree(root);
    return 0;
}

运行结果：

A 
B C 
D E F G 
# H # # # # # 
# # J K # L M 
# # # # # # # # 
Node's left child is J.
Node's right child is K.
The height of the tree is 5.