实验内容与步骤 （1）构造利用二叉链表存储表示的二叉树； （2）利用先序遍历创建一个二叉树； （3）递归计算二叉树的深度和叶子结点的个数。用c语言实现

实验内容与步骤：

1. **构建二叉链表表示的二叉树**:
- 定义一个结构体 `Node`，包含一个整数值 `val`、指向左孩子的指针 `left` 和指向右孩子的指针 `right`，以及一个用于链接前驱节点的指针 `prev`（用于辅助链表操作）。
- 创建二叉树的基本函数会接收两个参数：当前节点值和前驱节点，通过连续分配内存并连接节点完成二叉链表的构建。

2. **利用先序遍历创建二叉树**:
- 先序遍历顺序通常是根-左-右。编写一个递归函数，首先访问当前节点，然后对左右孩子分别进行递归调用，将节点插入到链表中。

3. **递归计算二叉树深度和叶子结点的个数**:
- 深度函数：从根节点开始，递归地检查每个子树的最大深度，返回整个树的最大深度加一。
- 叶子结点计数：同样递归，判断当前节点是否为叶子（没有子节点），如果是则累加计数，同时通知下一层也统计其子树的叶子结点。

以下是简单的C语言实现示例：

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

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
    struct Node* prev;
} Node;

// 先序遍历并构造二叉树
void createTree(Node** root, int arr[], int n) {
    for (int i = 0; i < n; i++) {
        *root = (Node*)malloc(sizeof(Node));
        (*root)->val = arr[i];
        if (!i)
            (*root)->prev = NULL;
        else {
            Node* last = (*(root)-1)->prev;
            if (last != NULL) {
                last->right = *root;
                *root->prev = last;
            } else {
                *root->prev = NULL;
            }
        }
        if (i == 0)
            (*root)->left = NULL;
        else {
            (*root)->left = createTree(&(*root)->left, arr + (i << 1), i / 2);
        }
        if (i % 2 == 1)
            (*root)->right = createTree(&(*root)->right, arr + ((i + 1) << 1), (n - i - 2) / 2);
    }
}

// 计算深度和叶子结点个数
int depth(Node* root) {
    if (root == NULL)
        return 0;
    else
        return 1 + max(depth(root->left), depth(root->right));
}

int countLeaves(Node* root) {
    if (root == NULL)
        return 0;
    else if (root->left == NULL && root->right == NULL)
        return 1;
    else
        return countLeaves(root->left) + countLeaves(root->right);
}

// 示例主函数
int main() {
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    Node* root = NULL;
    createTree(&root, arr, n);
    printf("Depth of the tree: %d\n", depth(root));
    printf("Number of leaves: %d\n", countLeaves(root));
    return 0;
}