Huffman最优二叉树对于压缩编码具有重要作用
本文利用C++实现了Huffman二叉树做学习参考
[cpp]
/*huffman树——最优二叉树*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//定义节点结构体类型
typedef struct Node {
int val;
Node *left, *right, *parent; //左右节点和父节点指针
void set(int value, Node *lft, Node *rgt) {
val = value;
left = lft;
right = rgt;
parent = NULL;
};
Node() {
val = -1;
left = right = parent = NULL;
}
} Node;
//存放节点的向量
vector<Node> nodes;
//存放节点编号的向量
vector<int> pnodes;
//初始化最小带权路径和
int sum = 0;
//按照节点编号对应节点的值对编号进行排序
bool sortpnode(int a, int b)
{
return nodes[a].val < nodes.val;
}
//利用递归遍历huffman树实现输出
void output(Node *tree)
{
Node *ptr;
//若当前节点为空，退出
if (tree == NULL)
return;
//否则，输出当前根节点的值
cout << tree->val << "-> Left: " << (tree->left ? tree->left->val : -1) << ", Right: " << (tree->right ? tree->right->val : -1) << endl;
//若左孩子不为空，则通过递归遍历左子树
if (tree->left)
output(tree->left);
//若左孩子已遍历，且右子树不为空，则通过递归遍历右子树
if (tree->right)
output(tree->right);
//若当前节点的左右孩子都为空，则说明该节点是叶子节点
//此时，计算其带权路径并求和
if (!tree->left && !tree->right)
{
//计算到根节点的长度
int level = 0;
ptr = tree->parent;
while(ptr != NULL)
{
level++;
ptr = ptr->parent;
}
//用叶子深度乘以
sum += level * tree->val;
cout << "深度：" << level << ", 节点值：" << tree->val << "，带权路径和=" << sum << endl;
}
}
int main()
{
int values[] = {1, 2, 3, 4, 5, 30, 5, 8},
n = sizeof(values)/sizeof(int);
int cnt = n;
Node *tnode;
//直接在nodes中放入(2 + n) * n / 2
nodes.resize(2 * n - 1);
//为pnodes设置n个元素，且每个元素——即节点编号为-1
pnodes.resize(n, -1);
//为节点赋值
for(int i = 0; i < n; i++)
{
nodes.val = values;
pnodes = i;
}
//循环
while(pnodes.size() > 1)
{
//按照节点编号所对象节点的值对节点编号排序
sort(pnodes.begin(), pnodes.end(), sortpnode);
//0--n-1为已处理节点，cnt编号对应的为待处理节点
tnode = &nodes[cnt];
//为派生节点赋值并指定左、右孩子及父节点
tnode->val = nodes[pnodes[0]].val + nodes[pnodes[1]].val;
tnode->left = &nodes[pnodes[0]];
tnode->right = &nodes[pnodes[1]];
tnode->parent = NULL;
//将派生节点编号加入pnodes向量
pnodes.insert(pnodes.begin(), cnt);
//设置孩子节点的父节点地址
nodes[pnodes[1]].parent = &nodes[cnt];
nodes[pnodes[2]].parent = &nodes[cnt];
//从pnodes中删除已处理的节点编号
pnodes.erase(pnodes.begin() + 1);
pnodes.erase(pnodes.begin() + 1);
//设置下一个派生节点的编号
cnt++;
}
//nodes[cnt-1]为树的根节点
//输出树
output(&nodes[cnt-1]);
//输出huffman树的最小带权路径长度
cout << "最小带权路径长为：" << sum << endl;
return 0;
}
/*huffman树——最优二叉树*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//定义节点结构体类型
typedef struct Node {
int val;
Node *left, *right, *parent; //左右节点和父节点指针
void set(int value, Node *lft, Node *rgt) {
val = value;
left = lft;
right = rgt;
parent = NULL;
};
Node() {
val = -1;
left = right = parent = NULL;
}
} Node;
//存放节点的向量
vector<Node> nodes;
//存放节点编号的向量
vector<int> pnodes;
//初始化最小带权路径和
int sum = 0;
//按照节点编号对应节点的值对编号进行排序
bool sortpnode(int a, int b)
{
return nodes[a].val < nodes.val;
}
//利用递归遍历huffman树实现输出
void output(Node *tree)
{
Node *ptr;
//若当前节点为空，退出
if (tree == NULL)
return;
//否则，输出当前根节点的值
cout << tree->val << "-> Left: " << (tree->left ? tree->left->val : -1) << ", Right: " << (tree->right ? tree->right->val : -1) << endl;
//若左孩子不为空，则通过递归遍历左子树
if (tree->left)
output(tree->left);
//若左孩子已遍历，且右子树不为空，则通过递归遍历右子树
if (tree->right)
output(tree->right);
//若当前节点的左右孩子都为空，则说明该节点是叶子节点
//此时，计算其带权路径并求和
if (!tree->left && !tree->right)
{
//计算到根节点的长度
int level = 0;
ptr = tree->parent;
while(ptr != NULL)
{
level++;
ptr = ptr->parent;
}
//用叶子深度乘以
sum += level * tree->val;
cout << "深度：" << level << ", 节点值：" << tree->val << "，带权路径和=" << sum << endl;
}
}
int main()
{
int values[] = {1, 2, 3, 4, 5, 30, 5, 8},
n = sizeof(values)/sizeof(int);
int cnt = n;
Node *tnode;
//直接在nodes中放入(2 + n) * n / 2
nodes.resize(2 * n - 1);
//为pnodes设置n个元素，且每个元素——即节点编号为-1
pnodes.resize(n, -1);
//为节点赋值
for(int i = 0; i < n; i++)
{
nodes.val = values;
pnodes = i;
}
//循环
while(pnodes.size() > 1)
{
//按照节点编号所对象节点的值对节点编号排序
sort(pnodes.begin(), pnodes.end(), sortpnode);
//0--n-1为已处理节点，cnt编号对应的为待处理节点
tnode = &nodes[cnt];
//为派生节点赋值并指定左、右孩子及父节点
tnode->val = nodes[pnodes[0]].val + nodes[pnodes[1]].val;
tnode->left = &nodes[pnodes[0]];
tnode->right = &nodes[pnodes[1]];
tnode->parent = NULL;
//将派生节点编号加入pnodes向量
pnodes.insert(pnodes.begin(), cnt);
//设置孩子节点的父节点地址
nodes[pnodes[1]].parent = &nodes[cnt];
nodes[pnodes[2]].parent = &nodes[cnt];
//从pnodes中删除已处理的节点编号
pnodes.erase(pnodes.begin() + 1);
pnodes.erase(pnodes.begin() + 1);
//设置下一个派生节点的编号
cnt++;
}
//nodes[cnt-1]为树的根节点
//输出树
output(&nodes[cnt-1]);
//输出huffman树的最小带权路径长度
cout << "最小带权路径长为：" << sum << endl;
return 0;
}
