이상한 트리 (자바)를주는 허프만 인코딩 알고리즘

저는 여기에서 많은 다른 것들을 시도해 왔으며 제대로 작동하지 않는 것처럼 보입니다. 입력은 "abbcccddddeeeee"였으며, 링크 된 목록 a, b, c, d, e에 각각 1, 2, 3, 4, 5의 주파수를 제공했습니다. 어떤 이유이상한 트리 (자바)를주는 허프만 인코딩 알고리즘

는하지만, 그것은 나에게 내가 실행 한 다른 테스트의 많은에 따라 다음 트리주는 것으로 나타납니다 : 누군가가 나를 도울 수 있다면 절대적으로 놀라운 것

    f15 
       / \ 
       f6 f9 
      /\ 
       d4 e5 
      /\ 
      f3 c3 
     /\ 
     a1 b2 

public static HTree createHuffmanTree(HLinkedList list) 
{ 
    while (list.size() != 1) 
    { 
    list = getSortedLinkedList(list); 
    HTreeNode p = list.head; 
    HTreeNode q = p.next; 
    HTreeNode r = new HTreeNode('f'); 
    r.left = p; 
    r.right = q; 
    r.frequency = (p.frequency + q.frequency); 
    list.insertIntoPosition(r, 2); 
    list.remove(0); 
    list.remove(0); 
    list = getSortedLinkedList(list); 
    } 
    return new HTree(list.head); 
}

을, 나는 믿을 수 없을 정도로, 매우 좌절감을 느낀다.

감사합니다.

출처

2011-10-05 Andrew Latham

문제는 getSortedLinkedList입니다. 포인터가 빈도 값으로 이동하지 않도록 노드 자체가 아닌 빈도 값을 교환하는 것처럼 보입니다. 당신이 연결리스트를 처리 할 때

일반적으로, 각 단계의 그림을 그릴 정말 유용 :

a1->b2->c3->d4->e5

첫 번째 단계 :

f3->c3->d4->e5 
    /\ 
a1 b2

종류 :

다음 변화 없음 단계 :

f6->d4->e5 
    /\ 
    f3 c3 
    /\ 
a1 b2

종류는이 작업을 수행합니다

d4->e5->f6 (forgot to move child nodes with frequency) 
    /\ 
    f3 c3 
    /\ 
a1 b2

다음 단계 :

 f9->f6 
     /\ 
    d4 e5 
    /\ 
    f3 c3 
    /\ 
a1 b2

종류 :

 f6->f9 (forgetting to move child nodes with frequency) 
     /\ 
    d4 e5 
    /\ 
    f3 c3 
    /\ 
a1 b2

마지막 단계 :

출처

2011-10-05 07:48:41 Skizz

너무 감사합니다! :) –

이상한 트리 (자바)를주는 허프만 인코딩 알고리즘

답변

관련 문제