java Huffman树输出错误

Question

这是我第一次使用stackoverflow提问，希望你们能帮我：）

我正在做一个项目来实现哈夫曼代码。问题是当我试图打印代码时得到了错误的结果

以下是输入文件和正确的结果：

Symbol    A     B   C   D    _
frequency 0.35 0.1 0.2 0.2 0.15
Code      11   100 00  01  101

我得到的结果是：

Symbol    A     B   C   D    _
frequency 0.35 0.1 0.2 0.2 0.15
Code      00   011  10  11  010

下面是类文件：

import java.util.*;
import java.io.*;
import java.util.PriorityQueue;

public class Node implements Comparable<Node> {
Node left;
        Node right;
    Node parent;
    String text;
    Float frequency;

    public Node(String textIn, Float frequencies) {
        text = textIn;
        frequency = frequencies;
    }

    public Node(Float d) {
        text = "";
        frequency = d;
    }

    public int compareTo(Node n) {
        if (frequency < n.frequency) {
            return -1;
        } else if (frequency > n.frequency) {
            return 1;
        }
        return 0;
    }

    public static void buildPath(Node root,String code)
{
    if (root!=null)
    {   
        if (root.left!=null)
            buildPath(root.left, code+"0");
        if (root.right!=null)   
          buildPath(root.right,code+"1");
        if (root.left==null && root.right==null)
            System.out.println(root.text+": "+code);               
    }       
}



    public static Node makeHuffmanTree(Float[] frequencies, String text[]) {
        PriorityQueue<Node> queue = new PriorityQueue<Node>();
        for (int i = 0; i < text.length; i++) {
            Node n = new Node(text[i], frequencies[i]);
            queue.add(n);
        }
        Node root = null;
        while (queue.size() > 1) {
            Node least1 = queue.poll();
            Node least2 = queue.poll();
            Node combined = new Node(least1.frequency + least2.frequency);
            combined.right = least1;
            combined.left = least2;
            least1.parent = combined;
            least2.parent = combined;
            queue.add(combined);
            // Keep track until we actually find the root
            root = combined;
        }
        return root;
    }

我想我的打印方法有问题吗

这是我的主要观点

public static void main(String[] args)
String[] Symbol = {"A","B","C","D","_"};
Float[] frequency = (0.35,0.1,0.2,0.2,0.15};

        Node root = Node.makeHuffmanTree(frequency, Symbol);
        Node.buildPath(root, "");

Answer 1

在您的输出中，单个代码的长度看起来不错，所以我不太相信这是一个树遍历问题

差异很可能在于你如何建造这棵树。当您从队列中弹出两个元素，并将这两个元素作为子树创建一个新树时，选择哪个子树是“左”子树会影响生成的代码

看看你的while循环，我明白了

while (queue.size() > 1) {
        Node least1 = queue.poll();
        Node least2 = queue.poll();
        Node combined = new Node(least1.frequency + least2.frequency);
        combined.right = least1;
        combined.left = least2;
        least1.parent = combined;
        least2.parent = combined;
        queue.add(combined);
        // Keep track until we actually find the root
        root = combined;
}

我还没有完全看完这个例子，但是看完你的例子后，我认为只要换成combined.left = least1和combined.right = least2而不是相反的方式，就会得到你所期望的代码