wpl演算法java

⑴ 哈夫曼樹左小右大是指什麼

哈弗曼（Huffman）樹，也稱最優樹，是一類帶全路徑長度最短的樹，在實際中有廣泛的應用，也是二叉樹的一個具體應用。
在哈夫曼樹的定義中，涉及到了路徑、路徑長度、權等概念，下面先給出概念的定義。

一、概念與定義

路徑：從樹的一個結點到另一個結點的分支構成這兩個結點之間的路徑，對於哈夫曼樹特指從根節點到某節點的路徑。

路徑長度：路徑上的分支數目叫做路徑長度。
樹的路徑長度：從樹根到每一結點的路徑長度之和。
權：賦予某一個事物的一個量，是對事物的某個或某些屬性數值化描述。在數據結構中，包括結點和邊兩大類，所以對應有結點權和邊權。其具體代表的意義有具體情況而定。
結點的帶權路徑長度：從樹根到結點之間的路徑長度與結點上權的乘積。
樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和(WPL--weighted path length)。它的權值分別為，從根到各葉子結點的路徑長度分別為。則其帶權路徑長度WPL通常記作：

WPL的計算如下所示：

對於圖a：WPL=2*(9+8+1+6)=48;

對於圖b：WPL=8*1+9*2+(1+6)*3=47;

對於圖c：WPL=9*1+8*2+(1+6)*3=46;

由圖可以看出，權值越大的結點離根節點越近。

二、哈夫曼樹構造演算法

哈弗曼樹的構造步驟：

1、根據給定的n個權值（w1,w2,w3,....wn）,構造n棵只有根結點的二叉樹，令起權值為wj；
2、在森林中選取兩棵根結點權值最小的樹作為左右子樹，構造一棵新的二叉樹，置新二叉樹根結點權值為其左右子樹根結點權值之和
3、在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中；
4、重復上述兩個步驟，最後構成的樹即為哈弗曼樹。
下圖顯示了構造一棵哈弗曼樹的兩種方法：
常見的構造比較簡單，這里我選擇了兩種比較特殊的數據進行了構造：
哈弗曼樹並行生長的原則：如果新形成的二叉樹的根節點的值大於或等於森林中的另外兩個只有根結點樹的值，那麼接下來的兩棵樹將並行生長。並不是線性的直接向上生長。

構造方法一：

構造方法二：

最後顯示了哈夫曼樹的編碼，編碼的原則左小右大。

三、哈夫曼樹在編碼中的應用
哈夫曼樹最常應用的地方就是對報文進行編碼傳輸通信。在數據的交流中，我們對數據是有要求的：
（1）解碼結果與發送方發送的電文完全一樣。也就是說發送方傳輸的二進制編碼，到接收方解碼後必須具有唯一性；
（2）為了傳輸的效率和網路的通信及時佔用資源少，發送的二進制編碼盡可能地短。
下面介紹兩種編碼方式：
1. 等長編碼
這種編碼方式的特點是每個字元的編碼長度相同，編碼長度就是每個編碼被翻譯的二進制位數。假設字元集只含有4個字元A，B，C，D，用二進制兩位表示的編碼分別為00，01，10，11。 若現在有一段電文為：ABACCDA，則應發送二進制序列：000100101011000111，總長度為16位。當接收方接收到這段電文後，將按兩位一段進行解碼。這種編碼的特點是解碼簡單且具有唯一性，但是存在的問題是編碼長度並不是最短的，不滿足上面的（2）的要求，因為在大數據量的情況下，我們必須的考慮效率問題，那麼如何得到最短的編碼呢？使用哈夫曼樹就可以解決這個問題。這里先介紹一個前綴嗎的概念。
前綴碼：如果在一個系統中，任意一個編碼都不是其他任何編碼的前綴（最左子串），則稱此編碼系統中的編碼是前綴碼。
例如：（A:110、B:111、C:10、D:0）就是前綴碼。但是（A:110、B:11、C:00、D:0）就不是前綴碼。0是00的前綴，11是110的前綴。如果不定長的編碼不是前綴碼，則在解碼時會產生二義性。例如110是A呢？還是BD呢？所以對於不定長編碼一定要是前綴碼。
2. 不等長編碼
不等長編碼可以叫最優的前綴碼。在傳送報文時，為了使其二進制位數盡可能地少，可以將每個字元的編碼設計為不等長的， 使用頻度較高的字元分配一個相對比較短的編碼，使用頻度較低的字元分配一個比較長的編碼。如何得到最優的前綴編碼呢？我們就可以利用上述的哈夫曼樹來設計，同常成這種編碼為哈夫曼編碼，它不僅減少電文的總長，還必須考慮編碼的唯一性。

四、哈夫曼樹中的唯一和不唯一
唯一：哈夫曼樹的WPL一定是最小的，唯一，最優是不變的。
不唯一：編碼不唯一（表現出來就是形態不唯一）。比如說左小右大，或者是左大右小，樹枝左右順序是可以交換的，也就是說所得的哈夫曼編碼則可能不同

