Huffman-Tree-Codierung

Meine Huffman-Baum, die ich gebeten hatte, über früher hat ein anderes problem! Hier ist der code:

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());
        }
    }

}

Was getan werden muss, jetzt muss ich eine Methode erstellen, wird die Suche durch den Baum zu finden, den binären code (011001 etc), um den besonderen Charakter. Was ist der beste Weg, dies zu tun? Vielleicht dachte ich, ich würde eine normale Suche durch den Baum, als wäre er ein AVL-Baum gehen, um den richtigen, wenn Ihr größer oder Links, wenn es kleiner ist.

Aber da die Knoten nicht verwenden, ints verdoppelt usw. aber nur mit Objekten, die Zeichen enthalten, die als String oder null, um zu signalisieren Ihr nicht ein Blatt, sondern nur eine Wurzel. Die andere option wäre eine in-order Durchlaufen, um das Blatt, die ich Suche, aber zur gleichen Zeit, wie würde ich feststellen, ob ich nach rechts Gefahren so viele Male oder Links, so viele Male, um den Charakter.

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);
    }
}

Was ich versuche zu tun ist, suchen Sie der binäre code, um tatsächlich zu jedem Charakter. Also, wenn ich versuchen zu codieren aabbbcccc wie würde ich einen string enthält den Binärcode für einen nach Links ist 0 und rechts 1.

Was mich verwirrt ist, weil man nicht feststellen kann, wo etwas ist, da der Baum offensichtlich unausgewogen und es gibt keine Bestimmung, ob ein Zeichen nach rechts oder Links ab, wo Sie sind. So haben Sie zum durchsuchen des gesamten Baumes, aber wenn Sie sich zu einem Knoten, das ist nicht, was Sie suchen, haben Sie backtrack auf einen anderen root zu bekommen auf die anderen Blätter.

InformationsquelleAutor Zieklecknerizer | 2010-07-22