【数据结构】树和二叉树的应用（哈夫曼树和哈夫曼编码、堆和优先级队列）

文章目录

• 哈夫曼树和哈夫曼编码
• • 哈夫曼树
  • • 基本概念
    • 特点
    • 构造函数
    • 创建哈夫曼树
    • 选出paretent的值为0且权值最小的子树的根节点，并记录下标。
  • 哈夫曼编码
  • • 输出叶结点及其哈夫曼编码
• 堆和优先级队列
• • 堆
  • 优先级队列
  • • 入队
    • 向上调整堆
    • 出队（删除）
    • 向下调整堆
    • 建堆（自下而上）
    • 其他
    • • 构造空堆
      • 构造无序堆
      • 扩大堆空间
• 习题（含408）

哈夫曼树和哈夫曼编码

哈夫曼树

哈夫曼树又称为最优二叉树，是带权路径长度（WPL）最短的树

基本概念

路径：从树中的一个结点到另一个结点之间的分支构成这两点之间的路径
路径长度：路径上的分支数目
权：赋予某个实体的一个量
树的路径长度：从树根到每一个结点的路径长度之和
结点的带权路径长度：从该结点到根结点之间的路径长度与结点上权的乘积
树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和

特点

（1）有n个叶结点的哈夫曼树共有2n-1个结点。
（2）权值越大的叶结点，离根节点越近；权值越小的叶结点，离根节点越远；
（3）哈夫曼树是正则二叉树，只有度为0和度为2的结点。
（4）哈夫曼树的左右子树可互换，形状不唯一，但WPL是相同。

构造哈夫曼树：
（1）把结点从小到大排序
（2）把权值最小的两个结点，分别作为左右子树构造一颗二叉树。
（3）在排序把删除步骤二用的两个小结点，添加他们的结点之和。
（4）重复步骤二、三。

具体例子可见：哈夫曼树原理、画法和具体例子

哈夫曼树的类型定义及运算如下：

#include<iostream>
#ifndef _HUFFMAN_TREE_H_
#define _HUFFMAN_TREE_H_
using namespace std;

template <class T>
class huffmanTree{
private:
    struct  Node{  
        T data;                // 结点数据域
        int weight;              // 结点的权值      
        int parent, left, right;          // 双亲及左右孩子的下标
        Node() {                // 构造函数
            weight = parent = left = right = 0; 
        };
    };
    struct huffmanCode {      
    	T data;
    	string code;        // 保存data的哈夫曼编码
    	huffmanCode(){ code=""; }  // 构造函数
  	};
  	
    Node *hfTree;          // 顺序结构，保存huffman树
  	huffmanCode *hfCode;      // 顺序结构，保存结点的huffman编码
    int size;                  // 叶结点数
    void selectMin(int m,int& p);        // 选出当前集合中的最小元素
    
public:
    huffmanTree(int initSize);    // 构造函数
    ~huffmanTree() {delete [] hfTree;delete []hfCode;}      // 析构函数
  	void createHuffmanTree(const T *d, const int *w);//创建哈夫曼树
    void huffmanEncoding();      // 获取huffman编码
    void printHuffmanCode();        // 输出huffman编码
}; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

（1）size个叶结点的哈夫曼树共有2size-1个结点，故哈夫曼树可用一个2size的数组hfTree来存储。数组下标为0的不用，根节点存放在下标为1的单元。
（2）parent域有两个作用：第一，在构造时，用于区别结点是否被使用过。parent=0表示该结点没有双亲，还未被使用过。第二，在构造后求哈夫曼编码，需从叶结点出发走一条从叶结点到根结点的路径，因此需要知道结点的双亲的信息。
（3）每个huffmanCode类型保存的信息有：数据域data以及编码code。因哈夫曼树有size个叶结点，故哈夫曼编码可以用一个大小为size的huffmanCode类型的数组hfCode来存储。

构造函数

template <class T>
huffmanTree<T>::huffmanTree(int initSize){
    size = initSize;          // size为初始集合中的结点数
    hfTree = new Node[2*size];		//顺序存储结构
	hfCode = new huffmanCode[size];	//哈夫曼编码
}
1
2
3
4
5
6

创建哈夫曼树

根据叶结点数据数组v及权值数w创建哈夫曼树

template <class T>
void huffmanTree<T>::createHuffmanTree(const T *d, const int *w) {  
    int i, min1, min2;	//最小数、次最小数的下标

    for (i = size;i < 2*size;++i) {		//给size个叶结点赋值
        hfTree[i].data = d[i-size];
        hfTree[i].weight = w[i-size];
    }

    for (i = size-1;i > 0;--i) {	//合并产生size-1个新结点
    //选出选出paretent的值为0且权值最小的两个子树min1，min2作为结点i的左右孩子
        selectMin(i+1,min1);
        hfTree[min1].parent = i;
        selectMin(i+1,min2);
        hfTree[min2].parent = i;

        hfTree[i].weight = hfTree[min1].weight + hfTree[min2].weight;
        hfTree[i].left = min1;
        hfTree[i].right = min2;
    }
} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