⑵ 到底什麼是哈夫曼樹啊，求例子

哈夫曼樹是給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。

例子：

1、將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；

2、 在森林中選出兩個根結點的權值最小的樹合並，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；

3、從森林中刪除選取的兩棵樹，並將新樹加入森林；

4、重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

(2)wpl演算法java擴展閱讀：

按照哈夫曼編碼構思程序流程：

1、切割的順序是從上往下，直至數組中的元素全部出現在葉節點；

2、我們思路正好相反，從數組中找出最小的兩個元素作為最下面的葉節點，在向備選數組中存入這兩個葉節點的和（這個新的和加入累加運算，這個和也就是所求的最小值的一部分，原因如上圖）。

3、以本題為例，備選數組中現有元素為{30，30}，再次取出兩個最小元素進行求和，得到新的元素，回歸備選數組並記入累加。

4、上述2.3布重復執行直至備選數組中只有一個元素，此時累加結束，返回累加值即可

5、求數組中的最小值，可以用小根堆進行提取最為方便；此題用到了貪心的思路，即用相同的策略重復執行，直至我們得到所需的結果。

⑶ 對於給定的一組權值W={1, 3, 7, 8, 14},建立哈夫曼樹.

五個權值是137814

(1)從小到大排序137814(這是有序序列)
(2)每次提取最小的兩個結點,取結點1和結點3,組成新結點N4,其權值=1+3=4,
取數值較小的結點作為左分支,1作為左分支,而3就作為右分支.
(3)將新結點N4放入有序序列,保持從小到大排序:
N47814
(4)重復步驟(2),提取最小的兩個結點,N4與結點7組成新結點N11,其權值=4+7=11,
N4數值較小,作為左分支,而結點7就作為右分支.
(5)將新結點N11放入有序序列,保持從小到大排序:
8N1114
(6)重復步驟(2),提取最小的兩個結點,結點8與N11組成新結點N19,其權值=8+11=19,
結點8的數值較小,作為左分支,N11就作為右分支.
(7)將新結點N19放入有序序列,保持從小到大排序:
14N19
(8)重復步驟(2),提取剩下的兩個結點,結點14與N19組成新結點N33,其權值=14+19=33,
數值較小的結點14作為左分支,N19就作為右分支.
有序序列已經沒有結點,最後得到"哈夫曼樹":

N33
/
14N19
/
8N11
/
N47
/
13

帶權路徑長度(WPL):
根結點N33到結點14的路徑長度是1,結點14的帶權路徑長度是14*1
根結點N33到結點8的路徑長度是2,結點8的帶權路徑長度是8*2
根結點N33到結點7的路徑長度是3,結點7的帶權路徑長度是7*3
根結點N33到結點3的路徑長度是4,結點3的帶權路徑長度是3*4
根結點N33到結點1的路徑長度是4,結點1的帶權路徑長度是1*4
所以,哈夫曼樹的帶權路徑長度(WPL)等於
14*1+8*2+7*3+3*4+1*4=67

哈夫曼編碼:
規定哈夫曼樹的左分支代表0,右分支代表1.
從根結點N33到結點14,經歷一次左分支,結點14的編碼就是0
從根結點N33到結點8,先經歷右分支,後經歷左分支,結點8的編碼就是10
從根結點N33到結點7,先後經歷三次右分支,結點7的編碼就是111
從根結點N33到結點3,先經歷兩次右分支,再經歷左分支,最後經歷右分支,結點3的編碼就是1101
從根結點N33到結點1,先經歷兩次右分支,再經歷兩次左分支,結點1的編碼就是1100
得出所有結點的"哈夫曼編碼":
權值14:0
權值8:10
權值7:111
權值3:1101
權值1:1100


//C語言測試程序(來自其他網友)
//
//輸入構造哈夫曼樹中帶權葉子結點數(n)：5
//輸入5個整數作為權值：137814
//可以得出哈夫曼樹的廣義表形式,帶權路徑長度,以及哈夫曼編碼.

#include<stdio.h>
#include<stdlib.h>
typedefintElemType;
structBTreeNode
{
ElemTypedata;
structBTreeNode*left;
structBTreeNode*right;
};

//1、輸出二叉樹，可在前序遍歷的基礎上修改。
//採用廣義表格式，元素類型為int
voidPrintBTree_int(structBTreeNode*BT)
{
if(BT!=NULL)
{
printf("%d",BT->data);//輸出根結點的值
if(BT->left!=NULL||BT->right!=NULL)
{
printf("(");
PrintBTree_int(BT->left);//輸出左子樹
if(BT->right!=NULL)
printf(",");
PrintBTree_int(BT->right);//輸出右子樹
printf(")");
}
}
}

