亲宝软件园·资讯

展开

C++哈夫曼树 C++实现哈夫曼树的方法

李杨在路上 人气:0

序言

对于哈夫曼编码,个人的浅薄理解就是在压缩存储空间用很大用处。
用一个很简单例子,存储一篇英文文章时候,可能A出现的概率较大,Z出现的记录较小,如果正常存储,可能A与Z存储使用的空间一样。但是用哈夫曼编码方式,A经常出现,所用编码长度就短。

构造哈夫曼树,生成哈夫曼编码

一、定义节点类型

struct Node {
 char C;
 long key;
 Node *Left, *Right,*parent;
 Node() { Left = Right = NULL; }
};

二、定义树类型(节点数组)

三要素:不定长数组,元素大小,有效元素个数

struct RootA {
 Node *NodeA;
 const int Size;
 int n;
 RootA(int Size) :Size(Size) { n = 0; NodeA = new Node[Size]; }
 ~RootA() { delete[]NodeA; }
};

三、创建哈夫曼树

1.将每一个节点都当成一棵树,初始化数组大小,并进行赋值

RootA RA(4);
 //1.在RA.NodeA中存入字母和权值
 for (RA.n = 0;RA.n < RA.Size;RA.n++) {
 cout << "字母:";
 cin >> RA.NodeA[RA.n].C;
 cout << "权值:";
 cin >> RA.NodeA[RA.n].key;
 }

2.将树按权值大小排序

void Sort(RootA *ra) {
 for (int i = 0;i < ra->n;i++) {
 bool ESC = false;
 for (int j = 0;j < ra->n - i - 1;j++) {
  if (ra->NodeA[j].key > ra->NodeA[j + 1].key) {
  Node T;T = ra->NodeA[j];ra->NodeA[j] = ra->NodeA[j + 1];ra->NodeA[j + 1] = T;
  ESC = true;
  }
 }
 if (!ESC) return;
 }
}

3.(1)遍历数组,将RA.NodeA[0]和RA.Node[1]合并,其余向前移动,重新排序
(2)将RA.NodeA[0],RA.NodeA[1]分别放在新合并的RA.NodeA[0]的左右子结点中

while (RA.n > 1) {
 //1.将RA.NodeA[0]和RA.NodeA[1]合并,将其余向前移动
 Node *NewNode0 = new Node;
 *NewNode0 = RA.NodeA[0];
 Node *NewNode1 = new Node;
 *NewNode1 = RA.NodeA[1];
 RA.NodeA[0].C = ' ';
 RA.NodeA[0].key = RA.NodeA[0].key + RA.NodeA[1].key;
 RA.NodeA[0].Left = NewNode0;
 NewNode0->parent = &RA.NodeA[0];
 RA.NodeA[0].Right = NewNode1;
 NewNode1->parent = &RA.NodeA[0];
 for (int i = 1;i < RA.n-1;i++) {
  RA.NodeA[i] = RA.NodeA[i + 1];
 }
 RA.n = RA.n - 1;
 //2.排序
 Sort(&RA);
 }

4.输出哈夫曼编码

递归,找到叶子节点,记录路径,左记录0,右记录1,直到输出所有叶子节点

void CrateCode(Node *t,string &s) {
 //1.遍历节点,遍历左节点编码为0,右节点则为1,递归,直到输出所有叶子节
 if (t->Left != NULL && t->Right != NULL) {
 s.push_back('0'); CrateCode(t->Left, s);
 s.pop_back();
 s.push_back('1');CrateCode(t->Right, s);
 s.pop_back();
 }
 else {
 cout << "哈夫曼编码:";
 cout << t->C << ":" << s<<endl;
 }
}

以上是对构造哈夫曼树以及生成哈夫曼编码的总结,希望对你们有所帮助!

加载全部内容

相关教程
猜你喜欢
用户评论