허프만 트리(Huffman Tree)

허프만 트리

가장 빈도가 많이 나온순으로 정렬하고

그 값들을 트리에 모두 달아준다. 이때 0과 1로 된 트리에 달아줌으로써 문자열을 압축할 수 있다.

(Greedy Algorithm의 일종)

허프만 트리 설명 :: https://wooyaggo.tistory.com/95

입력이 

1110010001 이고

4개의 값(A,B,C,D)이 각각 00 01 11 10일 때

즉, 

1110010001

4 00 01 11 10 

로 인풋이 들어왔을 때

허프만 트리 알고리즘을 이용하면

답이 CDBAB가 된다.

추가 케이스 :

0001001100100111001

4 11 01 10 00 

답 DBDADCBAD

소스 코드 : 

 
#include <iostream>
 
typedef struct HuffmanTree {
public:
    HuffmanTree *left, *right;
    char ch;
 
    HuffmanTree() {
        left = right = nullptr;
        ch = '\0';
    }
};
 
int _strlen(char *str) {
    int len = 0;
    while (str[++len]);
    return len;
}
int main() {
    char str[52];
    scanf("%s", str);
 
    int n;
    scanf("%d", &n);
 
    HuffmanTree *root = new HuffmanTree();
 
    for (int i = 0; i < n; i++) {
        char tmp[52];
        scanf("%s", tmp);
 
        int len = _strlen(tmp);
        HuffmanTree *cur = root;
        for (int j = 0; j < len; j++) {
            if (tmp[j] == '0') {
                if (cur->left == nullptr) 
                    cur->left = new HuffmanTree();
 
                cur = cur->left;
            }
            else if(tmp[j] == '1') {
                if (cur->right == nullptr)
                    cur->right = new HuffmanTree();
 
                cur = cur->right;
            }
        }
        cur->ch = 'A' + i;
    }
 
    int len = _strlen(str);
    HuffmanTree *cur = root;
    for (int i = 0; i < len; i++) {
        if (str[i] == '0') {
            cur = cur->left;
            if (cur->left == nullptr) {
                printf("%c", cur->ch);
                cur = root;
            }
        }
        else if (str[i] == '1') {
            cur = cur->right;
            if (cur->right == nullptr) {
                printf("%c", cur->ch);
                cur = root;
            }
        }
    }
    return 0;
}