C 语言二叉树

二叉树（binary tree）是每个节点最多拥有两个子节点（左子树、右子树）的树形结构，是二叉搜索树、堆等结构的基础。实现方式与链表类似，依赖结构体指针与动态内存；遍历与插入则常使用递归。

基本术语

• 根（root）：树的顶端节点。
• 左子节点 / 右子节点：每个节点最多两个子指针。
• 叶子（leaf）：左右子指针均为 NULL 的节点。
• 高度：从根到某叶的路径长度（根高度常记为 0）。平衡良好的树高度约为 O(log n)，有利于查找。

二叉树是阶数为 2 的特殊情况。插入、删除与遍历的具体规则取决于是否维护有序性以及树是否平衡。

节点定义

typedef struct node {
    int val;
    struct node *left;
    struct node *right;
} node_t;

插入（有序二叉树示例）

下列插入规则为：小于当前节点值进入左子树，大于或等于进入右子树（不保证平衡）：

void insert(node_t *tree, int val) {
    if (tree->val == 0) {
        tree->val = val;
    } else if (val < tree->val) {
        if (tree->left != NULL) {
            insert(tree->left, val);
        } else {
            tree->left = (node_t *)malloc(sizeof(node_t));
            tree->left->val = val;
            tree->left->left = NULL;
            tree->left->right = NULL;
        }
    } else {
        if (tree->right != NULL) {
            insert(tree->right, val);
        } else {
            tree->right = (node_t *)malloc(sizeof(node_t));
            tree->right->val = val;
            tree->right->left = NULL;
            tree->right->right = NULL;
        }
    }
}

新建节点后应将 left、right 置为 NULL；使用 calloc 分配时字段会被零初始化。

遍历方式概述

• 深度优先（DFS）：沿一条路径向下再回溯。常见顺序包括前序（根—左—右）、中序（左—根—右）、后序（左—右—根）。
• 广度优先（BFS）：按层访问，同层节点全部处理后再进入下一层。

对满足二叉搜索树性质的结构做中序遍历，输出序列按升序排列。

前序遍历示例

void printDFS(node_t *current) {
    if (current == NULL) {
        return;
    }
    printf("%d ", current->val);
    printDFS(current->left);
    printDFS(current->right);
}

将 printf 移至两次递归调用之间即为中序遍历；移至两次递归之后即为后序遍历。可对比三种顺序的输出差异。

本节建立了二叉树节点与递归遍历的基本模型。更复杂的平衡策略与专用树结构可在掌握指针、内存管理与递归之后继续学习。下一节介绍位掩码，用整数的单个位表示开关状态。