【算法竞赛】二叉树和哈夫曼树

标签：编码遍历哈夫曼频次算法二叉树节点

树是非线性数据结构,它能很好地描述数据的层次关系。

树这种结构的现实场景很常见,如文件目录、书本的目录就是典型的树形结构。二叉树是最常用的树形结构,特别适合编码,常常将一般的树转换为二叉树来处理。

本节介绍二叉树的定义和存储。

哈夫曼(Huffman)树是二叉树的一个应用。

二叉树的概念

二叉树的性质

二叉树的每个节点最多有两个子节点,分别称为左孩子、右孩子,以它们为根的子树称
为左子树、右子树。

二叉树的每层节点数以2的倍数递增,所以二叉树的第i层最多有2^(i-1)个节点。如果
每层的节点数都是满的,称它为满二叉树。一个n层的满二叉树,一共有2ⁿ-1个节点。

如果满二叉树只在最后一层有缺失,并且缺失的约编号都在最后,则称为完全二叉树。

图1.3所示为一棵满二叉树和一棵完全二叉树。
在这里插入图片描述
1号节点是二叉树的根,它是唯一没有父节点的节点。

从根到节点u的路径长度定义为u的深度,节点u到它的叶子节点的最大路径长度定义为节点u的高度。根的高度最大,称为树的高。

二叉树之所以应用广泛,得益于它的形态。高级数据结构大部分与二叉树有关,下面列
举二叉树的一些优势。

在二叉树上能进行极高效率的访问。
一棵平衡的二叉树,如满二叉树或完全二叉树,每层的节点数量约为上一层数量的2倍。也就是说,一棵有N个节点的满二叉树,树的高度为O(log₂N)。从根节点到叶子节点,只需要走log₂N步,就能到达树中的任意节点.

例如,N=100万,树的高度仅为log2N=20,只需要20步就能到达这100万个节点中的任
意一个。但是,如果二叉树不是满的,而且很不平衡,甚至在极端情况下退化为一条"链",访
问效率会打折扣。维护二叉树的平衡是高级数据结构的主要任务之一.

二叉树很适合做从整体到局部、从局部到整体的操作。
二叉树内的一棵子树可以看作整棵树的一个子区间,求区间最值、区间和、区间翻转、区间合并、区间分裂等,用二叉树都很快捷。例如,文本编辑器用二叉树实现效率很高。
基于二叉树的算法容易设计和实现。
例如,二叉树用宽长度优先搜索(Breadth-FirstSearch,BFS)和深度优先搜索(Depth-First Search,DFS)处理都极为简便。二叉树可以一层一层地搜索,这是BFS。
二叉树的任意一个子节点,是以它为根的一棵二叉树,这是一种递归结构,用DFS访问二叉树极容易编码。BFS和DFS是二叉树的绝配。

二叉树的存储结构

二叉树的一个节点的存储,包括节点的值、左右子节点,有动态和静态两种存储方法

动态二叉树
数据结构中一般这样定义二叉树:

struct Node
{
	//节点的值,可以定义多个值
	
	int value;
	
	//指向左右子节点
	node * lson, * rson;
};

动态新建一个Node时,用new运算符动态申请一个节点。使用完毕后,应该用delete命令释放它,否则会内存泄漏。
动态二叉树的优点是不浪费空间,缺点是需要管理,不小心会出错。

用静态数组存储二叉树。
在算法竞赛中,为了编码简单,加快速度,一般用静态数组实现二叉树。
下面定义一个大小为N的结构体数组。

//静态二叉树
struct Node
{
	
	char value;
	
	//左右孩子,竞赛时把lson、rson简写为1、r
	int Ison, rson;
}tree[N];
//可以把tree简写为t

在这里插入图片描述
图1.4所示为一棵二叉树的静态存储,根是tree[5]。
编码时一般不用tree[0],因为0被用来表示空节点,如叶子节点tree[2]没有子节点,就把它的子节点赋值为Z=r=0。

特别地,用数组实现完全二叉树,访问非常便捷,此时连lson、rson都不需要定义。一棵节点总数量为k的完全二叉树,设1号节点为根节点,有以下性质:

编号i>1的节点,其父节点编号是i/2;
如果2i>k,那么节点i没有左孩子;如果2i+1>k,那么节点i没有右孩子;
如果节点i有孩子,那么它的左孩子是节点2i,右孩子是节点2i+1。

