数据结构：树与二叉树

🌳 一，树与二叉树的定义

树是一种非线性数据结构，它通过层次化的关系组织数据，广泛应用于文件系统、数据库索引、人工智能等领域。与线性表的“一对一”关系不同，树的核心是“一对多”的层级关系。

（一）树的定义

树（Tree）是由n（n≥0）个节点组成的有限集合。当n=0时，称为空树；当n>0时，满足：

• 有且仅有一个特定的节点称为根（Root），它没有前驱节点；
• 其余节点可分为m（m≥0）个互不相交的有限集合T₁,T₂,…,Tₘ，每个集合本身又是一棵树，称为根的子树（Subtree）。

示例：一个家族树中，祖父是根节点，父亲和叔叔是祖父的子节点，而父亲的子女是其下的子树节点。树的定义具有递归性——子树也是树。

（二）树的基本术语

• 节点的度（Degree）：节点拥有的子树数量。例如，根节点若有3个子树，则度为3。
• 叶子节点（Leaf）：度为0的节点（无子女），又称终端节点。
• 分支节点：度不为0的节点，又称非终端节点（根节点除外的分支节点称为内部节点）。
• 树的度：所有节点中度的最大值。
• 层次（Level）：从根开始计数，根为第1层，根的子女为第2层，以此类推。
• 深度（Depth）：树中节点的最大层次数（从根到最远叶子的层数）。
• 有序树与无序树：若子树的顺序有意义（如左子树≠右子树），则为有序树；否则为无序树。
• 森林：m（m≥0）棵互不相交的树的集合（可理解为“去掉根的树”）。

（三）二叉树的定义

二叉树（Binary Tree）是一种特殊的树，它的每个节点最多有两棵子树，且子树有左右之分（左子树和右子树，顺序不可颠倒）。

二叉树的递归定义：

• 空树是二叉树；
• 若存在一个节点，其左子树和右子树都是二叉树，则该结构为二叉树。

特殊二叉树类型：

• 满二叉树：除叶子节点外，每个节点都有左右两棵子树，且所有叶子节点在同一层次（如深度为3的满二叉树有7个节点）。
• 完全二叉树：深度为k的二叉树，前k-1层为满二叉树，第k层的节点从左到右连续排列（缺一不可），适合顺序存储。

🌰 二，案例引入

场景1：文件系统的目录结构

电脑中的文件系统是典型的树结构：

• 根目录（如Windows的C:\）是根节点；
• 文件夹是分支节点，包含子文件夹或文件；
• 具体文件是叶子节点，没有子节点。
  通过树结构，用户可高效地层级化管理文件（如“文档→2023→报告.docx”）。

场景2：决策树模型

在AI分类任务中，决策树通过层层判断实现分类：

• 根节点是初始特征（如“天气是否晴朗”）；
• 分支节点是中间判断条件（如“温度是否高于25℃”）；
• 叶子节点是分类结果（如“适合户外活动”或“不适合”）。
  树的层次结构模拟了人类的决策逻辑。

这些案例表明，树结构擅长表达具有层级关系或决策流程的数据，其效率远高于线性表。

📋 三，树与二叉树的抽象数据类型定义

树的ADT定义

ADT Tree {
    数据：
        节点集合，根节点唯一，其余节点分属子树，存在层次关系。
    
    操作：
        1. InitTree(&T)：初始化空树T。
        2. CreateTree(&T)：按指定方式创建树T。
        3. Root(T)：返回树T的根节点。
        4. Parent(T, x)：返回节点x的父节点。
        5. Child(T, x, i)：返回节点x的第i个子节点。
        6. InsertChild(&T, x, i, c)：将子树c插入为x的第i个子树。
        7. DeleteChild(&T, x, i)：删除x的第i个子树。
        8. TraverseTree(T)：遍历树T的所有节点。
        9. DestroyTree(&T)：销毁树T。
}

二叉树的ADT定义

ADT BinaryTree {
    数据：
        节点集合，每个节点最多有左、右两棵子树，子树有序。
    
    操作：
        1. InitBiTree(&T)：初始化空二叉树T。
        2. CreateBiTree(&T)：创建二叉树T。
        3. BiRoot(T)：返回二叉树T的根节点。
        4. LeftChild(T, x)：返回节点x的左子节点。
        5. RightChild(T, x)：返回节点x的右子节点。
        6. InsertLeftChild(&T, x, c)：为x插入左子树c。
        7. InsertRightChild(&T, x, c)：为x插入右子树c。
        8. PreOrderTraverse(T)：先序遍历二叉树。
        9. InOrderTraverse(T)：中序遍历二叉树。
        10. PostOrderTraverse(T)：后序遍历二叉树。
        11. LevelOrderTraverse(T)：层序遍历二叉树。
        12. DestroyBiTree(&T)：销毁二叉树T。
}