选出paretent的值为0且权值最小的子树的根节点，并记录下标。

template<class T>
void huffmanTree<T>::selectMin(int m,int& p){  
    int j = m;
    while (hfTree[j].parent != 0) {	//跳过已有双亲的结点
        j++;
    }

    for (p = j,j+=1;j < 2*size;j++) {		//向后扫描剩余元素
        if ( (hfTree[j].weight < hfTree[p].weight) && 0 == hfTree[j].parent) {
            p = j;		//发现更小的记录，记录它的下标
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

函数selectMin被定义在名为huffmanTree的模板类中，该类用于构建 Huffman 树。
参数m表示当前已经构建的节点数目。
函数通过遍历hfTree数组来找到权重最小的节点。hfTree数组存储了 Huffman 树的节点信息，其中hfTree[i].weight表示第i个节点的权重，hfTree[i].parent表示第i个节点的父节点在数组中的索引，如果为 0 表示没有父节点。

首先，函数通过循环跳过已经有父节点的节点，以找到尚未构建子树的节点。这是因为在构建 Huffman 树时，每次都是选择两个权重最小的节点进行合并，而已经有父节点的节点已经被合并到其他节点中了，所以不再考虑。
然后，从剩余的未被合并的节点中选择权重最小的节点。它通过遍历数组并比较节点的权重来实现。在每次循环中，如果发现当前节点的权重比记录的最小权重还要小，并且该节点没有父节点（即还未被合并），则更新记录的最小权重节点的索引。
最终，函数返回权重最小的节点的索引p，用于后续的树节点合并操作

哈夫曼编码

前缀编码：任一字符的编码都不是另一个字符的编码的前缀。
哈夫曼编码：利用哈夫曼算法可以得到最优的前编码

构造哈夫曼编码的方式：
将信息中各字符出现的频率作为权值来构造一颗哈夫曼树，每个带权叶结点都对应一个字符，根结点到叶结点都有一条路径。我们约定指向左子树用0表示，右子树用1表示，则从根节点到每个叶结点的0、1码序列的字符为哈夫曼编码。

根据哈夫曼树的每个叶结点生成哈夫曼编码：

template <class T>
void huffmanTree<T>::huffmanEncoding(){
    int f, p;	//p是正在处理的结点，f是p的双亲的下标

    for (int i = size;i < 2*size;++i) {
        hfCode[i - size].data = hfTree[i].data;
        p = i;
        f = hfTree[p].parent;

        while (f) {
            if (hfTree[f].left == p) {	//p是其双亲f的左孩子，编码+‘\0’
                hfCode[i - size].code = '0' + hfCode[i - size].code;
            } else {				//p是其双亲f的右孩子，编码+‘1’
                hfCode[i - size].code = '1' + hfCode[i - size].code;
            }

            p = f;
            f = hfTree[p].parent;
        }
    }
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

输出叶结点及其哈夫曼编码

template<class T>
void huffmanTree<T>::printHuffmanCode(){
  for (int i=0; i< size; i++) 
      cout<< hfCode[i].data <<' '<< hfCode[i].code << endl;
}
1
2
3
4
5

堆和优先级队列

堆

结构性：可看成一颗完全二叉树
有序性：任何一个结点的键值不大于（或不小于）其左、右孩子的键值
最大堆，也称大根堆或大堆：根结点是序列中的最大值。
最小堆，也称小根堆或小堆：根结点是序列中的最小值。

前面介绍过，完全二叉树适合用顺序存储结构表示和实现，因此堆可以用一维数组实现。

优先级队列

优先级队列每个元素都有一个优先级，元素出队的先后次序由优先级的高低决定，而不是由入队的先后次序决定。优先级高的先出队，优先级低的后出队。

特点：可以从一个集合快速地查找和删除具有最大值或最小值的元素。

最小优先级队列适合查找和删除最小元素。
最大优先级队列适合查找和删除最大元素。

对有n个结点的堆，从结点从1到n进行编号，数组0号单元不使用，对任意结点，若i=1，则结点i为根，无双亲；若i>1,则结点i的双亲的编号i/2。若2i<=n,则i的左孩子是2i；若2i+1<=n,则i的右孩子是2i+1。

对于一个树高度为h，包含了N=2^h+1-1个结点的满二叉树，结点高度为N-h-1；

基于小根堆的最小优先级队列的定义：

template <class elemType>
class priorityQueue{
private:
	int curLength;	//队列中元素个数
	elemType *data;		//指向存放元素的数组
	int maxSize;	//队列的大小
	
	void resize();		//扩大队列空间
	void siftDown(int parent);	//从parent位置向下调整优先级队列
	void siftUp(int position);	//从position位置向上调整优先级队列

public:
	priorityQueue(int initSize=100);	//创建容量为0的空的优先队列
	priorityQueue(const elemType data[], int size);	//用给定键值数据创建优先级队列
	~priorityQueue(){ delete [] data; }
	
	bool empty()const{ return curLength==0; }		//判空
	int size()const{ return curLength; }			//求长度
	void buildHeap();							//建堆
	void enQueue(const elemType & x);			//入队
	elemType deQueue();							//出队
	elemType getHead()const{					//取队首长度
		if(empty()) throw outOfRange();
		return data[1];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

入队

算法思想：小根堆结点个数为n，插入一个新元素时，放在数组末尾，其编号为i=n+1。
如果结点i的键值小于其双亲i/2的键值，则交换元素，直到结点i的键值不小于双亲的键值或者i到达根结点。
时间复杂度O(logn)

template <class elemType>
void priorityQueue<elemType>::enQueue(const elemType & x){
	if(curLength==maxSize-1)	resize();
	data[++curLength]=x;	//下标从1开始
	siftUp(curLength);		//新入队元素需向上调整
}
1
2
3
4
5
6

向上调整堆

当双亲的键值大时，采用向下移动双亲数据的策略，而不是交换数据。

template <class elemType>
void priorityQueue<elemType>::siftUp(int position){	//从position开始向上调整
	elemType temp=data[position];					//保存position位置元素
	for(;position>1 && temp<data[position/2];position/=2)
		data[position]=data[position/2];  //position位置元素比双亲小，双亲下移
	data[position]=temp;
}
1
2
3
4
5
6
7

出队（删除）

算法思想：在小根堆删除一个元素时，该元素必定在数组下标为1处的根结点中；删除根结点后元素个数变为n-1，为保持完全二叉树，将下标为n的叶结点暂存在下标为1的根结点中。
如果结点i的键值大于其较小孩子的键值，则交换元素，直到结点i的键值不大于其较小孩子的键值或者i到达叶结点。
时间复杂度O(logn)

template <class elemType>
void priorityQueue<elemType>::deQueue(const elemType & x){
	if(empty())		throw outOfRange();
	
	elemTpye min;
	min=data[1];	//保存最小元素
	data[1]=data[curLength--];	//队尾元素存入下标1位置（堆顶）
	siftDown(1);		//从队首向下调整
	return min;			//返回队首元素
1
2
3
4
5
6
7
8
9

向下调整堆

当孩子的键值较小时，采用向上移动较少的孩子数据的策略，而不是交换数据。

template <class elemType>
void priorityQueue<elemType>::siftDown(int parent){
	int child;
	elemType temp=data[parent];
	for(; parent*2<=curLength; parent=child){
		child = parent * 2;
		if(child != curLength && data[child+1] < data[child])
			child++;
		if(data[child]<tmp)		data[parent]=data[child];
		else break;
		}
		data[parent] = tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

建堆（自下而上）

自顶向下建堆法：首先初始化一个空的优先级队列，然后连续性进行n次入队操作。
时间复杂度O(NlogN)

自下向上建堆法：将给定的序列看成一颗完全二叉树，然后从最后一个分支结点一直根结点，调用n/2次向下调整算法，把它调整为堆.
时间复杂度O(n)

template <class elemType>
void priorityQueue<elemType>::buildHeap(){
	for(int i =curLength/2; i>0; i--)
		siftDown(i);	//[curLength/2...1]从下标最大的分支结点开始调整
}
1
2
3
4
5

其他

构造空堆

只有初始大小，无初始序列，建堆时需调用入队操作。

template <class elemType>
priorityQueue<elemType>::priorityQueue(int initSize=100){
	if(initSize<=0)	throw badSize();
	
	data = new elemType[initSize];
	maxSize = initSize;
	curLength=0;
}
1
2
3
4
5
6
7
8

构造无序堆

有初始大小和初始序列，使用堆之前需要调用buildHeap()建堆。

template <class elemType>
priorityQueue<elemType>::priorityQueue(const elemType *item, int size){
	data = new elemType[maxSize];
	for(int i=0;i<size; i++)
		data[i+1]=items[i];
}
1
2
3
4
5
6

扩大堆空间

template <class elemType>
void priorityQueue<elemType>::resize(){
	elemType * tmp = data;		//tmp指向原堆空间
	maxSize *=2;			//堆空间扩大2倍
	data = new elemType[maxSize];		//data指向新的堆空间
	
	for(int i=0; i<curLength ; ++i)
		data[i]=tmp[i];
	delete [] tmp;
}
1
2
3
4
5
6
7
8
9
10

习题（含408）

1.【408真题】下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是（）
A.24，10，5和24，10，7
B.24，10，5和24，12，7
C.24，10，10和24，14，11
D.24，10，5和24，14，6

选D

2.求根据以权值{2，5，7，9，12}构造的哈夫曼树所构造的哈夫曼编码中最大的长度。

注意求的是编码的长度。

3.一份电文中右6个字符：a,b,c,d,e,f,他们的出现频率依次为2，3，4，7，8，9，构造一颗哈夫曼树，并求WPL和字符c的编码。

WPL=80; c的编码为110

4.一组数据{6，2，7，10，3，12}，用其构造一颗哈夫曼树，求树高和WPL