허프만 트리 잘못 출력

Question

이있는 질문을하고 난 너희들이이 허프만 코드를 구현하는 투사에 :) 내가하고 있어요

나를 도울 수 희망 유래를 사용하여 내 첫 번째 시간입니다. 문제는 코드를 인쇄하려고 할 때 잘못된 결과가 발생한다는 것입니다.

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

내가 가진 결과 : 뭔가가 있다고 생각

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

:

여기

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

클래스 파일입니다 여기에

입력 파일 및 올바른 결과입니다 내 인쇄 방법에 문제가 있니?

과 출력에서 ​​

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

을 heres 내 주요는 개별 코드의 길이는 잘 보면, 그래서 그것을 지금 트리 탐색 문제의 적은 확신한다.

불일치는 나무를 어떻게 만들고 있는지 잘 나타납니다. 대기열에서 두 개의 요소를 제거하고 그 두 개를 하위 트리로 사용하여 새 트리를 만들 때 어떤 하위 트리가 "왼쪽"하위 트리인지 선택하면 결과 코드가 영향을받습니다.

당신의 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 생각 주위에 당신이 기대하는 코드를 줄 것이다.