🔑 四，二叉树的性质和存储结构

（一）二叉树的性质

性质1：在二叉树的第i层上，最多有2ⁱ⁻¹个节点（i≥1）。

• 示例：第1层最多1个节点（2⁰），第2层最多2个节点（2¹），第3层最多4个节点（2²）。

性质2：深度为k的二叉树最多有2ᵏ - 1个节点（k≥1）。

• 满二叉树是该性质的特例（如深度为3的满二叉树有2³ - 1 = 7个节点）。

性质3：对任意二叉树，若叶子节点数为n₀，度为2的节点数为n₂，则n₀ = n₂ + 1。

• 推导：总节点数n = n₀ + n₁ + n₂（n₁为度1的节点数），总边数n-1 = n₁ + 2n₂，联立得n₀ = n₂ + 1。

性质4：具有n个节点的完全二叉树的深度为⌊log₂n⌋ + 1（⌊x⌋表示向下取整）。

• 示例：n=7时，深度为⌊log₂7⌋ + 1 = 2 + 1 = 3。

性质5：对完全二叉树中编号为i的节点（从1开始）：

• 若i>1，则父节点编号为⌊i/2⌋；
• 左子节点编号为2i（若2i≤n）；
• 右子节点编号为2i+1（若2i+1≤n）。

（二）二叉树的存储结构

1. 顺序存储结构

适合完全二叉树，用数组按层序存储节点，通过性质5的公式计算父子节点位置。

• 存储表示（C语言）：

  #define MAXSIZE 100
  typedef char TElemType;
  typedef struct {
      TElemType data[MAXSIZE];  // 存储节点数据
      int length;               // 节点总数
  } SqBiTree;
  

• 优势：空间紧凑，访问父子节点高效（O(1)）；

• 劣势：非完全二叉树会浪费大量空间（需用特殊值填充空缺节点）。

2. 链式存储结构（二叉链表）

每个节点包含数据域和两个指针域（分别指向左、右子节点），适合任意二叉树。

• 存储表示（C语言）：

  typedef char TElemType;
  typedef struct BiTNode {
      TElemType data;                // 数据域
      struct BiTNode *lchild, *rchild; // 左、右子指针
  } BiTNode, *BiTree;
  

• 示例：创建一个简单二叉树节点：

  BiTree CreateNode(TElemType x) {
      BiTNode *node = (BiTNode*)malloc(sizeof(BiTNode));
      node->data = x;
      node->lchild = NULL;
      node->rchild = NULL;
      return node;
  }
  
  // 构建一棵二叉树：    A
  //                  /   \
  //                 B     C
  BiTree BuildBiTree() {
      BiTree root = CreateNode('A');
      root->lchild = CreateNode('B');
      root->rchild = CreateNode('C');
      return root;
  }
  

• 优势：空间利用率高，插入删除灵活；

• 劣势：访问父节点需遍历（可扩展为三叉链表，增加父指针域）。

🔍 五，遍历二叉树与线索二叉树

（一）遍历二叉树

遍历是按某种规则访问二叉树的所有节点，且每个节点仅访问一次。二叉树的遍历基于递归定义，核心有4种方式：

1. 先序遍历（Pre-order）

顺序：根节点 → 左子树 → 右子树（根左右）。
递归实现：

void PreOrderTraverse(BiTree T) {
    if (T == NULL) return;
    printf("%c ", T->data);       // 访问根节点
    PreOrderTraverse(T->lchild);  // 遍历左子树
    PreOrderTraverse(T->rchild);  // 遍历右子树
}

示例：对树 A(B(D,E),C(,F)) 先序遍历结果为：A B D E C F。

2. 中序遍历（In-order）

顺序：左子树 → 根节点 → 右子树（左根右）。
递归实现：

void InOrderTraverse(BiTree T) {
    if (T == NULL) return;
    InOrderTraverse(T->lchild);   // 遍历左子树
    printf("%c ", T->data);       // 访问根节点
    InOrderTraverse(T->rchild);   // 遍历右子树
}

