Построение дерева Хаффмана - PullRequest
Новая
       29

Построение дерева Хаффмана

2 голосов
/ 23 июля 2010

Я работал над этим конструктором деревьев Хаффмана: 

// 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 (который содержит все символы) удалите из очереди первые два, затем установите новый корень, чтобы иметь левого и правого дочернего элемента, которые являются удаленными из двух узлов, затем вставьте новый корень с объединенными частотами из двух удаленных из очереди элементы в очереди приоритетов. вот и все, что должен делать метод.

Предполагается, что этот метод создает дерево Хаффмана, но он строит его неправильно. Я следовал коду и создал дерево вручную, но то, что я получаю на бумаге, отличается от того, что представляет собой программа! Правильный ответ, сгенерированный другой программой, не совпадает с моим решением. Входные данные (буквы и частоты): 

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

что касается текста, который я читаю, он не имеет значения, потому что частоты уже здесь. все, что мне нужно сделать 2, это построить дерево из этих частот.

Ответы [ 2 ]

2 голосов
/ 23 июля 2010

Можете ли вы попытаться записать свой алгоритм простым языком, игнорируя какие-либо детали Java? Это может помочь вам понять, где что-то идет не так (в алгоритме или в коде, его реализующем), но также поможет людям помочь вам.

Независимо от алгоритма, действительно ли вы хотите, чтобы ваш корневой узел начинался со второго элемента в ArrayList? List s индексируются начиная с 0, а не 1. List.get(1) возвращает второй элемент. 

public Frequency buildTree(ArrayList<Frequency> al) {
    Frequency r = al.get(1);
0 голосов
/ 23 июля 2010

когда это должно быть?Я бы начал писать модульные тесты для каждого функционального бита вашей реализации - вы могли бы раскрыть вашу проблему таким образом.Также исправьте ваше форматирование для этого беспорядка.size (); i ++) {pq.add (al.get (i));} / while (pq.size ()> 0) {System.out.println (pq.remove (). getString ());} / "

edit- после форматирования - мне трудно читать ваш код.Сделайте имена переменных описательными.«r» ничего не говорит мне, и «al» тоже не говорит.Было бы полезно узнать, какой текст вы кодируете ....

...