一、前言

        链表是最基础的数据结构之一，它通过指针将零散的内存块串联起来，形成一个线性序列。二叉树是每个节点最多有两个子节点的树结构，广泛应用于搜索、排序等场景。链表构建二叉树的核心思想就是将链表的“一个next指针”扩展为“两个指针”，分别指向左右子树， 二叉树节点本质上是一个带有两个next指针的链表节点。

二、代码详解

2.1 结构体定义

typedef struct TreeNode {
    int data;                // 节点数据
    struct TreeNode* left;   // 左子树指针
    struct TreeNode* right;  // 右子树指针
} Node, *Link;

2.2 创建节点

        这个函数接收一个整数值，使用 malloc 函数动态地从堆内存中申请一块能容纳一个 Node 结构体的空间。申请成功后，将传入的数据存入新节点的 data 域，并将其 left 和 right 指针明确设置为 NULL，表示这是一个尚未连接任何子树的孤立节点，最后将这块内存的地址返回，将这个功能独立成函数。

Link createNode(int data) {
    Link newNode = (Link)malloc(sizeof(Node));
    newNode->data = data;   // 设置节点值
    newNode->left = NULL;   // 左指针初始为空
    newNode->right = NULL;  // 右指针初始为空
    return newNode;
}

2.3 插入函数

        这个函数核心规则是：如果要插入的树为空（root == NULL），说明找到了一个合法的插入位置，直接返回一个新创建的节点。

        如果树不为空，则将待插入数据与当前根节点的数据进行比较：若小于，则递归地向左子树插入；若大于或等于，则递归地向右子树插入。

        这个递归过程会一直沿着树的分支下行，直到在某一个叶子节点的空指针位置“着陆”，然后创建新节点并沿着递归链逐级返回，更新沿途父节点的指针。

        正是这个简洁的递归逻辑，保证了最终构建出的树满足BST的性质：任意节点的左子树所有节点值都小于它，右子树所有节点值都大于或等于它。

Link insertNode(Link root, int data) {
    if (root == NULL) {    // 找到空位置了，创建新节点插入
        return createNode(data);
    }
    
    if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else {
        root->right = insertNode(root->right, data);
    }
    
    return root;
}

2.4 创建二叉树

        接受一个整数数组和其长度作为参数，初始化一个空的树根指针，然后简单地循环遍历数组，依次将每个元素通过 insertNode 函数插入树中。每次插入都可能改变树的结构，因此需要将 insertNode 返回的（可能更新的）根节点指针重新赋值给 root。

Link createTree(int arr[], int n) {
    Link root = NULL;
    for (int i = 0; i < n; i++) {
        root = insertNode(root, arr[i]);
    }
    return root;
}

2.5 三种遍历

1. 前序遍历（根、左、右）

void preOrder(Link root) {
    if (root == NULL) return;      // 1. 到终点了，返回
    printf("%d ", root->data);     // 2. 先访问根
    preOrder(root->left);          // 3. 再遍历左子树
    preOrder(root->right);         // 4. 最后遍历右子树
}

2. 中序遍历（左、根、右）

void inOrder(Link root) {
    if (root == NULL) return;      // 1. 到终点了
    inOrder(root->left);           // 2. 先遍历左子树
    printf("%d ", root->data);     // 3. 再访问根
    inOrder(root->right);          // 4. 最后遍历右子树
}

3. 后序遍历（左、右、根）

void postOrder(Link root) {
    if (root == NULL) return;      // 1. 到终点了
    postOrder(root->left);         // 2. 先遍历左子树
    postOrder(root->right);        // 3. 再遍历右子树
    printf("%d ", root->data);     // 4. 最后访问根
}

2.6 计算树的高度

• 空树高度 = 0

• 非空树高度 = max(左子树高, 右子树高) + 1

• +1的含义：当前节点自身占一层

int treeHeight(Link root) {
    if (root == NULL) return 0;    // 空树高度为0
    
    int left = treeHeight(root->left);    // 左子树高度
    int right = treeHeight(root->right);  // 右子树高度
    
    return (left > right ? left : right) + 1;  // 取较大值 + 1
}

2.7 计算节点总数

        当前树的节点数 = 1(自己) + 左子树节点数 + 右子树节点数

int countNodes(Link root) {
    if (root == NULL) return 0;    // 空节点不计数
    
    return 1 + countNodes(root->left) + countNodes(root->right);
}

2.8 释放内存

        freeTree 函数负责在程序结束前释放所有动态申请的内存，防止内存泄漏。它必须采用后序遍历的顺序：先递归释放左子树，再递归释放右子树，最后才释放根节点本身。

        这是因为如果先释放了根节点，存储在其内部的左右子节点指针就会丢失，导致其指向的整棵子树的内存都无法再被访问和释放。

void freeTree(Link root) {
    if (root == NULL) return;
    
    freeTree(root->left);   // 先拆左子树
    freeTree(root->right);  // 再拆右子树
    free(root);            // 最后拆自己
}

2.9 主函数main入口

        在 main 函数中，代码将上述所有模块串联起来：定义测试数据、调用 createTree 构建二叉树、依次执行三种遍历并打印结果、计算并输出树的高度与节点总数、最终调用 freeTree 安全清理内存。

int main() {
    int data[] = {7, 4, 5, 9, 3, 2};
    int n = sizeof(data) / sizeof(data[0]);
    
    Link root = createTree(data, n);  // 创建树
    
    // 测试各种功能
    printf("前序遍历: ");
    preOrder(root);
    
    printf("\n中序遍历: ");
    inOrder(root);
    
    printf("\n后序遍历: ");
    postOrder(root);
    
    printf("\n树高度: %d", treeHeight(root));
    printf("\n节点数: %d\n", countNodes(root));
    
    freeTree(root);  // 释放内存
    return 0;
}

二叉树结果展示图

        整个程序逻辑连贯，结构清晰，不仅实现了二叉树链表表示法的基本操作，也展示了递归思想和动态内存管理在数据结构实现中的核心应用。