示例：上述树的中序遍历结果为：D B E A C F。

3. 后序遍历（Post-order）

顺序：左子树 → 右子树 → 根节点（左右根）。
递归实现：

void PostOrderTraverse(BiTree T) {
    if (T == NULL) return;
    PostOrderTraverse(T->lchild); // 遍历左子树
    PostOrderTraverse(T->rchild); // 遍历右子树
    printf("%c ", T->data);       // 访问根节点
}

示例：上述树的后序遍历结果为：D E B F C A。

4. 层序遍历（Level-order）

顺序：按层次从左到右访问节点（需借助队列实现）。
算法步骤：

1. 根节点入队；
2. 队不空时，出队一个节点并访问；
3. 若该节点有左子节点，入队；
4. 若该节点有右子节点，入队；
5. 重复步骤2-4直至队空。

实现代码：

void LevelOrderTraverse(BiTree T) {
    if (T == NULL) return;
    BiTNode *queue[MAXSIZE];  // 用数组模拟队列
    int front = 0, rear = 0;
    queue[rear++] = T;        // 根节点入队
    while (front != rear) {
        BiTNode *p = queue[front++];  // 出队
        printf("%c ", p->data);       // 访问节点
        if (p->lchild) queue[rear++] = p->lchild;  // 左子节点入队
        if (p->rchild) queue[rear++] = p->rchild;  // 右子节点入队
    }
}

示例：上述树的层序遍历结果为：A B C D E F。

（二）线索二叉树

二叉链表中存在大量空指针（n个节点有n+1个空指针），线索二叉树利用这些空指针存储遍历序列中的前驱/后继信息，提高遍历效率。

• 线索：将空的左指针改为指向遍历前驱，空的右指针改为指向遍历后继，称为线索。
• 线索二叉树结构：在二叉链表基础上增加两个标志位（ltag/rtag）：
  • ltag=0：lchild指向左子树；ltag=1：lchild指向前驱；
  • rtag=0：rchild指向右子树；rtag=1：rchild指向后继。

typedef struct ThreadNode {
    TElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;  // 线索标志位
} ThreadNode, *ThreadTree;

• 优势：无需递归或栈即可实现遍历，节省空间，适合频繁遍历的场景。

🌳 六，树与森林

（一）树的存储结构

1. 双亲表示法

用数组存储节点，每个节点记录数据和父节点下标，适合查询父节点的场景。

#define MAX_TREE_SIZE 100
typedef struct {
    TElemType data;
    int parent;  // 父节点下标（-1表示无父节点）
} PTNode;

typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int r;  // 根节点下标
    int n;  // 节点总数
} PTree;

2. 孩子表示法

数组+链表结合：数组存储节点，每个节点通过链表指向所有子节点，适合查询子节点的场景。

3. 孩子兄弟表示法（二叉树表示法）

每个节点包含数据、第一个孩子指针和右兄弟指针，可将树转换为二叉树（左孩子右兄弟）。

typedef struct CSNode {
    TElemType data;
    struct CSNode *firstchild, *nextsibling;  // 第一个孩子、右兄弟
} CSNode, *CSTree;

（二）森林与二叉树的转换

森林与二叉树可相互转换，核心规则：

• 树→二叉树：根节点的左子树为第一个孩子，右子树为兄弟节点；
• 森林→二叉树：第一棵树转换为二叉树，其余树的根节点作为前一棵树的右子树依次连接；
• 二叉树→森林：根节点的左子树为第一棵树，右子树递归转换为其余森林。

（三）树和森林的遍历

• 树的遍历：
  • 先根遍历：先访问根节点，再依次先根遍历各子树；
  • 后根遍历：先依次后根遍历各子树，再访问根节点。
• 森林的遍历：
  • 先序遍历：先序遍历第一棵树，再先序遍历其余森林；
  • 中序遍历：中序遍历第一棵树，再中序遍历其余森林。

📊 七，哈夫曼树及其应用

（一）哈夫曼树的基本概念

哈夫曼树（Huffman Tree）又称最优二叉树，是一类带权路径长度（WPL）最小的二叉树。

