数据结构_哈夫曼树及其应用

构造算法的例子

构造算法的实现

初始化，置权值

int i, m, s1, s2;m = 2 * n - 1;for (i = 1; i <= m; i++){HT[i].lch = 0;HT[i].rch = 0;HT[i].parent = 0;}for (i = 1; i <= n; i++){cin >> HT[i].weight;}

合并结点

// 创建哈夫曼树for (i = n + 1; i <= m; i++){s1 = -1;s2 = -1;Selete(HT, i - 1, s1, s2);HT[s1].parent = i;HT[s2].parent = i;HT[i].lch = s1;HT[i].rch = s2;HT[i].weight = HT[s1].weight + HT[s2].weight;}

哈夫曼编码

void HuNode::create_Code(HuNode* HT, char** code, int n)
{int i, current, parent, k;char temp[100]; // 临时数组存放编码for (i = 1; i <= n; i++){current = i;parent = HT[i].parent;k = 0; // 编码长度计数器while (parent != 0){if (HT[parent].lch == current){temp[k] = '0'; // 左子节点编码为 '0'k++;}else{temp[k] = '1';k++;}current = parent;parent = HT[current].parent;}temp[k] = '\0';// 将编码倒置并保存code[i] = new char[k + 1];for (int j = 0; j < k; j++){code[i][j] = temp[k - j - 1];}code[i][k] = '\0';}
}

文件的编码或译码

int HuNode::Decode(const string codestr, char txtstr[], int n)
{int index, root, i, curNode;index = 0;root = 2 * n - 1; // 根节点编号curNode = root;for (i = 0; i < codestr.length(); i++){if (codestr[i] == '0'){curNode = this[curNode].lch;}else{curNode = this[curNode].rch;}// 解码失败if (curNode == 0){return error;}// 是叶子节点if (this[curNode].lch == 0 && this[curNode].rch == 0){txtstr[index] = this[curNode].data;index++;curNode = root;}}if (curNode != root){return error;}txtstr[index] = '\0';return ok;
}