1

这是我第一次使用 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, "");
4

1 回答 1

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不是相反将给出您期望的代码。

于 2013-08-08T19:14:55.097 回答