• 关键术语：
  • 路径：从一个节点到另一个节点的分支序列（如根节点到叶子节点的路径）；
  • 路径长度：路径上的分支数（根到第k层节点的路径长度为k-1）；
  • 节点的权：赋予节点的数值（如字符出现的频率）；
  • 带权路径长度（WPL）：树中所有叶子节点的权值与路径长度的乘积之和，公式为：
    WPL = Σ(ωᵢ × lᵢ)（ωᵢ为第i个叶子节点的权值，lᵢ为其路径长度）。

示例：
假设有4个叶子节点，权值分别为3、4、5、6，两种二叉树结构的WPL计算如下：

• 结构1（不平衡）：WPL = 3×3 + 4×3 + 5×2 + 6×1 = 9 + 12 + 10 + 6 = 37；
• 结构2（哈夫曼树）：WPL = 3×2 + 4×2 + 5×2 + 6×2 = 6 + 8 + 10 + 12 = 36。
  显然结构2的WPL更小，为最优结构。

（二）哈夫曼树的构造算法

哈夫曼树的构造遵循贪心策略，核心是通过反复合并权值最小的子树，最终形成最优树。

算法步骤

1. 初始化：将所有权值节点视为独立的单节点树（只有根节点，无左右子树），组成森林F；
2. 合并子树：从F中选择两棵权值最小的树T₁和T₂，创建新节点作为它们的父节点，新节点的权值为T₁和T₂的权值之和；
3. 更新森林：将T₁和T₂从F中移除，将新树加入F；
4. 重复步骤2-3：直到F中只剩下一棵树，该树即为哈夫曼树。

示例（权值3、4、5、6）

• 第1次合并：选择3和4，新节点权值7，森林变为{5,6,7}；
• 第2次合并：选择5和6，新节点权值11，森林变为{7,11}；
• 第3次合并：选择7和11，新节点权值18，森林只剩{18}，构造完成。

代码实现（基于最小堆）

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int weight;          // 节点权值
    int parent, lchild, rchild; // 父节点、左/右子节点下标
} HTNode, *HuffmanTree;

