第 5 章 · 树与二叉树

树 = 「一对多」分层结构；二叉树每节点最多两孩子，BST/AVL/堆全是二叉树。

5.1 定义与存储

typedef struct TNode { int val; struct TNode *left, *right; } TNode;

每个节点两个指针，比链表多一个分支（见第 2 章、第 12 章）。

5.2 四种遍历

遍历	顺序	典型用途
先序	根 → 左 → 右	复制树、求前缀表达式
中序	左 → 根 → 右	BST 得到有序序列
后序	左 → 右 → 根	释放树、求后缀表达式
层序	逐层从左到右	求高度、BFS

void inorder(TNode *r) {          // 递归中序
    if (!r) return;
    inorder(r->left);
    printf("%d ", r->val);
    inorder(r->right);
}

// 层序遍历：借助队列（第 3 章）
void level(TNode *r) {
    if (!r) return;
    TNode *q[1000]; int f = 0, b = 0;
    q[b++] = r;
    while (f < b) {
        TNode *n = q[f++];
        printf("%d ", n->val);
        if (n->left)  q[b++] = n->left;
        if (n->right) q[b++] = n->right;
    }
}

5.3 BST：二叉搜索树

左 < 根 < 右。查找/插入沿一条路径下沉，O(h)；但按升序插入会退化成链表，h = n。

TNode *insert(TNode *r, int v) {
    if (!r) {
        TNode *n = malloc(sizeof(*n));
        if (!n) return NULL;
        n->val = v; n->left = n->right = NULL;
        return n;
    }
    if (v < r->val) r->left = insert(r->left, v);
    else if (v > r->val) r->right = insert(r->right, v);
    return r;
}

删除分三种：叶子直接删、单孩子用孩子顶替、双孩子用中序后继（右子树最左）替换值再删后继。

5.4 AVL：自平衡

每个节点记录平衡因子「左高 − 右高」，绝对值 > 1 时旋转修正，保证 |h左 − h右| ≤ 1，从而 h = O(log n)。四种失衡：LL、RR 单旋（右旋/左旋）；LR、RL 先旋成 LL/RR 再旋。查找、插入、删除都 O(log n)。

5.5 堆：完全二叉树的数组存储

堆是完全二叉树，可用数组存（父下标 i，左孩子 2i+1，右孩子 2i+2）。大顶堆：每个节点 ≥ 孩子。

// 上浮：新元素插末尾，与父比较交换（大顶堆）
void up(int *h, int i) {
    while (i > 0 && h[(i - 1) / 2] < h[i]) {
        int t = h[i]; h[i] = h[(i - 1) / 2]; h[(i - 1) / 2] = t;
        i = (i - 1) / 2;
    }
}

取堆顶 O(1)，插入/删除 O(log n)。堆用于优先队列和堆排序（第 8 章）。

对比：BST vs AVL vs 堆——

结构	有序性	平衡	操作复杂度	用途
BST	中序有序	否，可退化	平均 O(log n)，最坏 O(n)	动态查/插/删
AVL	中序有序	严格平衡	稳定 O(log n)	频繁查找 + 增删
堆	仅「父 ≥ 子」	完全二叉树	O(log n)	取最大/最小、优先队列

堆不做「有序遍历」，它只要「最大/最小」；BST/AVL 要的是全序。

对比：递归简洁但每层压栈帧（见 C 指针第 2 章）、深树可能溢出；非递归显式用栈（第 3 章）更安全但代码更绕。