bittern.cn
4数据结构与算法分析：C语言描述（第2版）

树

树形结构

二叉树搜索树AVL树B树

🎯 AI 时代的学习建议：不要只读理论。理解这一章的设计动机（为什么需要这个概念？）和边界条件（什么情况下会失效？）。当 AI 生成的代码涉及这些概念时，你能判断它是否用对了场景。AI 能帮你总结内容，但无法替代你亲手阅读、思考、建立直觉的过程。

第4章：树（Trees）

一、导读

1.1 本章学习目标

第4章介绍树这种重要的非线性数据结构。与前面章节的线性结构不同，树结构天然适合表示具有层次关系的数据。从文件系统到数据库索引，从编译器语法树到网络路由，树结构无处不在。

本章的核心学习目标包括：

  • 理解树的基本术语和性质：根、叶、深度、高度、度、路径等概念
  • 掌握二叉树的遍历方法：前序、中序、后序、层序遍历的递归和迭代实现
  • 深入理解二叉搜索树（BST）：查找、插入、删除操作的实现和复杂度分析
  • 理解平衡树的重要性：为什么BST可能退化为链表？AVL树如何解决这个问题？
  • 了解B树的基本概念：多路搜索树如何适用于磁盘存储？
  • 掌握树的实际应用：表达式树、Huffman编码、文件系统的目录结构

1.2 为什么第四章如此重要

树是计算机科学中最重要的数据结构之一。它不仅是一种存储结构，更是一种思维方式——将复杂问题分解为层次化的子问题。

二叉搜索树是后续学习平衡树（红黑树、B树、B+树）的基础。理解BST的退化问题和平衡的必要性，是理解高级数据结构设计动机的关键。

此外，树的遍历算法（前序、中序、后序）是递归思想的经典应用，在编译器、操作系统、图形学等领域都有广泛应用。

1.3 核心问题引导

一棵有 n 个节点的二叉树，最多有多少个叶节点？

二叉搜索树在什么情况下会退化为链表？如何避免？

AVL树的四种旋转操作分别在什么情况下触发？

为什么数据库索引通常使用B树而不是二叉搜索树？

如何通过前序遍历和中序遍历唯一确定一棵二叉树？

Huffman编码为什么能实现数据压缩？它的前缀性质有什么作用？

二、核心概念详解

4.1 树的基本概念

树是由 n（n≥0）个节点组成的有限集合。当 n=0 时称为空树。在非空树中：

  • 有一个特殊的节点称为根（root）
  • 其余节点可分为 m（m≥0）个互不相交的子集 T₁, T₂, ..., Tₘ，每个子集本身又是一棵树，称为根的子树

关键术语：

  • 节点的度：节点的子树个数
  • 叶节点：度为0的节点
  • 分支节点：度不为0的节点
  • 深度/高度：从根到该节点的路径长度
  • 树的深度：树中节点的最大深度

4.2 二叉树

二叉树是每个节点最多有两个子树（左子树和右子树）的树结构，且子树有左右之分。

c
typedef struct TreeNode {
    int element;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode *createNode(int val) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->element = val;
    node->left = node->right = NULL;
    return node;
}

4.2.1 二叉树的遍历

c
// 前序遍历：根-左-右
void preorder(TreeNode *T) {
    if (T == NULL) return;
    printf("%d ", T->element);
    preorder(T->left);
    preorder(T->right);
}

// 中序遍历：左-根-右
void inorder(TreeNode *T) {
    if (T == NULL) return;
    inorder(T->left);
    printf("%d ", T->element);
    inorder(T->right);
}

// 后序遍历：左-右-根
void postorder(TreeNode *T) {
    if (T == NULL) return;
    postorder(T->left);
    postorder(T->right);
    printf("%d ", T->element);
}

// 层序遍历（BFS）
void levelorder(TreeNode *root) {
    if (root == NULL) return;
    // 使用队列
    TreeNode *queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode *curr = queue[front++];
        printf("%d ", curr->element);
        if (curr->left) queue[rear++] = curr->left;
        if (curr->right) queue[rear++] = curr->right;
    }
}

遍历的应用：

  • 中序遍历BST得到有序序列
  • 后序遍历用于计算目录大小、释放内存
  • 前序遍历用于复制树、序列化

4.3 二叉搜索树（BST）

二叉搜索树满足以下性质：对于每个节点 X，左子树中所有节点的值小于 X 的值，右子树中所有节点的值大于 X 的值。

c
// 查找 - O(h)，h为树高
TreeNode *find(TreeNode *T, int x) {
    if (T == NULL) return NULL;
    if (x < T->element) return find(T->left, x);
    else if (x > T->element) return find(T->right, x);
    else return T;
}

// 查找最小值
TreeNode *findMin(TreeNode *T) {
    if (T == NULL) return NULL;
    while (T->left != NULL)
        T = T->left;
    return T;
}

// 插入 - O(h)
TreeNode *insert(TreeNode *T, int x) {
    if (T == NULL) {
        T = createNode(x);
    } else if (x < T->element) {
        T->left = insert(T->left, x);
    } else if (x > T->element) {
        T->right = insert(T->right, x);
    }
    return T;
}

// 删除 - O(h)
TreeNode *delete(TreeNode *T, int x) {
    if (T == NULL) return NULL;
    if (x < T->element)
        T->left = delete(T->left, x);
    else if (x > T->element)
        T->right = delete(T->right, x);
    else {
        // 找到要删除的节点
        if (T->left == NULL && T->right == NULL) {
            free(T);
            return NULL;
        } else if (T->left == NULL) {
            TreeNode *tmp = T->right;
            free(T);
            return tmp;
        } else if (T->right == NULL) {
            TreeNode *tmp = T->left;
            free(T);
            return tmp;
        } else {
            // 有两个子节点：用右子树的最小值替代
            TreeNode *minNode = findMin(T->right);
            T->element = minNode->element;
            T->right = delete(T->right, minNode->element);
        }
    }
    return T;
}