// 构建哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT, int n) {
    if (n <= 1) return;
    int m = 2 * n - 1;   // 哈夫曼树总节点数
    HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); // 下标从1开始
    for (int i = 1; i <= m; i++) { // 初始化
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    for (int i = 1; i <= n; i++) { // 输入叶子节点权值
        scanf("%d", &HT[i].weight);
    }
    // 合并子树
    for (int i = n + 1; i <= m; i++) {
        // 选择两个权值最小的无父节点的节点
        int s1, s2;
        // 找到第一个最小节点s1
        for (int j = 1; j < i; j++) {
            if (HT[j].parent == 0) {
                s1 = j;
                break;
            }
        }
        for (int j = 1; j < i; j++) {
            if (HT[j].parent == 0 && HT[j].weight < HT[s1].weight) {
                s1 = j;
            }
        }
        // 找到第二个最小节点s2（s2≠s1）
        for (int j = 1; j < i; j++) {
            if (HT[j].parent == 0 && j != s1) {
                s2 = j;
                break;
            }
        }
        for (int j = 1; j < i; j++) {
            if (HT[j].parent == 0 && j != s1 && HT[j].weight < HT[s2].weight) {
                s2 = j;
            }
        }
        // 合并s1和s2
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

（三）哈夫曼编码

哈夫曼编码是哈夫曼树的典型应用，用于数据压缩，通过变长编码实现无损压缩（频率高的字符用短编码）。

编码规则

• 从哈夫曼树的根节点出发，左分支标记为“0”，右分支标记为“1”；
• 每个叶子节点（对应字符）的编码为从根到该节点的路径上的标记序列。

示例（字符A(3)、B(4)、C(5)、D(6)）

• A的路径：根→7→3（左→左），编码为“00”；
• B的路径：根→7→4（左→右），编码为“01”；
• C的路径：根→11→5（右→左），编码为“10”；
• D的路径：根→11→6（右→右），编码为“11”。

优势

• 编码唯一：哈夫曼树中叶子节点的编码互不前缀（前缀编码特性），避免解码歧义；
• 压缩高效：频率高的字符编码短，总编码长度最短。

解码过程

根据哈夫曼树，从根节点开始，按编码序列遍历：遇到“0”走左子树，遇到“1”走右子树，到达叶子节点即完成一个字符的解码，重复直至所有编码解析完毕。

🛠️ 八，案例分析与实现

案例：哈夫曼编码压缩系统

功能：对输入的文本进行哈夫曼编码压缩，并能通过编码和解码表还原文本。

实现步骤

1. 统计文本中每个字符的出现频率（权值）；
2. 用频率构建哈夫曼树；
3. 生成每个字符的哈夫曼编码；
4. 用编码表将文本转换为二进制压缩串；
5. 保存编码表和解码表，用于解压还原。

核心代码

#include <string.h>

// 生成哈夫曼编码
void CreateHuffmanCode(HuffmanTree HT, char **&HC, int n) {
    HC = (char**)malloc((n + 1) * sizeof(char*)); // 存储每个字符的编码
    char *cd = (char*)malloc(n * sizeof(char));   // 临时存储编码
    cd[n - 1] = '\0';  // 编码结束符
    for (int i = 1; i <= n; i++) {
        int start = n - 1;  // 编码从后往前存储
        int c = i;
        int f = HT[i].parent;
        while (f != 0) { // 从叶子节点回溯到根
            start--;
            if (HT[f].lchild == c) {
                cd[start] = '0'; // 左子树为0
            } else {
                cd[start] = '1'; // 右子树为1
            }
            c = f;
            f = HT[f].parent;
        }
        HC[i] = (char*)malloc((n - start) * sizeof(char)); // 分配编码空间
        strcpy(HC[i], &cd[start]); // 复制编码
    }
    free(cd);
}

// 示例：压缩文本"ABACCD"
int main() {
    int n = 4; // 字符数：A、B、C、D
    HuffmanTree HT;
    CreateHuffmanTree(HT, n); // 构建哈夫曼树（权值3,4,5,6对应A,B,C,D）
    
    char **HC;
    CreateHuffmanCode(HT, HC, n); // 生成编码
    
    // 输出编码表
    printf("哈夫曼编码表：\n");
    printf("A: %s\n", HC[1]); // A: 00
    printf("B: %s\n", HC[2]); // B: 01
    printf("C: %s\n", HC[3]); // C: 10
    printf("D: %s\n", HC[4]); // D: 11
    
    // 压缩文本"ABACCD"
    char text[] = "ABACCD";
    printf("原文本：%s\n", text);
    printf("压缩编码：");
    for (int i = 0; i < strlen(text); i++) {
        switch (text[i]) {
            case 'A': printf("%s", HC[1]); break;
            case 'B': printf("%s", HC[2]); break;
            case 'C': printf("%s", HC[3]); break;
            case 'D': printf("%s", HC[4]); break;
        }
    }
    // 输出：压缩编码：000100101011
    
    // 释放内存
    free(HT);
    for (int i = 1; i <= n; i++) free(HC[i]);
    free(HC);
    return 0;
}

效果分析

原文本“ABACCD”共6个字符，若用ASCII编码需6×8=48位；
哈夫曼编码后为“000100101011”，共12位，压缩率达75%，体现了哈夫曼编码的高效性。

📝 章结

树与二叉树作为非线性数据结构的核心，以层次化关系突破了线性表的“一对一”限制，为表达复杂数据关系提供了强大工具：

• 树与二叉树的本质：树通过“一对多”的层级关系建模现实中的层级结构（如文件系统），而二叉树通过限制子树数量（最多两棵）简化了操作实现，成为树结构的研究重点。二叉树的性质（如节点数与深度的关系）为存储和遍历提供了理论基础，链式存储（二叉链表）则是实现二叉树的主流方式。

• 遍历的核心价值：先序、中序、后序遍历通过递归思想实现对二叉树的完整访问，层序遍历借助队列实现层次化访问，不同遍历方式适用于不同场景（如中序遍历可用于二叉搜索树的有序输出）。线索二叉树通过利用空指针存储前驱/后继信息，优化了遍历效率。

• 树与森林的扩展：树的存储结构（双亲表示法、孩子兄弟表示法）需根据操作需求选择，而森林与二叉树的转换则架起了树与二叉树的桥梁，使得二叉树的算法可迁移到树和森林中。

• 哈夫曼树的应用：哈夫曼树通过贪心策略构造最优二叉树，其衍生的哈夫曼编码利用变长编码实现高效数据压缩，体现了数据结构与算法结合解决实际问题的典型思路。

从层级建模到高效编码，树与二叉树的思想渗透在计算机科学的各个领域。理解它们的定义、性质和算法，不仅能解决具体问题，更能培养“层次化思维”和“优化意识”——这正是非线性数据结构的核心价值所在。