用c语言构建二叉树，要求使用括号表示法输入二叉树并转化为二叉树的链式存储结构；横向输出二叉树；求二叉树的高度；统计二叉树中的节点个数；中序遍历该二叉树（采用递归算法）；层序遍历该二叉树；（代码）

用C语言构建二叉树的步骤如下：

1. 定义二叉树的节点结构体

typedef struct BiTreeNode {
    char data; // 数据域
    struct BiTreeNode *lchild; // 左子树指针
    struct BiTreeNode *rchild; // 右子树指针
} BiTreeNode, *BiTree;

2. 用括号表示法输入二叉树并转化为二叉树的链式存储结构

括号表示法是一种简单而直观的二叉树表示方法，具体规则如下：

- 空树用“#”表示；
- 非空二叉树用“(data,left,right)”表示，其中data表示当前节点的数据，left表示左子树，right表示右子树。

例如，二叉树(A,(B,(D,#,#),(E,#,#)),(C,(F,#,#),(G,#,#)))用括号表示法表示为(A,(B,(D,#,#),(E,#,#)),(C,(F,#,#),(G,#,#)))。

转化为链式存储结构的过程可以使用递归的方式，按照以下步骤进行：

- 如果输入的字符为“#”，说明当前节点为空，返回NULL；
- 否则，创建一个新节点，并将输入的字符赋值给该节点的数据域；
- 递归调用函数，将返回值赋给当前节点的左子树指针；
- 递归调用函数，将返回值赋给当前节点的右子树指针；
- 返回当前节点。

代码如下：

BiTree CreateBiTree() {
    char ch;
    scanf("%c", &ch);
    getchar(); // 读取并丢弃回车符
    if (ch == '#') { // 空树
        return NULL;
    }
    BiTreeNode *root = (BiTreeNode *)malloc(sizeof(BiTreeNode)); // 创建新节点
    root->data = ch; // 赋值
    root->lchild = CreateBiTree(); // 递归调用左子树
    root->rchild = CreateBiTree(); // 递归调用右子树
    return root;
}

3. 横向输出二叉树

横向输出二叉树可以采用递归的方式，具体步骤如下：

- 如果二叉树为空，直接返回；
- 否则，先输出右子树，再输出当前节点，最后输出左子树。

代码如下：

void PrintBiTree(BiTree T, int level) {
    if (T == NULL) { // 空树
        return;
    }
    PrintBiTree(T->rchild, level + 1); // 输出右子树
    for (int i = 0; i < level; i++) { // 输出空格
        printf("    ");
    }
    printf("%c\n", T->data); // 输出当前节点
    PrintBiTree(T->lchild, level + 1); // 输出左子树
}

4. 求二叉树的高度

求二叉树的高度可以采用递归的方式，具体步骤如下：

- 如果二叉树为空，返回0；
- 否则，分别递归计算左右子树的高度，并取其中较大值加1。

代码如下：

int GetHeight(BiTree T) {
    if (T == NULL) { // 空树
        return 0;
    }
    int left_height = GetHeight(T->lchild); // 左子树高度
    int right_height = GetHeight(T->rchild); // 右子树高度
    return (left_height > right_height ? left_height : right_height) + 1; // 取较大值加1
}

5. 统计二叉树中的节点个数

统计二叉树中的节点个数也可以采用递归的方式，具体步骤如下：

- 如果二叉树为空，返回0；
- 否则，分别递归计算左右子树的节点个数，并将它们相加，并加上当前节点。

代码如下：

int GetNodeNum(BiTree T) {
    if (T == NULL) { // 空树
        return 0;
    }
    int left_num = GetNodeNum(T->lchild); // 左子树节点个数
    int right_num = GetNodeNum(T->rchild); // 右子树节点个数
    return left_num + right_num + 1; // 左右子树节点个数相加再加上当前节点
}

6. 中序遍历该二叉树（采用递归算法）

中序遍历二叉树可以采用递归的方式，具体步骤如下：

- 如果二叉树为空，直接返回；
- 否则，先递归遍历左子树，再输出当前节点，最后递归遍历右子树。

代码如下：

void InOrderTraversal(BiTree T) {
    if (T == NULL) { // 空树
        return;
    }
    InOrderTraversal(T->lchild); // 遍历左子树
    printf("%c ", T->data); // 输出当前节点
    InOrderTraversal(T->rchild); // 遍历右子树
}

7. 层序遍历该二叉树

层序遍历可以借助队列来实现，具体步骤如下：

- 首先将二叉树的根节点入队；
- 当队列不为空时，取出队头元素并输出，然后将队头元素的左右子节点（如果存在）入队；
- 重复执行第2步，直到队列为空。

代码如下：

void LevelOrderTraversal(BiTree T) {
    if (T == NULL) { // 空树
        return;
    }
    Queue q; // 队列
    InitQueue(&q); // 初始化队列
    EnQueue(&q, T); // 根节点入队
    while (!IsEmpty(&q)) { // 队列不为空时循环
        BiTreeNode *p = DeQueue(&q); // 出队并输出队头元素
        printf("%c ", p->data);
        if (p->lchild != NULL) { // 左子节点非空时入队
            EnQueue(&q, p->lchild);
        }
        if (p->rchild != NULL) { // 右子节点非空时入队
            EnQueue(&q, p->rchild);
        }
    }
}

完整代码如下：