java - 霍夫曼树编码

我之前问过的霍夫曼树还有另一个问题！这是代码：

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树，如果树较大则向右移动，如果树较小则向左移动。

但是，因为节点不使用整数双精度等，而是仅使用包含字符作为字符串或null的对象来表示其不是叶子，而是仅表示根。另一种选择是进行顺序查找以找到我要寻找的叶子，但与此同时，我将如何确定我是走了很多次还是走了很多次才能得到角色。

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。

我感到困惑的是，因为树无法平衡，您无法确定任何位置，也无法确定角色在您所在位置的右边还是左边。因此，您必须搜索整个树，但是如果到达的节点不是您要查找的节点，则必须回溯到另一个根节点才能到达另一个叶子。

最佳答案

遍历霍夫曼树节点以获取类似{'a'：“ 1001”，'b'：“ 10001”}等的映射。您可以使用此映射将二进制代码获取到特定字符。

如果需要反向操作，只需将其作为状态机处理即可：

state = huffman_root
for each bit
    if (state.type == 'leaf')
        output(state.data);
        state = huffman_root
    state = state.leaves[bit]

老实说，我没有调查您的代码。花式树怎么办应该很明显。