構建哈夫曼樹

我一直對這個哈夫曼樹構建器：構建哈夫曼樹

// variable al is an array list that holds all the different characters and their frequencies 
// variable r is a Frequency which is supposed to be the roots for all the leaves which holds a null string and the frequencies of the combined nodes removed from the priority queue 
public Frequency buildTree(ArrayList<Frequency> al) 
{ 
    Frequency r = al.get(0); 
    PriorityQueue<Frequency> pq = new PriorityQueue<Frequency>(); 
    for(int i = 0; i < al.size(); i++) 
    { 
     pq.add(al.get(i));   
    } 
    /*while(pq.size() > 0) 
    { 
     System.out.println(pq.remove().getString()); 
    }*/ 

    for(int i = 0; i < al.size() - 1; i++) 
    { 
     Frequency p = pq.remove(); 
     Frequency q = pq.remove(); 
     int temp = p.getFreq() + q.getFreq(); 
     r = new Frequency(null, temp); 
     r.left = p; 
     r.right = q; 
     pq.add(r); // put in the correct place in the priority queue 
    } 
    pq.remove(); // leave the priority queue empty 
    return(r); // this is the root of the tree built 

}

什麼代碼試圖做英語是

與它們的頻率從添加的所有字符的優先級隊列最低頻率最高。接下來是ArrayList al的大小（其中包含所有字符）將第一個兩個字符出列，然後設置一個新的根目錄，讓左右兩個子節點出列，然後插入新組合的頻率爲2的新根將項目出隊列入優先隊列。那所有的方法都應該這樣做。

這種方法應該是建立霍夫曼樹，但它構建得不正確我遵循代碼並手工構建樹，但是我在紙上得到的結果與程序不同！由不同程序生成的正確答案與我的解決方案不同。輸入數據（信件和頻率）是：

a 6 
b 5 
space 5 
c 4 
d 3 
e 2 
f 1

作爲該即時閱讀，從它並不重要，因爲頻率已經在這裏的文字。我所需要的2是從這些頻率構建樹。

來源

2010-07-23 Zieklecknerizer

大概需要看到Frequency'的'的定義以及 – barrowc 2010-07-23 00:38:38

的'定義Frequency'似乎是在您的其他問題：http://stackoverflow.com/questions/3311432/huffman-tree-encodeing – barrowc 2010-07-23 00:41:13

何時到期？我會開始爲您的實現的每個功能位編寫單元測試 - 您可能能夠以這種方式公開您的問題。也固定格式設置爲這種混亂

「公共頻率buildTree（ArrayList的人）{頻率R = al.get（1）; PQ的PriorityQueue =新的PriorityQueue（）;對（INT I = 0;我<人size（）; i ++）{pq.add（al.get（i））; }/while（pq.size（）> 0）{System.out.println（pq.remove（）。getString（））; 「/」

edit-格式化後 - 我很難讀取你的代碼。使變量名稱具有描述性。 'r'不會告訴我任何事情，'al'也不會。這將有助於知道你正在編碼的文字是什麼......

來源

2010-07-23 00:22:59 hvgotcodes

你可以嘗試用簡單的語言寫出你的算法，忽略任何Java細節？這可以幫助您瞭解哪裏出了問題（無論是在算法中還是在實現它的代碼中），還可以幫助人們幫助您。

無論算法如何，您是否真的打算讓您的根節點以ArrayList中的第二個元素開頭？ List s從0開始索引，而不是1. List.get(1)返回第二個元素。

public Frequency buildTree(ArrayList<Frequency> al) { 
    Frequency r = al.get(1);

來源

2010-07-23 01:50:03

構建哈夫曼樹

回答

相關問題