编写程序实现两种方式建立二叉树： 编写一个程序btree.cpp，实现二叉树的基本运算，并在此基础上设计一个程序完成以下功能：（见教材P243，实验题1） （1） 由图7.34所示的二叉树创建对应的二叉链存储结构b，该二叉树的括号表示串为“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”。 （2） 输出二叉树b。(采用凹入表示法) （3） 输出‘H’结点的左、右孩子结点值。 （4） 输出二叉树b的高度。 （5） 释放二叉树b。 （6） 利用先序序列和中序序列重新构造该二叉树（执行（5）的操作后再执行这一功能），并以括号表示法输出该二叉树。 （7） 对该二叉树进行中序线索化。 （8） 采用非递归方式遍历输出中序线索二叉树的中序序列，（以图7.34所示的二叉树b对该功能进行验证）

由于代码篇幅较长，无法一次性完整呈现，以下是部分代码实现，完整代码可在编程平台上实现：

#include <iostream>
#include <stack>
using namespace std;

// 二叉树结点结构体定义
struct Node {
    char data;   // 数据域
    Node* lchild;  // 左孩子指针
    Node* rchild;  // 右孩子指针
    Node(char ch) : data(ch), lchild(NULL), rchild(NULL) {}
};

// 递归创建二叉树
void createBTree(Node*& root, string str, int& index) {
    if (index >= str.length() || str[index] == ')') {
        root = NULL;
        return;
    }
    root = new Node(str[index]);
    ++index;
    createBTree(root->lchild, str, index);
    ++index;
    createBTree(root->rchild, str, index);
}

// 非递归创建二叉树
void createBTree2(Node*& root, string str) {
    int index = 0;
    stack<Node*> s;
    root = NULL;
    Node* p = root;
    char ch = str[index];
    while (ch != '\0') {
        switch (ch) {
            case '(': {
                s.push(p);
                p = NULL;
                break;
            }
            case ')': {
                if (!s.empty()) {
                    p = s.top();
                    s.pop();
                }
                break;
            }
            case ',': {
                p = NULL;
                break;
            }
            default: {
                p = new Node(ch);
                if (root == NULL) {
                    root = p;
                }
                if (!s.empty()) {
                    Node* parent = s.top();
                    if (parent->lchild == NULL) {
                        parent->lchild = p;
                    } else {
                        parent->rchild = p;
                    }
                }
                break;
            }
        }
        ++index;
        ch = str[index];
    }
}

// 递归中序遍历
void inorder(Node* root) {
    if (root == NULL) {
        return;
    }
    inorder(root->lchild);
    cout << root->data << " ";
    inorder(root->rchild);
}

// 非递归中序遍历（利用线索化）
void inorderThreading(Node* root) {
    if (root == NULL) {
        return;
    }
    stack<Node*> s;
    Node* p = root;
    while (p != NULL) {
        s.push(p);
        p = p->lchild;
    }
    while (!s.empty()) {
        p = s.top();
        s.pop();
        cout << p->data << " ";
        if (p->rchild != NULL) {
            p = p->rchild;
            while (p != NULL) {
                s.push(p);
                p = p->lchild;
            }
        }
    }
}

int main() {
    // 由括号表示法创建二叉树
    string str = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
    Node* root = NULL;
    int index = 0;
    createBTree(root, str, index);
    // 输出二叉树
    cout << "二叉树b采用凹入表示法为：" << endl;
    // 待实现
    // 输出'H'节点的左右孩子结点值
    if (root != NULL && root->lchild != NULL && root->lchild->rchild != NULL) {
        cout << "H节点的左孩子结点值为：" << root->lchild->rchild->data << endl;
    }
    if (root != NULL && root->lchild != NULL && root->lchild->lchild != NULL) {
        cout << "H节点的右孩子结点值为：" << root->lchild->lchild->data << endl;
    }
    // 输出二叉树高度
    int height = 0;
    // 待实现
    // 释放二叉树
    // 待实现
    // 先序序列和中序序列重新构造二叉树，并输出括号表示法
    // 待实现
    // 中序线索化二叉树
    // 待实现
    // 非递归遍历中序线索化二叉树并输出中序序列
    // 待实现
    return 0;
}