java霍夫曼樹,Java哈夫曼樹

本文目錄一覽：

• 1、java如何實現動態顯示哈夫曼樹？意思就是顯示每次兩個葉子結合，最後組成了一顆樹的那個過程。求大神
• 2、已知字符集{a,b,c,d}的權值集合為{7,5,1,2},構造哈夫曼樹,並求出字符集的哈夫
• 3、到底什麼是哈夫曼樹啊，求例子
• 4、Java中Huffman問題
• 5、在java中能直接把BitSet的對象直接輸入到二進制文件中嗎,用哪個流啊？
• 6、霍夫曼樹一定是滿二叉樹嗎？

java如何實現動態顯示哈夫曼樹？意思就是顯示每次兩個葉子結合，最後組成了一顆樹的那個過程。求大神

根據二叉樹的性質：n2=n0-1，列方程組得｛n2=n0-1,n0+n2=199｝，解方程組得n0=100，所以葉子結點有100個。

已知字符集{a,b,c,d}的權值集合為{7,5,1,2},構造哈夫曼樹,並求出字符集的哈夫

在森林中選出兩個根結點的權值最小的樹合併，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；從森林中刪除選取的兩棵樹，並將新樹加入森林。

樹的路徑長度是從樹根到每一結點的路徑長度之和；

WPL=（W1*L1+W2*L2+W3*L3+…+Wn*Ln），N個權值Wi（i=1,2,…n）構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li（i=1,2,…n）。可以證明哈夫曼樹的WPL是最小的。

A-B合併（權5）

A-B再和C合併（權10）

D-E合併（權16）

（A-B）-C再和F合併（權21）

最後((A-B)-C)-F再和D-E合併（權37）

總之是找兩個最小的結點合併，生成的新節點權為兩個結點權之和。

平均路徑長度為（2×3+3×3+5×2+7×1+9×1+12×1）/6=53/6約等於8.8

各字符Huffman編碼可以為：A-0000 B-0001 C- 001 D-10 E-11 F-01

擴展資料：

假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：

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

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

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

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

參考資料來源：百度百科-哈夫曼樹

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

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

例子：

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

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

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

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

擴展資料：

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

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

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

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

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

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

參考資料來源:百度百科——哈夫曼樹

Java中Huffman問題

這題在實現層面變得和Huffman樹沒啥關係…

反覆取取最小值，使值成為優先級..用優先隊列最合適。。可自己把輸入方式補上

import java.util.Arrays;

import java.util.PriorityQueue;

public class Test {

   public static void main(String[] args){      

      Integer[] a= {5, 3, 8, 2, 9};

      PriorityQueueInteger q=new PriorityQueueInteger(Arrays.asList(a));

      int cost=0;

      while(q.size()1){

         System.out.println(q); //可刪

         int c=q.poll()+q.poll();

         q.offer(c); cost+=c;            

      }

      System.out.println(q); //可刪

      System.out.println(cost);      

   }

}

[2, 3, 8, 5, 9]

[5, 5, 8, 9]

[8, 9, 10]

[10, 17]

[27]

59

在java中能直接把BitSet的對象直接輸入到二進制文件中嗎,用哪個流啊？

package com.tuz;

import java.io.*;

public class MyTest {

public static void main(String[] args) {

String s = “010101”;

int i = Integer.parseInt(s, 2);//按照2進制提取為十進制

try {

DataOutputStream out=

new DataOutputStream(

new BufferedOutputStream(

new FileOutputStream(“Data”)));//Data是文件的名字

out.writeByte(i);

out.close();

} catch (FileNotFoundException e) {

e.printStackTrace();

} catch (IOException e) {

e.printStackTrace();

}

}

}

霍夫曼樹一定是滿二叉樹嗎？

不是。

滿二叉樹是所有分支都有左孩子右孩子結點，葉子結點在二叉樹最下一層。

霍夫曼樹是帶權路徑最短，也叫最優二叉樹。