//2、根據數組a中n個權值建立一棵哈夫曼樹，返回樹根指針
structBTreeNode*CreateHuffman(ElemTypea[],intn)
{
inti,j;
structBTreeNode**b,*q;
b=malloc(n*sizeof(structBTreeNode));
//初始化b指針數組，使每個指針元素指向a數組中對應的元素結點
for(i=0;i<n;i++)
{
b[i]=malloc(sizeof(structBTreeNode));
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1;i<n;i++)//進行n-1次循環建立哈夫曼樹
{
//k1表示森林中具有最小權值的樹根結點的下標，k2為次最小的下標
intk1=-1,k2;
//讓k1初始指向森林中第一棵樹，k2指向第二棵
for(j=0;j<n;j++)
{
if(b[j]!=NULL&&k1==-1)
{
k1=j;
continue;
}
if(b[j]!=NULL)
{
k2=j;
break;
}
}
//從當前森林中求出最小權值樹和次最小
for(j=k2;j<n;j++)
{
if(b[j]!=NULL)
{
if(b[j]->data<b[k1]->data)
{
k2=k1;
k1=j;
}
elseif(b[j]->data<b[k2]->data)
k2=j;
}
}
//由最小權值樹和次最小權值樹建立一棵新樹，q指向樹根結點
q=malloc(sizeof(structBTreeNode));
q->data=b[k1]->data+b[k2]->data;
q->left=b[k1];
q->right=b[k2];

b[k1]=q;//將指向新樹的指針賦給b指針數組中k1位置
b[k2]=NULL;//k2位置為空
}
free(b);//刪除動態建立的數組b
returnq;//返回整個哈夫曼樹的樹根指針
}

