허프 먼 트리를 가로 질러

Question

그래서 현재는 허프 먼 트리를 만드는 프로그램이 있습니다. 그 나무는 다음과 같은 필드가있는 "Hnodes"로 구성됩니다. right (오른쪽 자식 노드) left (왼쪽 자식 노드를 가리킴) 코드 (정수 문자열, 이상적으로이 노드의 huffman 코드가 될 0과 1 문자) character 노드에 포함 된 문자).

링크 된 목록에서 노드를 추가하여 허프만 트리를 만들었습니다. 올바르게 생성 된 트리입니다. 내가 트리를 만들었을 때 노드에 부모 노드를 주었을 때 부모에게 "맞다"면 그 코드 문자열은 0이 남았을 때 1이었습니다. 그러나 분명히 전체 트리가 생성 된 후 각 노드는 오직 0이나 1을 가지지 만 00100101과 같은 문자열은 아닙니다. 제 질문은, 이제이 나무가 생겼을 때, 그것을 통과 할 수 있습니까? 나는 각 어린이에게 그 부모의 코드 + 그 자신의 코드를주는 것이라고 생각한다. 그러나 이것을 달성하기 위해 나무를 반복하는 법을 이해하지 못한다.

미리 감사드립니다.

Answer 1

어쩌면?

ExpandBinaryPaths(node, prefix) 
    1. if node is null then return 
    2. else then 
    3. node.binary = prefix concat node.binary 
    4. ExpandBinaryPaths(node.left, node.binary) 
    5. ExpandBinaryPaths(node.right, node.binary) 
    6. return 

접두어가없는 루트에서 생각해보십시오. ExpandBinaryPaths (루트, "").