浅谈【数据结构】树与二叉树之哈夫曼树
目录
1、哈夫曼树
1.1哈夫曼编码
1.2哈夫曼树
1.3构建一棵哈夫曼树
谢谢帅气美丽且优秀的你看完我的文章还要点赞、收藏加关注
没错，说的就是你，不用再怀疑！！！
希望我的文章内容能对你有帮助，一起努力吧！！！
1、哈夫曼树
1.1哈夫曼编码
在电报通信过程中，电文是以二进制0/1序列传送的，每一个字符对应了一个二进制的编码。
为了缩短按电文长度，采用不等长的编码方式，把使用频率较高的字符采用短编码。使用频率低的字符 采用长的编码。
1.2哈夫曼树
哈夫曼树：又称为最优二叉树
它是由n个带权的叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树
一棵树的带权路径长度：树中所有叶子结点的带权路径长度之和。
结点的带权路径长度：从根结点开始到该结点的路径的长度与该结点上的权值的乘积。
1.3构建一棵哈夫曼树
假设N个权值，分别为W1，W2，W3....Wn的叶子结点，构建这一棵哈夫曼树的规则：
- 第一步：
- 构建森林
- 把每一个叶子结点作为一棵独立的树看待（只有根结点的树），这样就拥有了n棵树的以 一个森林
- 把森林存放到一个优先队列（不是队列）中，方便取出最小的结点。
- 构建森林
- 第二步：
- 从优先队列中取出权值最小的两棵树（结点），再创建一棵新结点，将新结点设为两个最小结 点的父结点。父结点的权值就是两个结点的权值之和。
- 第三步：
- 将创建好的新结点加入到优先队列中。
- 第四步：
- 重复第二步和第三步直到优先队列中只剩一个结点，该节点就是哈夫曼树的根结点。
***示例代码***
#include <iostream>
#include <queue>
template <typename __queue_node_type__>
class priorityQueue
{
private:
typedef struct node
{
__queue_node_type__ data;
struct node *next;
}Node;
Node *first;
Node *final;
int count;
public:
priorityQueue()
:first(nullptr)
,final(nullptr)
,count(0)
{}
~priorityQueue()
{}
void push(__queue_node_type__ data_t)
{
// 新结点
Node *new_ptr = new Node;
new_ptr->data = data_t;
new_ptr->next = nullptr;
// 是否为链表中第一个结点
if(count == 0)
{
first = new_ptr;
final = new_ptr;
// 更新个数
count++;
return;
}
else
{
if(first->data > data_t)
{
new_ptr->next = first;
first = new_ptr;
// 更新个数
count++;
return;
}
// 查找插入位置
Node *node_ptr = first;
while(node_ptr->next)
{
if(node_ptr->data > data_t)
{
new_ptr->next = node_ptr->next;
node_ptr->next = new_ptr;
count++;
return;
}
node_ptr = node_ptr->next;
}
}
final->next = new_ptr;
final = new_ptr;
count++;
return;
}
__queue_node_type__ pop()
{
if(count == 0)
throw int(-1);
__queue_node_type__ data_t = first->data;
Node *node_ptr = first;
first = first->next;
node_ptr->next = nullptr;
delete node_ptr;
count--;
return data_t;
}
int length() const
{
return count;
}
};
template <typename __tree_node_type__>
class HafuManTree
{
private:
typedef struct node
{
__tree_node_type__ weight;
struct node *lchild;
struct node *rchild;
} Node;
Node *root;
public:
HafuManTree(std::initializer_list<__tree_node_type__> list)
: root(nullptr)
{
// 构建森林
// 创建一个优先队列
priorityQueue<Node*> queue;
// 第一步：把所有的结点存入优先队列
for(auto var : list)
{
Node *node_ptr = new Node;
node_ptr->weight = var;
node_ptr->lchild = nullptr;
node_ptr->rchild = nullptr;
queue.push(node_ptr);
}
// 第四步：重复第二步和第三步
while(queue.length()!=1)
{
// 第二步：取出权值最小的两棵树（结点），再创建一棵新结点
Node* data1 = queue.pop();
Node* data2 = queue.pop();
// 第三步创建新结点作为两个结点的父节点
Node* newfather = new Node;
newfather->weight = data1->weight + data2->weight;
newfather->lchild = data1;
newfather->rchild = data2;
// 把新结点存入优先队列
queue.push(newfather);
}
// 最后一个元素是哈夫曼树的根结点
root = queue.pop();
}
~HafuManTree(){}
void levelprint()
{
std::queue<Node*> queque;
queque.push(root);
while(queque.size())
{
Node *node_ptr = queque.front();
queque.pop();
if(node_ptr->lchild)
queque.push(node_ptr->lchild);
if(node_ptr->rchild)
queque.push(node_ptr->rchild);
std::cout << node_ptr->weight << std::endl;
}
}
};
int main()
{
HafuManTree<int> tree({1,2,3,4,5,6,7,8,9});
tree.levelprint();
return 0;
}