허프만 이진 트리가 적절해야합니까?

Question

허프만 코딩에서 찾을 수있는 모든 예제에는 작업 할 짝수 개의 문자가 포함되어 있습니다. 그것이 홀수의 문자 인 경우 트리에 추가 된 마지막 내부 노드는 단일 자식을 가질 수 있습니까? 또는 모든 내부 노드가 정확하게 2 개의 자식을 가질 수 있도록 일종의 NULL 노드를 추가해야합니까?

나중에있는 경우 모든 값이 유효한 ASCII 코드로 사용되므로 char에 NULL 값을 갖는 방법을 모르므로 혼란 스럽습니다.

Answer 1

홀수 인 char은 아무런 문제가되지 않습니다. 그러나 그것은 하나의 자식 만 가진 내부 노드로 이어지지 않을 것입니다. 나무가 구성되어

/\ 
/\ 
a × 
    /\ 
    b c 

방법은 모든 내부 노드에 관계없이 얼마나 많은 char의가에, 두 아이를 갖게됩니다.

잎 목록으로 시작한 다음 각 단계에서 최저 빈도를 가진 두 나무가 왼쪽 resp로 결합됩니다. 하나의 트리가 남을 때까지 새 노드 - 내부 노드의 오른쪽 서브 트리를 찾습니다. 최종 결과의 각 내부 노드는 두 개의 하위 트리를 결합하여 생성되므로 두 개의 하위 노드가 있습니다.