哈夫曼算法

哈夫曼樹是一種樹形結構，用哈夫曼樹的方法解編程題的算法就叫做哈夫曼算法。樹並不是指植物，而是一種數據結構，因為其存放方式頗有點象一棵樹有樹叉因而稱為樹。 最簡哈夫曼樹是由德國數學家馮.哈夫曼 發現的，使用了回溯的思想，此樹的特點就是引出的路程最短。 概念理解：1.路徑 從樹中一個節點到另一個節點之間的分支構成這兩個節點之間的路徑。2.路徑長度 路徑上的分支數目稱作路徑長度。

基本介紹

• 中文名：哈夫曼樹
• 結構：樹形結構
• 算法：哈夫曼算法
• 類別：數據結構
• 發明者：馮·哈夫曼
• 發明國家：德國
• 使用思想：回溯

定義

定義：它是由n個帶權葉子結點構成的所有二叉樹中帶權路徑長度最短的二叉樹。

因為這種樹最早由哈夫曼（Huffman）研究，所以稱為哈夫曼樹，又叫最優二叉樹。

概述

1.初始化： 根據給定的n個權值{w1,w2,…wn}構成n棵二叉樹的集合F={T1,T2,..,Tn}，其中每棵二叉樹Ti中只有一個帶權wi的根結點，左右子樹均空。

2. 找最小樹：在F中選擇兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且至新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和。

3. 刪除與加入：在F中刪除這兩棵樹，並將新的二叉樹加入F中。

4. 判斷：重複前兩步（2和3），直到F中只含有一棵樹為止。該樹即為哈夫曼樹

實現

用C語言最簡單的哈夫曼算法實現

#include <stdio.h>

#include <conio.h>

struct BinaryTree

{

long data;

int lchild,rchild;

};

//定義一個二叉樹結構體

void sort(struct BinaryTree cc[],int l,int r);

void xx(long kk,struct BinaryTree cc[]);

void zx(long kk,struct BinaryTree cc[]);

void hx(long kk,struct BinaryTree cc[]);

//對函式的聲明

main(void)

{

struct BinaryTree Woods[101];

long i,j,n,xs,k;

scanf("%d",&n);

for ( i=1; i<=n; ++i)

{

scanf("%d",&Woods.data);

Woods.lchild=0;

Woods.rchild=0;

} //依次讀入權值

k=n;

xs=1;

--n;

while (k>1)

{

sort(Woods,xs,n+1);

Woods[n+2].data=Woods[xs].data+Woods[xs+1].data; //將根結點權值為左子樹也右子樹權值之和

Woods[n+2].lchild=xs; //對左子樹和右子樹的設定

Woods[n+2].rchild=xs+1;

++n;

xs=xs+2;

--k;

} //哈夫曼算法

printf("%s","preorder:");

xx(n+1,Woods);

printf("\n%s","inorder:");

zx(n+1,Woods);

printf("\n%s","postorder");

hx(n+1,Woods);

printf("\n"); //輸出先序,中序,後序序列

getch();

}

//快速排序

void sort(struct BinaryTree cc[],int l,int r)

{

long x,y;

int i,j,rc,lc;

i=l;

j=r;

x=cc[(l+r)/2].data;

if (r<l)

return;

do

{

while(cc.data<x)

++i;

while(x<cc[j].data)

--j;

if (i<j)

{

y=cc.data;

rc=cc.rchild;

lc=cc.lchild;

cc.data=cc[j].data;

cc.lchild=cc[j].lchild;

cc.rchild=cc[j].rchild;

cc[j].data=y;

cc[j].lchild=lc;

cc[j].rchild=rc;

++i;

--j;

}

}

while(i>j);

if (i<r)

sort(cc,i,r);

if (j>l)

sort(cc,l,j);

}

//先序序列

void xx(long kk,struct BinaryTree cc[])

{

if (cc[kk].data!=0)

{

printf("%d%c",cc[kk].data,' ');

if (cc[kk].lchild!=0)

xx(cc[kk].lchild,cc);

if (cc[kk].rchild!=0)

xx(cc[kk].rchild,cc);

}

}

//中序序列

void zx(long kk,struct BinaryTree cc[])

{

if (cc[kk].data!=0)

{

if (cc[kk].lchild!=0)

zx(cc[kk].lchild,cc);

printf("%d%c",cc[kk].data,' ');

if (cc[kk].rchild!=0)

zx(cc[kk].rchild,cc);

}

}

//後序序列

void hx(long kk,struct BinaryTree cc[])

{

if (cc[kk].data!=0)

{

if (cc[kk].lchild!=0)

hx(cc[kk].lchild,cc);

if (cc[kk].rchild!=0)

hx(cc[kk].rchild,cc);

printf("%d%c",cc[kk].data,' ');

}

}