數據結構—哈夫曼樹

原理：參考趣學數據結構

代碼：

#include<stdio.h> #include<stdlib.h> #define N 100 #define INF 2^31-1 typedef struct fNode {//哈夫曼樹中每個節點的信息int c;//字符int parent;//父節點，左右孩子，權重int lchild, rchild;int weight; }fNode; typedef struct rNode {//存儲單個的編碼字符的編碼序列int r[N];int start;//有效編碼起始的位置int length; }rNode; void huffMan(fNode fnode[],int n) {//構造哈夫曼樹 選取二個最小的沒有父節點的結點合并，以此類推for (int i = 0; i < n - 1; i++) {//n個字符n-1次的構造即可構造哈夫曼樹int min1=INF, min2 = INF;int u =-1,v = -1;for (int j = 0; j < n + i; j++) {//找二個最小的沒有父節點的if (fnode[j].weight < min1 && fnode[j].parent==-1) {min2 = min1;//最值同時往前推v = u;min1 = fnode[j].weight;u = j;}else if(fnode[j].weight<min2 && fnode[j].parent == -1) {min2 = fnode[j].weight;v = j;}}fnode[n + i].weight = min1 + min2;fnode[n + i].lchild = u;fnode[n + i].rchild = v;fnode[u].parent = fnode[v].parent = n + i;//更新父節點} } void findHuffManCodePath(fNode fnode[],rNode rnode[],int n) {//尋找每個字符編碼表示rNode temp;int start=n-1;//最壞的哈夫曼樹為一條鏈表for (int i = 0; i < n; i++) {start = n - 1;//每個字符的編碼從葉子節點向根節點遍歷int p = fnode[i].parent;int tempv = i;while (p != -1) {//p不等于-1表示有父節點if (tempv == fnode[p].lchild) {temp.r[start] = 0;}else {temp.r[start] = 1;}start--;tempv = p;p = fnode[p].parent;}for (int j = start + 1; j <= n - 1; j++) {//更新每個字符的編碼數組rnode[i].r[j] = temp.r[j];rnode[i].start = start + 1;}rnode[i].length = n - start - 1;}int sum = 0;//遍歷每個字符的編碼數組for (int j = 0; j < n; j++) {//n個字符的編碼遍歷printf("%d的哈夫曼編碼為:", fnode[j].c);for (int k = rnode[j].start; k <= n - 1; k++) {printf("%d", rnode[j].r[k]);}sum += (fnode[j].weight*rnode[j].length);printf(" ");}printf("\n");printf("哈夫曼編碼長度為:%d\n",sum);printf("\n"); } int main() {fNode fnode[N];rNode rnode[N];int u;printf("請輸入編碼字符的個數:");scanf_s("%d", &u);int length = u;int c;int weight=0;//http://c.biancheng.net/view/1796.html 輸入字符參考for (int k = 0; k < u;k++) {//初始化字符編碼的信息 //c = getchar();//輸入字符scanf_s("%d %d", &c,&weight);fnode[k].c = c;fnode[k].weight = weight;}u = 2 * length - 1;//哈夫曼總共有2n-1個結點for(int i=0;i<u;i++){//初始化結點的左右孩子和父節點信息fnode[i].lchild = -1;fnode[i].rchild = -1;fnode[i].parent = -1;}huffMan(fnode, length);findHuffManCodePath(fnode, rnode, length);system("pause");return 0; }

測試截圖：

時間復雜度O(n x n),空間復雜度O(n)

如果存在什么問題，歡迎批評指正！謝謝！

總結

以上是生活随笔為你收集整理的数据结构---哈夫曼树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。