BST的复杂度分析：

  • 平均情况：O(log n)（树近似平衡时）
  • 最坏情况：O(n)（树退化为链表时，如按序插入）

4.4 AVL树

AVL树是最早的自平衡二叉搜索树。它要求每个节点的左右子树高度差不超过1。通过旋转操作维护平衡，保证树高始终为 O(log n)。

c
int height(TreeNode *T) {
    if (T == NULL) return -1;
    int lh = height(T->left);
    int rh = height(T->right);
    return (lh > rh ? lh : rh) + 1;
}

#define BF(T) (height(T->left) - height(T->right))

// 右旋（LL型）
TreeNode *rotateRight(TreeNode *k2) {
    TreeNode *k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    return k1;
}

// 左旋（RR型）
TreeNode *rotateLeft(TreeNode *k1) {
    TreeNode *k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    return k2;
}

// 平衡插入
TreeNode *avlInsert(TreeNode *T, int x) {
    if (T == NULL) return createNode(x);
    if (x < T->element)
        T->left = avlInsert(T->left, x);
    else if (x > T->element)
        T->right = avlInsert(T->right, x);
    else
        return T;
    
    int balance = BF(T);
    
    // LL型
    if (balance > 1 && x < T->left->element)
        return rotateRight(T);
    // RR型
    if (balance < -1 && x > T->right->element)
        return rotateLeft(T);
    // LR型
    if (balance > 1 && x > T->left->element) {
        T->left = rotateLeft(T->left);
        return rotateRight(T);
    }
    // RL型
    if (balance < -1 && x < T->right->element) {
        T->right = rotateRight(T->right);
        return rotateLeft(T);
    }
    return T;
}

AVL树的性质：

  • 树高不超过 1.44·log(n+2)
  • 查找、插入、删除均为 O(log n)
  • 插入最多需要1次旋转，删除可能需要 O(log n) 次旋转

4.5 B树

B树是一种多路搜索树，专为磁盘等外存设备设计。一个 m 阶B树满足：

  • 每个节点最多有 m 个子节点
  • 除根节点外，每个节点至少有 ⌈m/2⌉ 个子节点
  • 所有叶节点在同一层
c
#define ORDER 4

typedef struct BTreeNode {
    int keys[ORDER - 1];
    struct BTreeNode *children[ORDER];
    int n;        // 当前关键字数
    int leaf;     // 是否为叶节点
} BTreeNode;

// B树查找
BTreeNode *btreeSearch(BTreeNode *x, int k) {
    int i = 0;
    while (i < x->n && k > x->keys[i])
        i++;
    if (i < x->n && k == x->keys[i])
        return x;
    if (x->leaf)
        return NULL;
    return btreeSearch(x->children[i], k);
}
// B树查找复杂度：O(log_m(n))，其中m为阶数
// 由于m很大（如1000），树高很小（如3-4层）
// 每次查找只需少量磁盘I/O

三、实战案例

3.1 表达式树

c
// 判断字符是否为运算符
int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// 计算表达式树的值
int evalTree(TreeNode *T) {
    if (T == NULL) return 0;
    if (T->left == NULL && T->right == NULL)
        return T->element;  // 叶节点是操作数
    
    int leftVal = evalTree(T->left);
    int rightVal = evalTree(T->right);
    
    switch (T->element) {
        case '+': return leftVal + rightVal;
        case '-': return leftVal - rightVal;
        case '*': return leftVal * rightVal;
        case '/': return rightVal != 0 ? leftVal / rightVal : 0;
    }
    return 0;
}
// 表达式树 ((3+4)*2) 的值 = 14

3.2 Huffman编码

c
typedef struct HuffNode {
    int freq;
    char ch;
    struct HuffNode *left;
    struct HuffNode *right;
} HuffNode;

// 构建Huffman树（简化版）
HuffNode *buildHuffmanTree(int freq[], char chars[], int n) {
    // 使用优先队列（最小堆）
    // 每次取出两个最小频率的节点合并
    // 重复直到只剩一个节点
    // 此处省略优先队列的实现细节
    return NULL;  // 占位
}

// 生成Huffman编码表
void generateCodes(HuffNode *root, char *code, int depth) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {
        code[depth] = '\0';
        printf("'%c': %s\n", root->ch, code);
        return;
    }
    code[depth] = '0';
    generateCodes(root->left, code, depth + 1);
    code[depth] = '1';
    generateCodes(root->right, code, depth + 1);
}
// Huffman编码是最优前缀编码
// 频率高的字符编码短，频率低的编码长
// 总编码长度最小

四、本章小结

树是表示层次关系的非线性结构。二叉树是最常用的树形结构。

二叉搜索树支持 O(log n) 的查找、插入和删除（平均情况），但可能退化为 O(n)。

AVL树通过旋转操作维护平衡，保证 O(log n) 的最坏情况性能。

B树是多路搜索树，适用于磁盘存储，通过增大节点度数减少树高和I/O次数。

树的遍历（前序、中序、后序、层序）是递归和BFS思想的经典应用。

五、思考与练习

思考题

证明：含有 n 个节点的二叉树有 n-1 条边。

给定前序遍历为 [1,2,4,5,3,6]，中序遍历为 [4,2,5,1,6,3]，画出这棵二叉树。

为什么B树比二叉搜索树更适合数据库索引？

编程练习

实现二叉树的非递归遍历（使用栈）。

实现AVL树的完整插入和删除操作。

用Huffman编码实现一个简单的文件压缩程序。

4/10树
0%