[数据结构与算法]2021-10-06

计算Huffman树的带权路径长度WPL（C++优先队列实现）

1 构建一棵Huffman树

typedef struct HTreeNode
{
    DataType data;  //结点的关键字
    HTreeNode *lchild,*rchild;  //左右孩子
    int level;  //结点在树中的层次
    
}HTreeNode,*HTree;

/***
 * 构造Huffman树：
 * 对于优先队列中的结点，每次取下两个合成一个新的结点重新加入优先队列，直至优先队列中仅剩一个结点
 * 由于优先队列，所以我们每次取下的，必然是两个最小的关键字结点，契合Huffman算法
 **/ 
HTree HuffmanTree(priority_queue<HTree,vector<HTree>,cmp> &q){
    
    while (q.size()>1)//仅剩一个结点（即Huffman树的根节点时跳出循环）
    {
        HTree h1=q.top();
        q.pop();
        HTree h2=q.top();
        q.pop();
        HTree h=(HTreeNode*)malloc(sizeof(HTreeNode));  //将取出的两个节点合成新的结点
        h->lchild=h1;
        h->rchild=h2;
        h->data=h1->data+h2->data;
        q.push(h);
    }

    return q.top();
    
}

2 计算Huffman树中指定结点所在的层次

//计算在Huffman树中指定p结点的层次
int getLevel(HTree tree,HTreeNode* p){
    if(!tree)
        return 0;
    if(tree==p){//发现了p结点，则当前层为第一层，向上累加可得p结点的层次
        return 1;
    }
    int lLevel=getLevel(tree->lchild,p);
    int rLevel=getLevel(tree->rchild,p);
    
    if (lLevel || rLevel) //左右孩子不全为NULL时，则当前结点可能是根结点到P结点路径上的点，需要继续递归探查
    {
         return lLevel>rLevel? lLevel+1:rLevel+1;
    }
    //当tree结点不为NULL，不是p结点，又是叶子结点（即p不会是根节点到P结点路径上的点）
    return 0;
    
}

3 设置Huffman树中所有结点的层次

/***
 *设置HuffmanTree每个结点的层次值，这里采用遍历每个结点进行设置。 
 **/
void setTNodeDepth(HTree &tree){
    HTree t=tree;
   
    queue<HTree> q;
    q.push(tree);
    while(!q.empty()){
        HTree h=q.front();
        q.pop();
        h->level=getLevel(tree,h);
       	if(h->lchild)
            q.push(h->lchild);
        if(h->rchild)
            q.push(h->rchild);
    }
    
}

4 计算Huffman树的带权路径长度WPL

/***
 * 计算Huffman的WPL值：所有叶子的层次和权值的乘积之和
 **/
int getHuffmanTreeWPL(HTree tree){
    HTree t=tree;
    int HuffmanTreeWPL=0;
    queue<HTree> q;
    q.push(tree);
    while(!q.empty()){
        HTree h=q.front();
        q.pop();
        h->level=getLevel(tree,h);
        if(!h->lchild && !h->rchild){//只计算叶子节点的权值
            HuffmanTreeWPL+=(h->level*h->data);
        }
        if(h->lchild)
            q.push(h->lchild);
        if(h->rchild)
            q.push(h->rchild);
    }

    return HuffmanTreeWPL;
}

完整代码如下所示：

/*
 * @Descripttion: 利用C++ STL的优先队列解决Huffman问题
 * @version: 1.0
 * @Author: Sakura
 * @Date: 2021-10-06 12:34:18
 * @LastEditTime: 2021-10-06 22:45:15
 */
#include <iostream>
#include<queue>
#include<stack>
#define N 100
#define DataType int
using namespace std;

typedef struct HTreeNode
{
    DataType data;
    HTreeNode *lchild,*rchild;
    int level;
    
}HTreeNode,*HTree;

/**
 * 设置优先队列的排序规则，关键字小的放在队头
 **/ 
struct cmp
{
	bool operator () (const HTree &a, const HTree &b)		  
	{
		return a->data>b->data;			
	}
};

/**
 * 将数组中的关键字，逐个存入到优先队列中
 **/ 
void init(priority_queue<HTree,vector<HTree>,cmp> &q,int arr[],int len){

    
    for(int i=0;i<len;i++){
        HTree h=(HTreeNode*)malloc(sizeof(HTreeNode));
        h->lchild=NULL;
        h->rchild=NULL;
        h->data=arr[i];
        q.push(h);
    }

}

