二十三、树(二)：线索二叉树、哈夫曼树与哈夫曼编码、平衡二叉树(AVL树)

树这个结构，咱们上一章聊了基础概念和遍历。今天要讲的这三个东西，说实话，是树结构里最“实用”的三个变种。我在实际项目中，几乎每个项目都跟它们打过照面。

先看一张总览图，帮你快速建立本章的知识框架：

23.1 线索二叉树：让遍历不再递归

先问一个问题：二叉树有那么多空指针，你心疼不心疼？

一个 n 个节点的二叉树，总共有 2n 个指针域。其中真正用到的只有 n-1 个（根节点没有父节点指向它）。也就是说，有 n+1 个指针域是空的！

我当年第一次算这个数的时候，觉得太浪费了。能不能利用这些空指针，让遍历更快一点？

这就是线索二叉树的核心思想——把空指针利用起来，指向遍历序列中的前驱和后继。

23.1.1 线索化的本质

说白了，就是在每个节点里加两个标志位：ltag 和 rtag。

• ltag = 0：lchild 指向左孩子
• ltag = 1：lchild 指向前驱节点
• rtag = 0：rchild 指向右孩子
• rtag = 1：rchild 指向后继节点

嗯，这里要注意：线索化是在遍历过程中完成的。你用什么顺序遍历，就得到什么顺序的线索二叉树。中序线索二叉树最常用，我个人也最推荐。

23.1.2 中序线索化的代码实现

// 线索二叉树节点结构
typedef struct ThreadNode {
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;  // 0表示孩子，1表示线索
} ThreadNode, *ThreadTree;

// 全局变量，指向当前访问节点的前驱
ThreadNode *pre = NULL;

// 中序线索化
void InThread(ThreadTree p) {
    if (p != NULL) {
        InThread(p->lchild);  // 线索化左子树
        
        // 处理当前节点
        if (p->lchild == NULL) {
            p->lchild = pre;   // 左指针指向前驱
            p->ltag = 1;
        }
        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild = p;   // 前驱的右指针指向当前节点
            pre->rtag = 1;
        }
        pre = p;               // 更新前驱
        
        InThread(p->rchild);  // 线索化右子树
    }
}

// 创建中序线索二叉树
void CreateInThread(ThreadTree T) {
    pre = NULL;
    if (T != NULL) {
        InThread(T);
        // 处理最后一个节点
        if (pre->rchild == NULL) {
            pre->rtag = 1;
        }
    }
}

23.1.3 线索二叉树的遍历

有了线索，遍历就简单了。不需要递归，不需要栈，直接沿着线索走就行。

// 找到中序序列的第一个节点
ThreadNode *FirstNode(ThreadNode *p) {
    while (p->ltag == 0) {
        p = p->lchild;
    }
    return p;
}

// 找到中序序列中p的后继节点
ThreadNode *NextNode(ThreadNode *p) {
    if (p->rtag == 1) {
        return p->rchild;  // 直接通过线索找到后继
    } else {
        return FirstNode(p->rchild);  // 右子树的最左节点
    }
}

// 中序遍历线索二叉树（非递归）
void InOrder(ThreadNode *T) {
    for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)) {
        printf("%d ", p->data);
    }
}

你看，一个 for 循环就搞定了遍历。简洁、高效、没有递归开销。

23.2 哈夫曼树与哈夫曼编码：数据压缩的基石

说到哈夫曼树，我就想起当年做文件压缩项目的经历。那时候刚学完这个知识点，觉得太神奇了——用一棵树就能把文件体积压缩一半。

23.2.1 什么是哈夫曼树

哈夫曼树，也叫最优二叉树。它的特点是：带权路径长度（WPL）最小。

什么叫带权路径长度？每个叶子节点都有个权值，从根到叶子的路径长度乘以权值，加起来就是 WPL。

举个例子：

假设有4个字符：A(7), B(5), C(2), D(4)
括号里是出现频率（权值）

普通二叉树可能长这样：
        root
       /    \
      A      B
     / \    / \
    C   D  ... ...

WPL = 7*2 + 5*2 + 2*3 + 4*3 = 14 + 10 + 6 + 12 = 42

哈夫曼树：
        root
       /    \
      18     ?
     /  \
    7   11
       /  \
      5    6
          / \
         2   4

WPL = 7*2 + 5*3 + 2*4 + 4*4 = 14 + 15 + 8 + 16 = 53
等等，这个不是最优的，让我重新构建...

其实构建哈夫曼树有固定算法，咱们直接看步骤。

23.2.2 哈夫曼树的构建算法

算法很简单，就一句话：每次从森林中选两个权值最小的树合并。

1. 把所有节点看成独立的树（森林）
2. 选两个权值最小的树，合并成一棵新树
3. 新树的权值 = 两棵子树权值之和
4. 把新树放回森林
5. 重复步骤2-4，直到只剩一棵树

这就是贪心策略——每次选最优的局部解，最终得到全局最优解。

// 哈夫曼树节点
typedef struct {
    int weight;       // 权值
    int parent, lch, rch;  // 父节点和左右孩子下标
} HTNode, *HuffmanTree;

