У моего дерева Хаффмана, о котором я спрашивал ранее, есть еще одна проблема!Вот код:
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());
}
}
}
Теперь мне нужно создать метод, который будет искать в дереве, чтобы найти двоичный код (011001 и т. Д.) Для конкретного символа.Каков наилучший способ сделать это?Я подумал, что, возможно, я бы сделал обычный поиск по дереву, как если бы это было дерево AVL, идущее вправо, если оно больше, или влево, если оно меньше.
Но поскольку узлы не используют двойные числа типа int и т. Д., А используют только объекты, содержащие символы в виде строк или ноль, для обозначения не листа, а только корня.Другой вариант - сделать пробежку по порядку, чтобы найти лист, который я ищу, и в то же время, как я могу определить, много раз я ушел вправо или столько раз ушел, чтобы получить персонажа.
package huffman;
public class Frequency implements Comparable {
private String s;
private int n;
public Frequency left;
public Frequency right;
Frequency(String s, int n)
{
this.s = s;
this.n = n;
}
public String getString()
{
return s;
}
public int getFreq()
{
return n;
}
public void setFreq(int n)
{
this.n = n;
}
@Override
public int compareTo(Object arg0) {
Frequency other = (Frequency)arg0;
return n < other.n ? -1 : (n == other.n ? 0 : 1);
}
}
Я пытаюсь найти двоичный код, чтобы получить каждый символ.Так что, если бы я пытался закодировать aabbbcccc, как бы я создал строку, содержащую двоичный код для перехода влево - 0, а перехода вправо - 1.
Что меня смущает, так это то, что вы не можете определить гдевсе потому, что дерево явно не сбалансировано, и нет никакого определения, находится ли персонаж справа или слева от того места, где вы находитесь.Таким образом, вы должны искать по всему дереву, но если вы доберетесь до узла, который не является тем, что вы ищете, вы должны вернуться к другому корню, чтобы добраться до других листьев.