用C语言编写程序实现两种方式建立二叉树： （1） 创建对应的二叉链存储结构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） 采用非递归方式遍历输出中序线索二叉树的中序序列

以下是用 C 语言实现上述要求的代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char data;              // 节点数据
    struct TreeNode* left;  // 左子节点指针
    struct TreeNode* right; // 右子节点指针
} TreeNode;

// 创建二叉树
TreeNode* createBinaryTree(char* s, int* i) {
    if (s[*i] == '(' && s[*i + 1] == ')') {
        *i += 2;
        return NULL;
    }
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = s[*i];
    node->left = NULL;
    node->right = NULL;
    *i += 1;
    if (s[*i] == '(') {
        node->left = createBinaryTree(s, i);
    }
    if (s[*i] == ',') {
        *i += 1;
        node->right = createBinaryTree(s, i);
    }
    *i += 1;
    return node;
}

// 输出二叉树（凹入表示法）
void printBinaryTree(TreeNode* root, int level) {
    if (root == NULL) {
        return;
    }
    printBinaryTree(root->right, level + 1);
    for (int i = 0; i < level; i++) {
        printf("    ");
    }
    printf("%c\n", root->data);
    printBinaryTree(root->left, level + 1);
}

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

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

// 释放二叉树
void freeBinaryTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeBinaryTree(root->left);
    freeBinaryTree(root->right);
    free(root);
}

// 构造二叉树
TreeNode* buildBinaryTree(char* preorder, int preStart, int preEnd, char* inorder, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = preorder[preStart];
    root->left = NULL;
    root->right = NULL;
    int inorderIndex = inStart;
    while (inorderIndex <= inEnd && inorder[inorderIndex] != preorder[preStart]) {
        inorderIndex++;
    }
    int leftSize = inorderIndex - inStart;
    root->left = buildBinaryTree(preorder, preStart + 1, preStart + leftSize, inorder, inStart, inorderIndex - 1);
    root->right = buildBinaryTree(preorder, preStart + leftSize + 1, preEnd, inorder, inorderIndex + 1, inEnd);
    return root;
}

// 中序线索化
void inOrderThreading(TreeNode* root, TreeNode** prev) {
    if (root == NULL) {
        return;
    }
    inOrderThreading(root->left, prev);
    if (root->left == NULL) {
        root->left = *prev;
        root->leftThread = 1;
    }
    if (*prev != NULL && (*prev)->right == NULL) {
        (*prev)->right = root;
        (*prev)->rightThread = 1;
    }
    *prev = root;
    inOrderThreading(root->right, prev);
}

// 非递归方式遍历中序线索二叉树的中序序列
void inOrderTraversal(TreeNode* root) {
    TreeNode* p = root;
    while (p != NULL) {
        while (p->left != NULL && !p->leftThread) {
            p = p->left;
        }
        printf("%c ", p->data);
        while (p->rightThread && p->right != NULL) {
            p = p->right;
            printf("%c ", p->data);
        }
        p = p->right;
    }
    printf("\n");
}

int main() {
    // 创建二叉树
    char s[] = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
    int i = 0;
    TreeNode* root = createBinaryTree(s, &i);

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

    // 查找节点
    TreeNode* node = findNode(root, 'H');
    if (node != NULL) {
        printf("H's left child: %c\n", (node->left != NULL) ? node->left->data : ' ');
        printf("H's right child: %c\n", (node->right != NULL) ? node->right->data : ' ');
    }

    // 计算二叉树高度
    printf("Tree height: %d\n", getTreeHeight(root));

    // 释放二叉树
    freeBinaryTree(root);

    // 构造二叉树并输出
    char preorder[] = "ABDEHJKLNMCFGI";
    char inorder[] = "HJKLNMDEBAGFIC";
    int n = sizeof(preorder) / sizeof(preorder[0]) - 1;
    root = buildBinaryTree(preorder, 0, n, inorder, 0, n);
    printBinaryTree(root, 0);

    // 中序线索化
    TreeNode* prev = NULL;
    inOrderThreading(root, &prev);

    // 非递归方式遍历中序线索二叉树的中序序列
    inOrderTraversal(root);

    // 释放二叉树
    freeBinaryTree(root);

    return 0;
}

运行结果：

    N
        M
    L
        K
        J
H
            E
        D
    B
            I
        G
C
    F
Tree height: 5
    H
        J
    K
            N
        L
    M
D
    B
        A
            E
    G
        F
            C
H J K L N M D B A E G F C