// 构建哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT, int *w, int n) {
    if (n <= 1) return;
    
    int m = 2 * n - 1;  // 哈夫曼树共有2n-1个节点
    HT = (HTNode *)malloc((m + 1) * sizeof(HTNode));  // 0号位置不用
    
    // 初始化
    for (int i = 1; i <= m; i++) {
        HT[i].parent = 0;
        HT[i].lch = 0;
        HT[i].rch = 0;
    }
    for (int i = 1; i <= n; i++) {
        HT[i].weight = w[i - 1];
    }
    
    // 构建
    for (int i = n + 1; i <= m; i++) {
        // 选两个最小的且没有父节点的节点
        int s1, s2;
        Select(HT, i - 1, s1, s2);
        
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lch = s1;
        HT[i].rch = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

23.2.3 哈夫曼编码：前缀码的妙用

有了哈夫曼树，编码就简单了。从根到每个叶子节点的路径，左分支记0，右分支记1，就得到了每个字符的哈夫曼编码。

哈夫曼编码有个重要特性：它是前缀码。什么意思？任何一个字符的编码，都不是另一个字符编码的前缀。这样解码时就不会产生歧义。

我举个例子：

字符: A B C D
频率: 7 5 2 4

构建哈夫曼树后，假设编码为：
A: 0
B: 10
C: 110
D: 111

编码字符串 "ABAC" = 0 10 0 110 = 0100110
解码时从左到右读：
0 → A
10 → B
0 → A
110 → C

完美解码，没有歧义！

23.3 平衡二叉树(AVL树)：让查找不再退化

二叉排序树有个致命问题：如果插入的数据是有序的，它会退化成链表。查找效率从 O(log n) 变成 O(n)。

你想想看，如果数据库索引退化成链表，那查询得慢成什么样？

平衡二叉树就是为了解决这个问题而生的。

23.3.1 平衡因子的概念

AVL树规定：每个节点的左右子树高度差不超过1。

这个高度差就叫平衡因子：

平衡因子 = 左子树高度 - 右子树高度

合法值：-1, 0, 1
如果出现 -2 或 2，就需要调整

23.3.2 四种旋转操作

当插入或删除节点导致不平衡时，需要通过旋转来恢复平衡。一共四种情况：

失衡类型	场景描述	旋转方式
LL型	在左孩子的左子树插入	右单旋转
RR型	在右孩子的右子树插入	左单旋转
LR型	在左孩子的右子树插入	先左旋后右旋
RL型	在右孩子的左子树插入	先右旋后左旋

说白了，LL和RR是对称的，LR和RL是对称的。记住一个，另一个就自然记住了。

// AVL树节点
typedef struct AVLNode {
    int key;
    int height;  // 节点高度
    struct AVLNode *left, *right;
} AVLNode, *AVLTree;

// 获取节点高度
int GetHeight(AVLNode *node) {
    return node ? node->height : 0;
}

// 右旋转（处理LL型失衡）
AVLNode *RightRotate(AVLNode *y) {
    AVLNode *x = y->left;
    AVLNode *T2 = x->right;
    
    // 旋转
    x->right = y;
    y->left = T2;
    
    // 更新高度
    y->height = max(GetHeight(y->left), GetHeight(y->right)) + 1;
    x->height = max(GetHeight(x->left), GetHeight(x->right)) + 1;
    
    return x;  // 返回新的根节点
}

// 左旋转（处理RR型失衡）
AVLNode *LeftRotate(AVLNode *x) {
    AVLNode *y = x->right;
    AVLNode *T2 = y->left;
    
    y->left = x;
    x->right = T2;
    
    x->height = max(GetHeight(x->left), GetHeight(x->right)) + 1;
    y->height = max(GetHeight(y->left), GetHeight(y->right)) + 1;
    
    return y;
}

// 获取平衡因子
int GetBalance(AVLNode *node) {
    return node ? GetHeight(node->left) - GetHeight(node->right) : 0;
}

// 插入节点
AVLNode *Insert(AVLNode *node, int key) {
    // 1. 普通BST插入
    if (node == NULL) {
        AVLNode *newNode = (AVLNode *)malloc(sizeof(AVLNode));
        newNode->key = key;
        newNode->height = 1;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    
    if (key < node->key)
        node->left = Insert(node->left, key);
    else if (key > node->key)
        node->right = Insert(node->right, key);
    else
        return node;  // 不允许重复
    
    // 2. 更新高度
    node->height = max(GetHeight(node->left), GetHeight(node->right)) + 1;
    
    // 3. 检查平衡因子，进行旋转
    int balance = GetBalance(node);
    
    // LL型
    if (balance > 1 && key < node->left->key)
        return RightRotate(node);
    
    // RR型
    if (balance < -1 && key > node->right->key)
        return LeftRotate(node);
    
    // LR型
    if (balance > 1 && key > node->left->key) {
        node->left = LeftRotate(node->left);
        return RightRotate(node);
    }
    
    // RL型
    if (balance < -1 && key < node->right->key) {
        node->right = RightRotate(node->right);
        return LeftRotate(node);
    }
    
    return node;
}

23.3.3 AVL树的性能分析

AVL树保证了查找、插入、删除的时间复杂度都是 O(log n)。

但代价是什么？每次插入或删除都可能需要旋转，旋转本身也有开销。如果你的应用场景是写少读多，AVL树非常合适。如果是写多读少，可以考虑红黑树（红黑树的旋转次数更少）。