C++ 实现哈夫曼树

离散数学课本最后一章有讲到这一种“近大远小”的数据结构哈夫曼树，这种数据结构是实现哈夫曼编码的基础，书上讲得比较抽象于是尝试用C++简单的实现一下。

0x00 前提

在这看到了一个比较通俗易懂的解释:

https://baijiahao.baidu.com/s?id=1663514710675419737&wfr=spider&for=pc

主要就是通过一个优先队列+树的结构来实现的，之前没用过STL里面的优先队列，因为需要将元素设置为自定义类型的指针，所以需要写一个比较函数来实现升序排列（ priority_queue 默认是降序排列）。

如下：

struct compareNode{ //重写仿函数
	bool operator()(Node *&a, Node *&b) const
	{
		return a->weight > b->weight;//小顶堆
	}
};
priority_queue<Node*,vector<Node*>,compareNode> nodeQueue; //升序

0x01 代码实现

#include<cstdio>
#include<cstring>
#include<unistd.h>
#include<iostream>
#include<queue>
using namespace std;

#define MAXINPUT 64
#define raiseError(errMsg) write(2,errMsg,strlen(errMsg));exit(-1);
/*初始化一个新节点*/
#define initNewNode(ptr) ptr=(Node*)malloc(sizeof(Node));\
    if(ptr==NULL){raiseError("Malloc error!");}         \ 
    ptr->weight=-1;                                     \
    ptr->father=NULL;                                   \
    ptr->left=NULL;                                     \
    ptr->right=NULL;
/*生成父节点*/                                        
#define getNewFatherNode(father,leftPtr,rightPtr) initNewNode(father);\
    father->weight = leftPtr->weight + rightPtr->weight;    \
    father->left = leftPtr; father->right = rightPtr;       \
    leftPtr->father = father; rightPtr->father = father;

struct Node{
    int weight;
    struct Node *father;
    struct Node *left;
    struct Node *right;
    bool operator < (const Node &v) const{ 
        return weight > v.weight;   
    }
};
struct compareNode{
	bool operator()(Node *&a, Node *&b) const
	{
		return a->weight > b->weight; //小顶堆
	}
};
priority_queue<Node*,vector<Node*>,compareNode> nodeQueue; //升序

Node *currRoot=NULL;

void initNodeQueue(int *input,int len){ //初始化叶子节点队列
    Node *tmp=NULL;
    for(int i=0;i<len;i++){
        initNewNode(tmp);
        tmp->weight=input[i];
        nodeQueue.push(tmp);
        //printf("%d\n",tmp->weight);
    }
}

Node *huffmanTree(){ //构造哈夫曼树
    Node *leftPtr=NULL,*rightPtr=NULL;
    Node *father=NULL;
    while(nodeQueue.size()>1){
        leftPtr = nodeQueue.top(); nodeQueue.pop();
        rightPtr = nodeQueue.top(); nodeQueue.pop();
        getNewFatherNode(father,leftPtr,rightPtr);
        currRoot = father;
        nodeQueue.push(father);
    }
    return currRoot;
}

int main(int argc,char **argv){
    int input[MAXINPUT]={0};
    int j=0,len=0;
    scanf("%d",&len); //读取叶子节点个数
    len=len<MAXINPUT?len:MAXINPUT;
    for(int i=0;i<len;i++){
        scanf("%d",&input[i]); //读取叶子节点的权
    }
    initNodeQueue(input,len);
    huffmanTree();
    printf("Root weight: %d\n",currRoot->weight);
    return 0;
}