//3、求哈夫曼樹的帶權路徑長度
ElemTypeWeightPathLength(structBTreeNode*FBT,intlen)//len初始為0
{
if(FBT==NULL)//空樹返回0
return0;
else
{
if(FBT->left==NULL&&FBT->right==NULL)//訪問到葉子結點
{
printf("+%d*%d",FBT->data,len);
returnFBT->data*len;
}
else//訪問到非葉子結點，進行遞歸調用，
{//返回左右子樹的帶權路徑長度之和，len遞增
returnWeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}

//4、哈夫曼編碼（可以根據哈夫曼樹帶權路徑長度的演算法基礎上進行修改）
voidHuffManCoding(structBTreeNode*FBT,intlen)//len初始值為0
{
//定義靜態數組a，保存每個葉子的編碼，數組長度至少是樹深度減一
staticinta[10];
inti;
//訪問到葉子結點時輸出其保存在數組a中的0和1序列編碼
if(FBT!=NULL)
{
if(FBT->left==NULL&&FBT->right==NULL)
{
printf("權值為%d的編碼：",FBT->data);
for(i=0;i<len;i++)
printf("%d",a[i]);
printf("
");
}
else//訪問到非葉子結點時分別向左右子樹遞歸調用，
{//並把分支上的0、1編碼保存到數組a的對應元素中，
//向下深入一層時len值增1
a[len]=0;
HuffManCoding(FBT->left,len+1);
a[len]=1;
HuffManCoding(FBT->right,len+1);
}
}
}

intmain()
{
intn,i;
ElemType*a;
structBTreeNode*fbt;
printf("輸入構造哈夫曼樹中帶權葉子結點數(n)：");
while(1)
{
scanf("%d",&n);
if(n>1)
break;
else
printf("重輸n值：");
}
a=malloc(n*sizeof(ElemType));
printf("輸入%d個整數作為權值：",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
fbt=CreateHuffman(a,n);
printf("廣義表形式的哈夫曼樹：");
PrintBTree_int(fbt);
printf("
");
printf("哈夫曼樹的帶權路徑長度：
");
printf("=");
printf("
=%d
",WeightPathLength(fbt,0));
printf("樹中每個葉子結點的哈夫曼編碼：
");
HuffManCoding(fbt,0);

return0;
}

⑷ 哈夫曼樹

轉自： http://blog.csdn.net/hikvision_java_gyh/article/details/8952596
哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的帶權路徑長度記為WPL=(W1 L1+W2 L2+W3 L3+...+ Wn Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。【例】給定4個葉子結點a，b，c和d，分別帶權7，5，2和4。構造如下圖所示的三棵二叉樹(還有許多棵)，它們的帶權路徑長度分別為: (a)WPL=7 2+5 2+2 2+4 2=36 (b)WPL=7 3+5 3+2 1+4 2=46 (c)WPL=7 1+5 2+2 3+4 3=35其中(c)樹的WPL最小，可以驗證，它就是哈夫曼樹。

構造哈夫曼樹的演算法如下： 1）對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。 2）在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。 3）從F中刪除這兩棵樹，並把這棵新的二叉樹同樣以升序排列加入到集合F中。 4）重復2）和3），直到集合F中只有一棵二叉樹為止。 例如，對於4個權值為1、3、5、7的節點構造一棵哈夫曼樹，其構造過程如下圖所示：

可以計算得到該哈夫曼樹的路徑長度WPL＝(1+3) 3+2 5+1*7=26。
哈夫曼編碼應用 大數據 量的圖像信息會給存儲器的存儲容量，通信干線信道的帶寬，以及計算機的處理速度增加極大的壓力。單純靠增加存儲器容量，提高信道帶寬以及計算機的處理速度等方法來解決這個問題是不現實的，這時就要考慮壓縮。壓縮的關鍵在於編碼，如果在對數據進行編碼時，對於常見的數據，編碼器輸出較短的碼字；而對於少見的數據則用較長的碼字表示，就能夠實現壓縮。【例】：假設一個文件中出現了8種符號S0，SQ，S2，S3，S4，S5，S6，S7，那麼每種符號要編碼，至少需要3bit。假設編碼成 000，001， 010，011，100，101，110，111。那麼符號序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼後變成 ，共用了42bit。我們發現S0，S1，S2這3個符號出現的頻率比較大，其它符號出現的頻率比較小，我們採用這樣的編碼方案：S0到S7的碼遼分別01，11，101，0000，0001，0010，0011， 100，那麼上述符號序列變成，共用了39bit。盡管有些碼字如 S3，S4，S5，S6變長了(由3位變成4位)，但使用頻繁的幾個碼字如S0，S1變短了，所以實現了壓縮。對於上述的編碼可能導致解碼出現非單值性：比如說，如果S0的碼字為01，S2的碼字為011，那麼當序列中出現011時，你不知道是S0的碼字後面跟了個1，還是完整的一個S2的碼字。因此，編碼必須保證較短的編碼決不能是較長編碼的前綴。符合這種要求的編碼稱之為前綴編碼。要構造符合這樣的二進制編碼體系，可以通過二叉樹來實現。以下是哈夫曼樹的 Java 實現：
[java] view plain

// 二叉樹節點
public class Node implements Comparable { private int value; private Node leftChild; private Node rightChild; public Node(int value) { this.value = value; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Node getLeftChild() { return leftChild; } public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } public Node getRightChild() { return rightChild; } public void setRightChild(Node rightChild) { this.rightChild = rightChild; } public int compareTo(Object o) { Node that = (Node) o; double result = this.value - that.value; return result > 0 ? 1 : result == 0 ? 0 : -1; } }

private static Node build(List<Node> nodes) {
nodes = new ArrayList<Node>(nodes);
sortList(nodes);
while (nodes.size() > 1) {
createAndReplace(nodes);
}
return nodes.get(0);
}

/**

/**

private static void sortList(List<Node> nodes) {
Collections.sort(nodes);
}

`
/**

⑸ 兩道題，求詳細過程，講解的。

首先聲明，我沒學過數據結構，以下專業術語不正確的或者做錯了那麼。。。請自己翻書查相關的准確術語
nk=(k-1)n0+1
如果nk成為父節點有nk個，n0成為子節點有n0個。對於k叉樹而言，每當一個子節點拓展為一個父節點時，則子節點變為父節點即ak+=1同時a0-=1，同時子節點又多了k個即an+=k，兩式子聯立得每拓展一次時
ak+=1 a0+=k-1
又因為樹的根節點是沒有父親的，所以n0要再加1
就得到上面的關系了。

自己畫畫圖就出來了

第二題
樹的形狀如下圖
○
○ 8
○ 7
○ 4
○ 3
1 2
中間的線不知道怎麼畫，就是A的子女分別是B和8，B的子女分別是C和7，下同，最後的E的子女是1和2
WPL演算法 1*5+2*5+3*4+4*3+7*2+8*1 答案自己算（如果所有的路徑的權都是1的話。。）

哈弗曼數演算法如下
霍夫曼演算法
（1）由給定的n個權值構造具有n棵擴充二叉樹的森林F，其中每一棵擴充二叉樹只有一個帶有權值的根結點；
（2）在F中選取兩棵根結點的權值最小的擴充二叉樹作為左、右子樹構造一棵新的二叉樹，置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值的之和。在F中刪去這兩棵二叉樹，把新的二叉樹加入F；
（3）重復步驟（2）直到F中僅剩下一棵樹為止。

反正簡單的理解就是說越是小的數越是放下面，然後每個根節點下面就放一個帶有權的數，另一個當然就是根節點了，然後小的放下面，大的放上面，所謂WPL就是根節點到葉節點有幾條路徑，簡單來說就是幾條線，再乘以那個葉節點上的權值，然後都加起來就可以了。哈弗曼演算法是這樣的，怎麼證明的忘記了。。。

⑹ java 題目 最好有簡短的思路 謝謝

數據結構題，和java木有啥關系的。

⑺ 哈夫曼演算法簡介

看官們建議在看我的這篇文章之前，先看一下RlE演算法  這個是計算機壓縮演算法的入門級，如果連這個演算法的思想都不清楚的，請私聊我，單獨講解

簡單說一下rle=字元乘以重復數量

舉個例子，aaaaaabbbbbb的rlu就是a6b6

說回哈夫曼演算法

第一  統計每個字元出現的次數

第二  將出現次數最少的字元連線並求數量和

第三  重復第二步完成哈夫曼樹

第四  將哈夫曼樹的左邊的邊寫上0，右邊的邊也寫上  1 

第五  從根節點開始沿著邊去將數字寫在對應的字元下面

這樣一個哈夫曼編碼就完成了

#include <iostream>

#include <iomanip>

using namespace std;

//哈夫曼樹的存儲表示

typedef struct

{

    int weight;    // 權值

    int parent, lChild, rChild;    // 雙親及左右孩子的下標

}HTNode, *HuffmanTree;

// 選擇權值最小的兩顆樹

void SelectMin(HuffmanTree hT, int n, int &s1, int &s2)

{

    s1 = s2 = 0;

    int i;

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

        if(0 == hT[i].parent){

            if(0 == s1){

                s1 = i;

            }

            else{

                s2 = i;

                break;

            }

        }

    }

    if(hT[s1].weight > hT[s2].weight){

        int t = s1;

        s1 = s2;

        s2 = t;

    }

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

        if(0 == hT[i].parent){

            if(hT[i].weight < hT[s1].weight){

                s2 = s1;

                s1 = i;

            }else if(hT[i].weight < hT[s2].weight){

                s2 = i;

            }

        }

    }

}

// 構造有n個權值（葉子節點）的哈夫曼樹

void CreateHufmanTree(HuffmanTree &hT)

{

    int n, m;

    cin >> n;

    m = 2*n - 1;

    hT = new HTNode[m + 1];    // 0號節點不使用

    for(int i = 1; i <= m; ++ i){

        hT[i].parent = hT[i].lChild = hT[i].rChild = 0;

    }

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

        cin >> hT[i].weight;    // 輸入權值

    }

    hT[0].weight = m;    // 用0號節點保存節點數量

    /****** 初始化完畢, 創建哈夫曼樹 ******/

    for(int i = n + 1; i <= m; ++ i){

        int s1, s2;

        SelectMin(hT, i, s1, s2);

        hT[s1].parent = hT[s2].parent = i;

        hT[i].lChild = s1; hT[i].rChild = s2;    // 作為新節點的孩子

        hT[i].weight = hT[s1].weight + hT[s2].weight;    // 新節點為左右孩子節點權值之和

    }

}

int HuffmanTreeWPL_(HuffmanTree hT, int i, int deepth)

{

    if(hT[i].lChild == 0 && hT[i].rChild == 0){

        return hT[i].weight * deepth;

    }

    else{

        return HuffmanTreeWPL_(hT, hT[i].lChild, deepth + 1) + HuffmanTreeWPL_(hT, hT[i].rChild, deepth + 1);

    }

}

// 計算WPL（帶權路徑長度）

int HuffmanTreeWPL(HuffmanTree hT)

{

    return HuffmanTreeWPL_(hT, hT[0].weight, 0);

}

// 輸出哈夫曼樹各節點的狀態

void Print(HuffmanTree hT)

{

    cout << "index weight parent lChild rChild" << endl;

    cout << left;    // 左對齊輸出

    for(int i = 1, m = hT[0].weight; i <= m; ++ i){

        cout << setw(5) << i << " ";

        cout << setw(6) << hT[i].weight << " ";

        cout << setw(6) << hT[i].parent << " ";

        cout << setw(6) << hT[i].lChild << " ";

        cout << setw(6) << hT[i].rChild << endl;

    }

}

// 銷毀哈夫曼樹

void DestoryHuffmanTree(HuffmanTree &hT)

{

    delete[] hT;

    hT = NULL;

}

int main()

{

    HuffmanTree hT;

    CreateHufmanTree(hT);

    Print(hT);

    cout << "WPL = " << HuffmanTreeWPL(hT) << endl;

    DestoryHuffmanTree(hT);

    return 0;

}

⑻ 用JAVA實現HUFFMAN演算法 1 HUFFMAN演算法原理 2 流程圖 3 用JAVA語言編寫代碼

import java.util.*;
class HuffmanCode{
String name;
double weight;
int lc,rc,pa;
public HuffmanCode(){
name="";
weight=0;
lc=-1;rc=-1;pa=-1;
}
}

public class Huffman {
HuffmanCode[] codes;
String[] huffstring;
StringBuffer buffer=new StringBuffer();
public Huffman(String s) {
for(int i=0;i<s.length();i++){
if(buffer.indexOf(s.substring(i,i+1))==-1){
buffer.append(s.charAt(i));
}
}
System.out.println("字母："+buffer);
huffstring=new String[buffer.length()];
codes=new HuffmanCode[2*buffer.length()-1];
for(int i=0;i<2*buffer.length()-1;i++)
codes[i]=new HuffmanCode();
for(int i=0;i<buffer.length();i++){
codes[i].name=buffer.substring(i,i+1);
codes[i].weight=haveNum(buffer.charAt(i),s);
}
getHuffstring();
getCode(2*buffer.length()-2,huffstring,"");
//for(int i=0;i<codes.length;i++){
// System.out.println(""+i+":"+codes[i].name+codes[i].weight+" "+codes[i].lc+" "+codes[i].rc+" "+codes[i].pa);
//}
for(int i=0;i<huffstring.length;i++){
System.out.println(codes[i].name+" code:"+huffstring[i]);
}
System.out.println("編碼："+getHuffmanCode(s));
System.out.println("平均碼長為："+getLength());
}
public double getLength(){
double n=0;
for(int i=0;i<buffer.length();i++){
n+=huffstring[i].length();
}
return n/buffer.length();
}
public String getHuffmanCode(String s){
StringBuffer buf=new StringBuffer();
for(int i=0;i<s.length();i++){
buf.append(getEachCode(s.substring(i,i+1)));
}
return buf.toString();
}
public String getEachCode(String name){
for(int i=0;i<buffer.length();i++){
if(name.equals(codes[i].name)){
return huffstring[i];
}
}
return "";
}
public void getCode(int n,String[] thecodes,String thebuffer){
if(n<thecodes.length){
thecodes[n]=thebuffer;
return;
}
getCode(codes[n].lc,thecodes,thebuffer+"0");
getCode(codes[n].rc,thecodes,thebuffer+"1");
}
public void getHuffstring(){
int[] twos={0,0};
for(int i=buffer.length();i<2*buffer.length()-1;i++){
twos=findLastTwo(0,i);
codes[i].lc=twos[0];
codes[i].rc=twos[1];
codes[i].weight=codes[twos[0]].weight+codes[twos[1]].weight;
}
}
public int[] findLastTwo(int start,int end){
double[] weights={1.0,1.0};
int[] t={-1,-1};
for(int i=start;i<end;i++){
if(codes[i].pa!=-1)continue;
if(weights[0]>codes[i].weight){
weights[0]=codes[i].weight;
t[1]=t[0];
t[0]=i;
}
else if(weights[1]>codes[i].weight){
weights[1]=codes[i].weight;
t[1]=i;
}
}
codes[t[0]].pa=end;
codes[t[1]].pa=end;
return t;
}
public double haveNum(char c,String s){
double n=0;
for(int i=0;i<s.length();i++){
if(c==s.charAt(i))n++;
}
return n/s.length();
}
public static void main (String[] args) {
System.out.print("輸入編碼字元串：");
Scanner sr=new Scanner(System.in);
new Huffman(sr.nextLine());
}
}

⑼ 數據結構題、大哥大姐幫我做下題吧。萬分感謝啊

什麼是數據、數據對象、數據元素、數據結構、數據的邏輯結構與物理結構、邏輯結構與物理結構間的關系。
2、面向對象概念：理解什麼是數據類型、抽象數據類型、數據抽象和信息隱蔽原則。了解什麼是面向對象。由於目前關於這個問題有許多說法，我們採用了一種最流行的說法，即Coad與Yourdon 給出的定義：面向對象 = 對象 + 類 + 繼承 + 通信。
要點：
·抽象數據類型的封裝性
·面向對象系統結構的穩定性
·面向對象方法著眼點在於應用問題所涉及的對象
3、數據結構的抽象層次：理解用對象類表示的各種數據結構
4、演算法與演算法分析：理解演算法的定義、演算法的特性、演算法的時間代價、演算法的空間代價。
要點：·演算法與程序的不同之處需要從演算法的特性來解釋
·演算法的正確性是最主要的要求
·演算法的可讀性是必須考慮的
·程序的程序步數的計算與演算法的事前估計
·程序的時間代價是指演算法的漸進時間復雜性度量

第二章 數組
1、作為抽象數據類型的數組：數組的定義、數組的按行順序存儲與按列順序存儲
要點：
·數組元素的存放地址計算
2、順序表：順序表的定義、搜索、插入與刪除
要點：
·順序表搜索演算法、平均比較次數的計算
·插入與刪除演算法、平均移動次數的計算
3、多項式：多項式的定義
4、字元串：字元串的定義及其操作的實現
要點：
·串重載操作的定義與實現

第三章 鏈接表
1、單鏈表：單鏈表定義、相應操作的實現、單鏈表的游標類。
要點：
·單鏈表的兩種定義方式（復合方式與嵌套方式）
·單鏈表的搜索演算法與插入、刪除演算法
·單鏈表的遞歸與迭代演算法
2、循環鏈表：單鏈表與循環鏈表的異同
3、雙向鏈表：雙向鏈表的搜索、插入與刪除演算法、鏈表帶表頭結點的優點
4、多項式的鏈接表示

第四章 棧與隊列
1、棧：棧的特性、棧的基本運算
要點：
·棧的數組實現、棧的鏈表實現
·棧滿及棧空條件、抽象數據類型中的先決條件與後置條件
2、棧的應用：用後綴表示計算表達式，中綴表示改後綴表示
3、隊列：隊列的特性、隊列的基本運算
要點：
·隊列的數組實現：循環隊列中隊頭與隊尾指針的表示，隊滿及隊空條件
·隊列的鏈表實現：鏈式隊列中的隊頭與隊尾指針的表示、
4、雙向隊列：雙向隊列的插入與刪除演算法
5、優先順序隊列：優先順序隊列的插入與刪除演算法

第五章 遞歸與廣義表
1、遞歸：遞歸的定義、遞歸的數據結構、遞歸問題用遞歸過程求解
要點：·鏈表是遞歸的數據結構，可用遞歸過程求解有關鏈表的問題
2、遞歸實現時棧的應用
要點：·遞歸的分層（樹形）表示：遞歸樹
·遞歸深度（遞歸樹的深度）與遞歸工作棧的關系
·單向遞歸與尾遞歸的迭代實現
3、廣義表：廣義表定義、廣義表長度、廣義表深度、廣義表表頭、廣義表表尾
要點：
·用圖形表示廣義表的存儲結構
·廣義表的遞歸演算法

第六章 樹與森林
1、樹：樹的定義、樹的基本運算
要點：
·樹的分層定義是遞歸的
·樹中結點個數與高度的關系
2、二叉樹：二叉樹定義、二叉樹的基本運算
要點：
·二叉樹性質、二叉樹中結點個數與高度的關系、不同種類的二叉樹棵數
·完全二叉樹的順序存儲、完全二叉樹的雙親、子女和兄弟的位置
·二叉樹的前序·中序·後序·層次遍歷
·前序
·中序
·後序的線索化二叉樹、前驅與後繼的查找方法
3、霍夫曼樹：霍夫曼樹的構造方法、霍夫曼編碼、帶權路徑長度的計算
4、樹的存儲：樹的廣義表表示、樹的雙親表示、樹與二叉樹的對應關系、樹的先根·中根·後根·層次遍歷。
5、堆：堆的定義、堆的插入與刪除演算法
要點：
·形成堆時用到的向下調整演算法及形成堆時比較次數的上界估計
·堆插入時用到的向上調整演算法

第七章 集合與搜索
1、集合的概念：集合的基本運算、集合的存儲表示
要點：
·用位數組表示集合時集合基本運算的實現
·用有序鏈表表示集合時集合基本運算的實現
2、並查集：並查集定義、並查集的三種基本運算的實現
3、基本搜索方法
要點：
·對一般表的順序搜索演算法（包括有監視哨和沒有監視哨）
·對有序順序表的順序搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
·對有序順序表的折半搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
4、二叉搜索樹：
要點：
·動態搜索樹與靜態搜索樹的特性
·二叉搜索樹的定義、二叉搜索樹上的搜索演算法、二叉搜索樹搜索時的平均搜索長度（成功與不成功）的計算。
·AVL樹結點上的平衡因子、AVL樹的平衡旋轉方法
·高度為h的AVL樹上的最少結點個數與最多結點個數
· AVL樹的搜索方法、插入與刪除方法

第八章 圖
1、圖：圖的定義與圖的存儲表示
要點：
·鄰接矩陣表示（通常是稀疏矩陣）
·鄰接表與逆鄰接表表示
·鄰接多重表(十字鏈表)表示
2、深度優先遍歷與廣度優先遍歷
要點：
·生成樹與生成樹林的定義
·深度優先搜索是個遞歸的過程，而廣度優先搜索是個非遞歸的過程
·為防止重復訪問已經訪問過的頂點，需要設置一個訪問標志數組visited
3、圖的連通性
要點：
·深度優先搜索可以遍歷一個連通分量上的所有頂點
·對非連通圖進行遍歷，可以建立一個生成森林
·對強連通圖進行遍歷，可能建立一個生成森林
·關節點的計算和以最少的邊構成重連通圖
4、最小生成樹
要點：
·對於連通網路、可用不會構成環路的權值最小的n-1條邊構成最小生成樹
·會畫出用Kruskal演算法及Prim演算法構造最小生成樹的過程
5、單源最短路徑
要點：
·採用逐步求解的方式求某一頂點到其他頂點的最短路徑
·要求每條邊的權值必須大於零
6、活動網路
要點：
·拓撲排序、關鍵路徑、關鍵活動、AOE網
·拓撲排序將一個偏序圖轉化為一個全序圖。
·為實現拓撲排序，要建立一個棧，將所有入度為零的頂點進棧
·關鍵路徑的計算

第九章 排序
1、基本概念：關鍵碼、初始關鍵碼排列、關鍵碼比較次數、數據移動次數、穩定性、附加存儲、內部排序、外部排序
2、插入排序：
要點：
·當待排序的關鍵碼序列已經基本有序時，用直接插入排序最快
3、選擇排序：
要點：
·用直接選擇排序在一個待排序區間中選出最小的數據時，與區間第一個數據對調，而不是順次後移。這導致方法不穩定。
·當在n個數據（n很大）中選出最小的5 ~ 8個數據時，錦標賽排序最快
·錦標賽排序的演算法中將待排序的數據個數n補足到2的k次冪2k-1<n≤2k
·在堆排序中將待排序的數據組織成完全二叉樹的順序存儲。
4、交換排序：
要點：
·快速排序是一個遞歸的排序方法
·當待排序關鍵碼序列已經基本有序時，快速排序顯著變慢。
5、二路歸並排序：
要點：
·歸並排序可以遞歸執行
·歸並排序需要較多的附加存儲。可以採用一種"推拉法"（參見教科書上習題）實現歸並排序，演算法的時間復雜度為O (n)、空間復雜度為O(1)
·歸並排序對待排序關鍵碼的初始排列不敏感，排序速度較穩定
6、外排序
要點：
·多路平衡歸並排序的過程、I/O緩沖區個數的配置
·外排序的時間分析、利用敗者樹進行多路平衡歸並
·利用置換選擇方法生成不等長的初始歸並段
·最佳歸並樹的構造及WPL的計算

第十章 索引與散列
1、線性索引：
要點：
·密集索引、稀疏索引、索引表計算
·基於屬性查找建立倒排索引、單元式倒排表
2、動態搜索樹
要點：
·平衡的m路搜索樹的定義、搜索演算法
·B樹的定義、B樹與平衡的m路搜索樹的關系
·B樹的插入（包括結點分裂）、刪除（包括結點調整與合並）方法
·B樹中結點個數與高度的關系
·B+樹的定義、搜索、插入與刪除的方法
3、散列表
要點：
·散列函數的比較
·裝填因子 a 與平均搜索長度的關系，平均搜索長度與表長m及表中已有數據對象個數n的關系
·解決地址沖突的（閉散列）線性探查法的運用，平均探查次數的計算
·線性探查法的刪除問題、散列表類的設計中必須為各地址設置三個狀態
·線性探查法中的聚集問題
·解決地址沖突的（閉散列）雙散列法的運用，平均探查次數的計算
·雙散列法中再散列函數的設計要求與表長m互質，為此m設計為質數較宜
·解決地址沖突的（閉散列）二次散列法的運用，平均探查次數的計算
·注意：二次散列法中裝填因子 a 與表長m的設置
·解決地址沖突的（開散列）鏈地址法的運用，平均探查次數的計算

⑽ 求助有關哈夫曼樹的問題！急！滿意的答案再加!

哈夫曼樹
一、 基本術語
1. 路徑與路徑長度
若在一棵樹中存在一個結點序列 k1, k2, …., kj ，使得kj是kj+1的雙親（1<=i<j），則稱結點序列是從k1到kj 的路徑（如樹中的某個結點到它的某個祖先，或者到它的某個後代的的包括它本身的一系列按順序的結點序列稱為路徑），因樹中的每個結點只有一個雙親結點，所以這是兩個結點間的唯一路徑，從k1到kj 所經過的分支數稱為這兩點之間的路徑長度。它等於結點數-1。
如： 從結點A到結點J的結點序
列為A，B，E，J。
路徑長度為3。

8 10

4 5 3
2. 結點的權和帶權路徑長度
如果根據需要給樹中的結點賦予一個有某中意義的實數，則稱此實數為該結點的權，結點帶權路徑長度規定為從樹根結點到該結點之間的路徑長度乘上該結點的權值所得到的乘積。
3. 樹的帶權路徑長度
樹的帶權路徑長度定義為樹中所有葉結點的帶權路徑長度之和，通常記為：
n
WPL=∑ wili wi和li 分別代表葉結點ki的權值和ki到
i=1 根結點的路徑長度
例如：上圖的WPL=（4+5+3）*3+（8+10）*2=72
4. 哈夫曼樹
哈夫曼樹又稱為最優二叉樹，它是由n個帶權葉結點構成的所有二叉樹中帶權路徑長度WPL最小的二叉樹。
例如：有四個葉結點a，b，c，d，分別帶權為9，4，5，2，可以構成三棵不同的二叉樹（當然可以構成更多的二叉樹）見下圖：

9 4 5 2 WPL=（9+4+5+2）*2=40

4

2

5 9
WPL=（9+5）*3+2*2+4*1=50

4

2

5 9
WPL=（9+5）*3+2*2+4*1=50

9

5

4 2
WPL=9*1+5*2+（2+4）*3=37
可以證明最後一棵二叉樹是哈夫曼樹。
二、 構造哈夫曼樹
1. 將n個葉結點構成獨立的n棵二叉樹，每棵二叉樹只有一個根結點。
2. 選擇兩棵權值最小的二叉樹合並成一棵二叉樹，並以這兩棵二叉樹的權值之和作為這棵二叉樹的權值，取消原來的兩棵二叉樹。
3. 重復2，知道只剩一棵二叉樹為止。
例如：有6個帶權葉結點的權值分別為：3，6，8，5，2，2，構造一棵哈夫曼樹，並計算WPL的結果。
1.構造6棵二叉樹

3 6 8 5 2 2
2選出兩個權值最小的二叉樹的組成一棵二叉樹

2 2 合並權值為4

3 6 8 5
3 6 8 5 4
2 2
選出兩個權值最小的二叉樹的組成一棵二叉樹

7 6 8 5

3

2 2
選出兩個權值最小的二叉樹的組成一棵二叉樹

7 11 8

3
5 6
2 2
選出兩個權值最小的二叉樹的組成一棵二叉樹

15 11

8
5 6
3

2 2

選出兩個權值最小的二叉樹的組成一棵二叉樹（最終的哈夫曼樹）

8
5 6
3

2 2
WPL=（2+2）*4+3*3+（5+6+8）*2=16+9+38=63
作業：P221/9