前面我们介绍了哈夫曼树的理论实现，现在介绍一下具体代码实现。
我们先定义哈夫曼树节点的数据结构。
struct haffManTreeNode // 哈夫曼树的节点
{
char symbol; //存储的符号
int weight; //权重
haffManTreeNode* lChild;
haffManTreeNode* rChild;
};
struct haffManTreeRoot //为了方便，特别定义一个根节点
{
haffManTreeNode* next;
};
haffManTreeNode* initHaffManTreeNode(char symbol,int weight)
{
//初始化一个树节点
haffManTreeNode* tree = new haffManTreeNode;
tree->lChild = NULL;
tree->rChild = NULL;
tree->symbol = symbol;
tree->weight = weight;
return tree;
}
在有了树节点之后，我们需要一个链表结构来存储不同节点的权值，并将他们排序，用这些节点来构成我们的哈夫曼树。
struct haffManQueue //定义的链表结构
{
haffManTreeNode* tree; //存储哈夫曼树的节点
int weight; //节点的权重
haffManQueue* next;
};
struct haffManQueueHead //为了方便，定义一个头链表，存储链表大小
{
int size;
haffManQueue* next;
};
haffManQueue* initQueue()
{
//初始化链表节点
haffManQueue* queue = new haffManQueue;
queue->weight = 0;
queue->tree = NULL;
queue->next = NULL;
return queue;
}
在定义完了最基础的数据结构后，我们需要获得一个数组，用来存储一段文本的单个字符出现次数（权重），这里，我们利用数组下标实现这个功能。
void getWeight(string& str,int (&weight)[256])
{
//在这里，我们传入一个数组，与文本字符串
//注：（1）我们需要传入数组的引用，因为我们需要用形参影响实参
//（2）我们传入的数组大小为256位，正好是全部字符的个数
for(int i=0;i <= 255;i++)
{
//初始化数组
weight[i] = 0;
}
int count = str.length();
for(int i=0;i < count;i++)
{
//利用ascii码唯一对应的数字来标注
weight[ (char)str[i] ]++;
}
}
接下来，我们拥有了这个权重数组，那么我们需要的就是按照哈夫曼树的建立过程实现代码。
//先定义插入函数，可以更加简单。。。这里写的有些复杂
//注：同样，我们需要传入head的引用，因为我们需要在函数中改变其中指针的值
void insertQueue(haffManQueueHead* (&head),haffManQueue* (&inserter),haffManQueue* (&address))
{
//在address指针后面插入inserter指针，若address为NULL，则表示在表头后插入
if(address == NULL)
{
inserter->next = head->next;
head->next = inserter;
}
else if(address->next == NULL)
{
address->next = inserter;
}
else
{
inserter->next = address->next;
address->next = inserter;
}
}
//定义取值函数，取出当前链表中权重最小的节点
haffManQueue* getQueueItem(haffManQueueHead* (&head))
{
if(head->size == 0)
{
return NULL;
}
haffManQueue* temp = head->next;
head->next = head->next->next;
head->size--;
return temp;
}
//由权重数组，得到哈夫曼队列
haffManQueueHead* initHaffManQueue(int (&weight)[256])
{
//建立表头
haffManQueueHead* head = new haffManQueueHead;
head->next = NULL;
head->size = 0;
for(int i=0;i <= 255;i++)
{
if(weight[i] != 0)
{
if(head->size == 0)
{
//如果整个链表没有元素，直接插入为第一个
haffManQueue* queue = initQueue();
queue->tree = initHaffManTreeNode((char)i,weight[i]);
queue->weight = queue->tree->weight;
head->next = queue;
head->size++;
}
else
{
haffManQueue* queue = initQueue();
queue->tree = initHaffManTreeNode((char)i,weight[i]);
queue->weight = queue->tree->weight;
//定义两个指针，用来插入节点
haffManQueue* temp = head->next;
//指向当前节点的前一个元素，因为是单向链表，无法知道之前的元素地址
haffManQueue* preNode = NULL;
while(queue->weight > temp->weight && temp != NULL)
{
preNode = temp;
temp = temp->next;
}
insertQueue(head,queue,preNode);
head->size++;
}
}
}
return head;
}
//在得到哈夫曼队列之后，我们便可以建立我们的哈夫曼树了
haffManTreeRoot* creataHaffManTree(haffManQueueHead* (&head))
{
//初始化哈夫曼树的根节点
haffManTreeRoot* root = new haffManTreeRoot;
root->next = NULL;
if(head->size == 0)
{
return root;
}
else
{
while(head->size != 1)
{
//当链表大小为一时，退出循环
haffManQueue* lChild = getQueueItem(head);
haffManQueue* rChild = getQueueItem(head);
haffManQueue* newNode = initQueue();
//用'\0'，来填充新节点的符号位，权重为两个子树权重之和
newNode->tree = initHaffManTree('\0',lChild->weight+rChild->weight);
//将两个节点作为新节点的子树
newNode->tree->lChild = lChild->tree;
newNode->tree->rChild = rChild->tree;
newNode->weight = newNode->tree->weight;
//重新插入回链表，排序
if(head->size == 0)
{
head->next = newNode;
head->size++;
}
else
{
haffManQueue* temp = head->next;
haffManQueue* preNode = NULL;
while(newNode->weight > temp->weight && temp != NULL)
{
preNode = temp;
temp = temp->next;
}
insertQueue(head,newNode,preNode);
head->size++;
}
}
}
root->next = head->next->tree;
return root;
}
这就是我个人关于哈夫曼树的实现过程。
