C 语言二叉树

二叉树（binary tree）是一种节点最多有两个孩子（左孩子、右孩子）的数据结构。它是二叉搜索树、二叉堆的基础，排序和查找都靠它提速。下面先把概念和遍历过一遍。

树的基本概念

看两棵小树和一棵有序树：

几个术语：

• 根（root）：最顶上的节点。
• 左孩子 / 右孩子（left / right child）：一个节点最多两个分支。
• 叶子（leaf）：没有孩子的节点。
• 高度（height）：从根到某个叶子的节点层数，根记为 0。平衡树的高度大致是 log₂(n) 的整数部分，n 是节点总数，这就是为什么它查找快：每走一层，能砍掉一半的候选。

二叉树是"k 叉树"在 k=2 的特例。操作（插入、删除、遍历）的难度取决于树是否平衡、节点是叶还是枝。平衡树里每个节点的左右子树高度差不超过 1，深度可预测。

定义节点

和链表类似，但有两个指针：

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 {                        /* val >= tree->val */
        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 挪到两次递归中间，输出立刻变有序。练手题：把递归调用的位置换成先左、后右、最后打印自己，观察输出怎么变。

二叉树讲到这里，核心是"递归 + 两个指针"。后续二叉搜索树、堆、红黑树都在这个骨架上生长。