5

宿題の問題をどうするか理解しようとしています。Java でメッセージをエンコードおよびデコードするハフマン ツリーを作成しようとしています。私は文字列と周波数を与えられています。

[a=10, b=15, c=12, e=3, nl=4, sp=13, t=1].

ハフマン ツリーを使用すると、最も低い 2 つの周波数を取得し、それらの周波数の合計を親としてツリーにすることができます。Priority Queue を使用すると、すべての Frequency をそれに挿入し、remove()メソッドを使用して 2 つの最も低い Frequency を取り出すことができることを理解しています。次に、それらを合計して両方の重みを取得し、その重みをキューに挿入して繰り返します。

最終的なツリーは次の重みを保持する必要があります

[58=root, root.left = 33, root.right = 25]   
[33.left = 18,  18.left = 8,  8.left = 4]

頻度でツリーを作成し、ツリーを表示できるハフマンツリーコードの実装を開始する方法さえ正確にはわかりません。私は他のコードを見てきましたが、それらはすべてストリーミング入力コードなどから作成しているようです。

どんな助けでも私を動かすのに素晴らしいでしょう。前もって感謝します！

次のような形式で印刷することを想定しています: (pre-order traversal)

58  
- 33  
- - 18  
- - - 8  
- - - - 4  
- - - - - 1:t  
- - - - - 3:e  
- - - -  4:nl  
- - - 10:a  
- - 15:b  
- 25  
- - 12:c  
- - 13:sp
4

1 に答える 1

4 
import java.util.PriorityQueue;

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

    public Node(String textIn, int frequencyIn) {
        text = textIn;
        frequency = frequencyIn;
    }

    public Node(int frequencyIn) {
        text = "";
        frequency = frequencyIn;
    }

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

    public static void printFromPreOrder(Node n, String dashes) {
        // print with colon if leaf node
        if (n.text != "") {
            System.out.println(dashes + n.frequency + ":" + n.text);
        }
        else {
            System.out.println(dashes + n.frequency);
        }

        // Start recursive on left child then right
        if (n.left != null) {
            printFromPreOrder(n.left, dashes + "-");
        }
        if (n.right != null) {
            printFromPreOrder(n.right, dashes + "-");
        }
    }

    // Returns root node to pass to printFromPreOrder
    public static Node makeHuffmanTree(int 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) {
        int frequencies[] = {10, 15, 12, 3, 4, 13, 1};
        String text[] = {"a", "b", "c", "e", "nl", "sp", "t"};
        Node root = Node.makeHuffmanTree(frequencies, text);
        Node.printFromPreOrder(root, "");
    }
}

これはあなたのために働くでしょう。あなたの例を含めましたが、任意の数の頻度とテキストで機能するはずです。エラーチェックを行っていないため、頻度とテキストが同じサイズであることを確認してください。

于 2013-03-31T23:40:03.983 に答える