多叉树转换成二叉树

多叉树有B一树、B+树等。
把多叉树转化为二叉树的应用场景不多见,简单方法是将第1个孩子作为左孩子,将其兄弟节点作为右孩子。这样做做的缺点是可能导致树退化为一条长链,如图1.5所示。
在这里插入图片描述

二叉树的遍历

宽度优先遍历

有时需要按层次一层层从上到下遍历二叉树。例如,在图1.6中,需要按E-BG-ADFI-CH的顺序访问,此时用宽度优先搜索(BFS)是最合适的。
在这里插入图片描述

深度优先遍历

用深度优先搜索(DFS)遍历二叉树,代码很简单,而且产生了很多应用。

按深度搜索的顺序访问二叉树,对父节点、左孩子、右孩子进行组合,有先(父)序遍历、中(父)序遍历、后(父)序遍历这3种访问顺序,这里默认左孩子在右孩子前面。

先序遍历（按父节点、左孩子、右孩子的顺序访问）

在图1.6中,先序遍历输出的顺序是EBADCGFIH,先序遍历的第1个节点是根。先序遍历的伪代码如下：
在这里插入图片描述

中序遍历（按左孩子、父节点、右孩子的顺序访问）

在图1.6中,中序遍历输出的顺序是ABCDEFGHI。

读者可能注意到,ABCDEFGHI刚好是字典序,这不是巧合,是因为图示的是一个二叉搜索树。在二叉搜索树中,中序遍历实现了排序功能,返回的结果是一个有序排列。

中序遍历还有一个特征:如果已知根节点,那么在中序遍历的结果中,排在根节
点左边的点都在左子树上,右边的点都在右子树上。例如,E是根,E左边的ABCD在它的左子树上;再如,在子树ABCD上,B是子树的根,那么A在它它的左子树上,CD在它的右子树上。任意子树都符合这个特征。

中序遍历的伪代码如下：
在这里插入图片描述
3. 后序遍历,按左孩子、右孩子、父节点的顺序访问。
在图图1.6中,后序遍历输出的顺序是ACDBFHIGE。后序遍历的最后一个节点是根。
后序遍历的伪代码如下：

如果已知某棵二叉树的中序遍历和另一种遍历,可以报这棵树构造出来,即"中序遍历+先序遍历"或"中序遍历+后序遍历",都能确定一棵树。

但是,如果不知道中序遍历,只有先序遍历+后序遍历,则不能确定一棵二叉树。例如,图1.7所示的两棵不同的二叉树,它们的先序遍历都是"123",后序遍历都是"321"。

在这里插入图片描述

哈夫曼树与哈夫曼编码

哈夫曼树是一类带权路径长度最短的最优树,是贪心思想在二叉树上的应用。哈夫曼树的一个经典应用是哈夫曼编码。

二叉树上两个节点之间的路径长度是指这条路径经过的边的数量。

树的路径长度是从根到每个节点的路径长度之和。

显然,二叉树越平衡,从根到其他节点的路径越短,树的路径长度也越短。完全二叉树的路径长度是最短的。

把上述概念推广到带权节点。从根到一个带权节点的带权路径长度,是从根到该节点的路径长度与节点权值的乘积。树的带权路径长度是所有叶子节点的带权路径长度之和。

因为节点有权值,所以一棵平衡的二叉树并不一定有最小的带权路径长度。
给定几个权值,构造一棵有几个叶子节点的二叉树,每个叶子节点对应一个权值。有很多种构造方法,把其中带权路径长度最小的二叉树称为哈夫曼树,或者最优二叉树。

如何构造一棵哈夫曼树?容易想到一种贪心方法:把权值大的节点放在离根节点近的层次上,权值小的节点放在离根节点远的层次上。

哈夫曼算法步骤如下：

1.把每个权值构造成一棵只有一个节点的树,n个权值构成了n棵树,记为集合F={T₁,T₂,……,T_n}。

2.在F中选择权值最小的两棵树T_i和T_j,合并为一棵新的二叉树T_x,它的权值等于T_i与T_j的权值之和,左右子树分别为T_i和T_j。

3.在F中删除T_i和T_j,并把T_x加入F。

4.重复步骤(2)和步骤(3),直到F中只含有一棵树,这棵树就是哈夫曼树。
下面以哈夫曼编码为例介绍算法的执行步骤。

哈夫曼编码

