Mon arbre Huffman que j'avais demandé plus tôt a un autre problème! Voici le code:Huffman Tree Encodage
package huffman;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Huffman {
public ArrayList<Frequency> fileReader(String file)
{
ArrayList<Frequency> al = new ArrayList<Frequency>();
Scanner s;
try {
s = new Scanner(new FileReader(file)).useDelimiter("");
while (s.hasNext())
{
boolean found = false;
int i = 0;
String temp = s.next();
while(!found)
{
if(al.size() == i && !found)
{
found = true;
al.add(new Frequency(temp, 1));
}
else if(temp.equals(al.get(i).getString()))
{
int tempNum = al.get(i).getFreq() + 1;
al.get(i).setFreq(tempNum);
found = true;
}
i++;
}
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return al;
}
public Frequency buildTree(ArrayList<Frequency> al)
{
Frequency r = al.get(1);
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
}
public void inOrder(Frequency top)
{
if(top == null)
{
return;
}
else
{
inOrder(top.left);
System.out.print(top.getString() +", ");
inOrder(top.right);
return;
}
}
public void printFreq(ArrayList<Frequency> al)
{
for(int i = 0; i < al.size(); i++)
{
System.out.println(al.get(i).getString() + "; " + al.get(i).getFreq());
}
}
}
Ce qui doit être fait est maintenant je dois créer une méthode qui recherche dans l'arborescence pour trouver le code binaire (011001, etc.) au caractère spécifique. Quelle est la meilleure façon de procéder? Je pensais que je ferais peut-être une recherche normale à travers l'arbre comme si c'était un arbre AVL allant vers la droite s'il était plus grand ou à gauche s'il était plus petit.
Mais parce que les nœuds n'utilisent pas ints doubles etc. mais seulement en utilisant des objets qui contiennent des caractères comme des chaînes ou null pour signifier que ce n'est pas une feuille mais seulement une racine. L'autre option serait de faire une recherche en cours pour trouver la feuille que je cherche, mais en même temps, comment pourrais-je déterminer si je suis allé droit autant de fois ou à gauche tant de fois pour obtenir le personnage. Ce que j'essaie de faire est de trouver le code binaire pour arriver à chaque caractère. C'est ce que j'essaie de faire. Donc, si j'essayais de coder aabbbcccc comment je créer une chaîne contenant le code binaire pour un aller à gauche est 0 et aller à droite est 1.
Ce qui m'a confondu est parce que vous ne pouvez pas déterminer où est quelque chose parce que le l'arbre est évidemment déséquilibré et il n'y a pas de déterminant si un personnage est à droite ou à gauche de l'endroit où vous êtes. Vous devez donc effectuer une recherche dans l'ensemble de l'arborescence, mais si vous arrivez à un nœud qui n'est pas ce que vous recherchez, vous devez revenir à une autre racine pour accéder aux autres feuilles.
si l'im objet à l'aide devrait avoir une clé contenant le code binaire pour elle? donc je peux juste accéder directement à partir de l'objet que je cherche? – Zieklecknerizer
Attendez une seconde, je vais jeter un coup d'oeil à votre programme et voir si je peux offrir un aperçu. Cela ressemble étrangement à des devoirs - si c'est vous devriez ajouter l'étiquette de devoir. :) – corsiKa
ouais c'est HW suppose que je devrais alors haha – Zieklecknerizer