//输出整个优先队列
void print(priority_queue<HTree,vector<HTree>,cmp> &q){
    while (!q.empty())
    {
        HTree h=q.top();
        q.pop();
        cout<<h->data<<endl;
    }

    cout<<"--------------------------"<<endl;
}

/***
 * 构造Huffman树：
 * 对于优先队列中的结点，每次取下两个合成一个新的结点重新加入优先队列，直至优先队列中仅剩一个结点
 * 由于优先队列，所以我们每次取下的，必然是两个最小的关键字结点，契合Huffman算法
 **/ 
HTree HuffmanTree(priority_queue<HTree,vector<HTree>,cmp> &q){
    
    while (q.size()>1)//仅剩一个结点（即Huffman树的根节点时跳出循环）
    {
        HTree h1=q.top();
        q.pop();
        HTree h2=q.top();
        q.pop();
        HTree h=(HTreeNode*)malloc(sizeof(HTreeNode));  //将取出的两个节点合成新的结点
        h->lchild=h1;
        h->rchild=h2;
        h->data=h1->data+h2->data;
        q.push(h);
    }

    return q.top();
    
}
//递归计算指定节点的高度（与本题无关）
int getDepth(HTree tree){
    if (tree==NULL)
    {
        return 0;
    }else{
        
        int lDepth=getDepth(tree->lchild);
        int rDepth=getDepth(tree->rchild);
        return lDepth>rDepth? lDepth+1:rDepth+1;
    }
    
}

//计算在Huffman树中指定p结点的层次
int getLevel(HTree tree,HTreeNode* p){
    if(!tree)
        return 0;
    if(tree==p){//发现了p结点，则当前层为第一层，向上累加可得p结点的层次
        return 1;
    }
    int lLevel=getLevel(tree->lchild,p);
    int rLevel=getLevel(tree->rchild,p);
    
    if (lLevel || rLevel) //左右孩子不全为NULL时，则当前结点可能是根结点到P结点路径上的点，需要继续递归探查
    {
         return lLevel>rLevel? lLevel+1:rLevel+1;
    }
    //当tree结点不为NULL，不是p结点，又是叶子结点（即p不会是根节点到P结点路径上的点）
    return 0;
    
}

/***
 *设置HuffmanTree每个结点的层次值，这里采用遍历每个结点进行设置。 
 **/
void setTNodeDepth(HTree &tree){
    HTree t=tree;
    // int treeHeight=getDepth(tree);  //HuffmanTree的树高度
    queue<HTree> q;
    q.push(tree);
    while(!q.empty()){
        HTree h=q.front();
        q.pop();
        h->level=getLevel(tree,h);
        // cout<<tree->data<<"  "<<h->data<<"  "<<h->level<<endl;
        if(h->lchild)
            q.push(h->lchild);
        if(h->rchild)
            q.push(h->rchild);
    }
    
}

/***
 * 计算Huffman的WPL值：所有叶子的层次和权值的乘积之和
 **/
int getHuffmanTreeWPL(HTree tree){
    HTree t=tree;
    int HuffmanTreeWPL=0;
    queue<HTree> q;
    q.push(tree);
    while(!q.empty()){
        HTree h=q.front();
        q.pop();
        h->level=getLevel(tree,h);
        if(!h->lchild && !h->rchild){//只计算叶子节点的权值
            // cout<<h->level<<"*"<<h->data<<"="<<h->level*h->data<<endl;
            HuffmanTreeWPL+=(h->level*h->data);
        }
        if(h->lchild)
            q.push(h->lchild);
        if(h->rchild)
            q.push(h->rchild);
    }

    return HuffmanTreeWPL;
}

int main(){
    
    DataType arr[N] = {1, 8, 15, 19, 32, 17, 65, 3, 9};
    int len = 9;
    priority_queue<HTree,vector<HTree>,cmp> q;
    init(q,arr,len);
    HTree tree=HuffmanTree(q);

    setTNodeDepth(tree);
    cout<<getHuffmanTreeWPL(tree)<<endl;
    return 0;
}

小白也是在学习数据结构，哪里学的不通透欢迎各位指正！
觉得写得不错的话，点个赞吧！