哈夫曼树的一个经典应用是哈夫曼编码,这是一种"前缀"最优编码。
什么是编码?给定一段字符串,这段字符串包含很多字符。,每种字符出现次数不一样,有的频次高,有的频次低。现在把这段字符串存储在计算机中,因为数据在计算机中都是用二进制码表示的,所以需要把每个字符编码成一个二进制数。
最简单的编码方法是把每个字符都用相同长度的二进制数表示。例如,给出一段字符串,它只包含A、B、C、D、E这5种字符,编码方案如下。
在这里插入图片描述
这种编码方法简单实用,但是不节省空间。
由于每个字符出现频次不同,可以想到用变长编码:出现次数多的字符用短码表示,出现少的用长码表示。编码方案如下：

第2种方法相当于对第1种方法进行了压缩,压缩比为156/112~1.39

编码方法的基本要求：编码后得到的二进制串能唯一地进行行解码还原。
上面第1种简单方法显然是正确的,每3位二进制数对应一个字符。第2种方法也是正确的,如11001111001101,解码后唯一得到 ABDEC。

如果胡乱设定编码方案,很可能是错误的,例如下面的编码方案:
在这里插入图片描述
上述编码方案看起来似乎每个字符都有不同的编码,编码后的总长度也更短,只有3×3+9×2+6×2+15×1+19×1=73,但是编码无法解码还原。
例如,编码100,是解码为A、BE还是DEE呢?

错误的原因是某个编码是另一个编码的前缀(Prefix),即这两个编码有包含关系,导致了混淆。

有没有比第2种编码方法更好的方法?

这引出了一个常见问题:给定一个字符串,如何编码能使编码后的总长度最小?即如何得到一个最优解?

哈夫曼编码是前缀编码的一种最优算法。
如何设计编码方法?由于编码是二进制,容易想到用二叉树构造编码。例如,上面第2种编码方案的二叉树实现如图1.8所示。
在这里插入图片描述

在二叉树的每个分支,左边是0,右边是1。二叉树末端的叶子节点就是编码。把编码放在叶子节点上,可以保证符合"前缀不包含"的要求。

出现频次最高的字符E在最靠近根节点的位置,编码最短;出现频次最低的A在二叉树最深处,编码最长。

这棵编码二叉树是如何构造的?下面用哈夫曼树构造哈夫曼编码
首先对所有字符按出现频次排序,如下所示。
在这里插入图片描述
然后,从出现频次最低的字符开始,利用贪心思想安排在二叉树上。按哈夫曼算法执行如图1.9所示的步骤。

每个节点圆圈内的数字是这个子树下字符出现的频次之和。
贪心的过程是按出现频次从底层向顶层生成二叉树。贪心过程保证了出现频次低的字符被放在树的底层,编码更长;出现频次高的字符被放在顶层,编码更短。可以证明,哈夫曼算法符合贪心法的"最优子结构性质"和"贪心选择性质"，编码的结果是最优的。

下面给出一道例题：
在这里插入图片描述
本题正常的解题过程是首先统计字符出现的频次,然后用哈夫曼算法编码,最后计算编码后的总长度。
不过,由于只需要输出编码总长度,而不要求输出每个字符的编码,所以可以跳过编码过程,利用图1.9所描述的哈夫曼编码思想(圆圈内的数字为出现频次)直接计算编码的总长度。
下面的代码使用了STL的优先队列,在每个贪心步骤,从优先队列中取出最少的两个频次。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main(){
    priority_queue<int, vector<int>, greater<int>>q;
    string s;
    while(getline(cin, s) && s!= "END"){
        sort(s.begin(), s.end());
        int num = 1;
        for(int i = 1; i <= s.length(); i++){
            if(s[i]!=s[i - 1]){
                q.push(num);
                num = 1;
            }
            else{
                num++;
            }
        }
        int ans = s.length();
        if (q.size()==1){
            while(q.size()>1){
                int a = q.top();
                q.pop();
                int b = q.top();
                q.pop();
                ans += a + b;
                q.push(a + b);
            }
        }
        q.pop();
        printf("%d %d %.1f\n", s.length() * 8, ans, (double)s.length() * 8 / (double)ans);
    }
    return 0;
}

标签：编码,遍历,哈夫曼,频次,算法,二叉树,节点
From： https://blog.csdn.net/Sakura_ding/article/details/142415150