09.二叉树与哈夫曼编码

发表于 更新于 分类于 ，

二叉树与哈夫曼编码

二叉树作为一种基础的数据结构，其独特的递归定义和多样化的类型，如满二叉树、完全二叉树等，为解决诸如查找、排序及编码等问题提供了强大的支持，而哈夫曼编码通过构建最优二叉树实现了数据的高效压缩。

树

递归式定义：一个根节点带0到多个子节点，每个子节点可以是一棵子树的根，子树也符合树的定义。

名词表：

  • 根：没有前驱

  • 叶：没有后继

  • 森林：多棵不相交的树

  • 有序树：子树从左到右有序

  • 无序树：一个根的不同子树可互换位置

  • 父节点：直接前驱

  • 子节点：直接后继

  • 兄弟节点：同一个父节点的子节点

  • 堂兄弟：两个节点的父节点不同且位于同一层

  • 祖先：该节点到根节点路径上的所有节点

  • 子孙：该节点子树中的任意节点

  • 节点的度：一个节点的子节点数量

  • 节点的层次：根节点到该节点的层数

  • 终端节点：度为0的节点，即叶子

  • 分支节点：度不为0的节点

  • 树的度：所有节点的度的最大值

  • 树的深度：最大的层数

  • 满二叉树：每层都充满了，1层有1个点，2层有3个点，3层有7个点，找找规律~

  • 完全二叉树：除了最后面一层外全满，最后一层的点也聚集在“左边”，确定点的个数就完全可以确定完全二叉树的形态

  • 满二叉树与完全二叉树特性：如果从 1 开始一行一行地编号，对编号 \(i\) 的节点，父节点编号 \(i/2\) ，左子节点 \(i*2\) ，右子节点 \(i*2+1\)

二叉树

  • 所有节点度不大于2的树
  • 有序树，即子树有左右之分

也即二叉树是度为2的有序树的专有名词。

度为 2 的树，普通树与二叉树的典型区别：

  • 3个节点的二叉树有 5 种形态
  • 3个节点的度为 2 的普通树有 2 种形态

自行尝试画出它们

遍历二叉树

访问顺序： 先序 D L R、中序 L D R、后序 L R D

上图二叉树的三个访问顺序的输出结果是

  • 先序遍历：A B D E C 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void Pre(int now) {
        // 对数据做一个预定义的任务
        // 就是访问了这个数据
        // 比如printf("%d\n", data);
        DoSomething(tr[now].data);
        // 访问左子树
        if(tr[now].left != fakeNull)
        Pre(tr[now].left);
        // 访问右子树
        if(tr[now].right != fakeNull)
        Pre(tr[now].right);
    }
  • 中序遍历：D B E A C 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void In(int now) {
        // 访问左子树
        if(tr[now].left != fakeNull)
        In(tr[now].left);
        // 访问当前节点数据
        DoSomething(tr[now].data);
        // 访问右子树
        if(tr[now].right != fakeNull)
        In(tr[now].right);
    }
  • 后序遍历：D E B C A 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void Post(int now) {
        // 访问左子树
        if(tr[now].left != fakeNull)
        Post(tr[now].left);
        // 访问右子树
        if(tr[now].right != fakeNull)
        Post(tr[now].right);
        // 访问当前节点数据
        DoSomething(tr[now].data);
    }

例：知道中序和后序遍历，还原二叉树结构

已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树

  1. 由后序遍历特征，根节点必在后序序列尾部（A）由
  2. 中序遍历特征，根节点必在其中间，而且其左部必全部是左子树子孙（BDCE），其右部必全部是右子树子孙（FHG）
  3. 根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推，从而可以递归完成建树。

二叉搜索树

如果递归式定义并构建一个左子树所有节点值都比根节点值小，所有右子树节点值都比根大，就可以很快地做一些查找工作，比二分查找的优势在于，二叉树可以不断地动态添加数据，并在查找时保持二分查找的效率。

哈夫曼树与编码

当有树上的一系列查找工作，经过树上路径的总次数受数据比例和树的结构影响，如何在知道结点访问比例的情况下，优化树的结构？

哈夫曼树是一种根据字符出现频率构建的二叉树，出现频率高的字符编码短（靠近树根），频率低的编码长（远离树根），通过这种最短前缀编码方式实现数据的高效压缩。

初始化：每个结点作为独立的树（只有根结点的树）

  1. 取出权重最小的两棵树
  2. 新建一个根节点，左右子树分别为这两棵树，根节点权重为两棵树权重和
  3. 把新建的树放回
  4. 重复1~3，直到成为一棵树

tip ：如何找权重最小的两棵树？规模小就暴力找，规模大可以用堆或者priority_queue

1
2
3
4
5
6
7
8
9
10
11
12
while(q.size() > 1)
{
    Node ln = q.top(); q.pop(); // q是priority_queue
    Node rn = q.top(); q.pop();
    tr[tp].Init();
    tr[tp].data = ln.data + rn.data;
    tr[tp].address = tp;
    tr[tp].l = ln.address;
    tr[tp].r = rn.address;
    tr[ln.address].parent = tr[rn.address].parent = tp;
    q.push(tr[tp ++]);
}

在远程通讯中，要将待传字符转换成二进制的字符串，怎样编码才能使它们组成的报文在网络中传得最快？

例：对ABACCDA编码，等长编码假设如下

1
2
3
4
A    00
B    01
C    10
D    11

编码结果是000110010101100

如果不等长编码

1
2
3
4
A    0
B    00
C    1
D    01

就可以是 000011010

但是这样有问题，遇到00的时候，是一个B还是两个A呢？所以在设计不等长的编码时，需要让任一字符的编码都不是另一个字符的编码的前缀，这就是”前缀编码”，利用二叉树设计的哈夫曼编码就是最优前缀码。

编解码方式参考：

  1. 以字符出现频率为权值，构建赫夫曼树
  2. 编码：从字符对应的叶结点出发走到根结点，结点需保存parent信息 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int Encoding(char st[], char res[]){
        int resLen = 0;
        for(int i = strlen(st) - 1; i >= 0; i --){
            // iLetter 为要编码的字符对应的结点编号
            int iLetter = GetCharNode(st[i]);
            for(int j = iLetter; tr[j].parent != -1; j = tr[j].parent)
            res[resLen ++] = (j == tr[tr[j].parent].nex[1]) + '0';
        }
        // 从叶结点“上”去得到的编码是逆序的
        // 所以反向扫明文，得到结果再整体翻转一下
        std::reverse(res, res + resLen);
        res[resLen] = '\0';
        return resLen;
    }
  3. 解码：从根节点出发通过编码找到叶子结点 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void Decoding(char code[], char res[]){
        int resLen = 0;
        for(int i = 0, j = tp - 1; code[i]; i ++) {
            // nex[0] 表示 left，nex[1] 表示 right
            if(tr[j].nex[code[i] - '0'] == -1) break;
            j = tr[j].nex[code[i] - '0'];
            if(tr[j].nex[0] == -1 && tr[j].nex[1] == -1) {
                // 左右指针都空（-1），到了叶节点
                res[resLen ++] = val[tr[j].ith];
                j = tp - 1; // 回到根节点解码紧贴着的下一个字符
            }
        }
    }