HW_3_2

#include<bits/stdc++.h>
using namespace std;

string code[26];
struct tree_node{
    char ch;
    int val;
    tree_node *lch, *rch;
    tree_node(int v, char c){
        ch = c;
        val = v;
        lch = rch = nullptr;
    }
    tree_node(int v, char c, tree_node *l, tree_node *r){
        ch = c;
        val = v;
        lch = l;
        rch = r;
    }
    void preorder(){
        cout << ' ' << val;
        if(lch != nullptr)lch->preorder();
        if(rch != nullptr)rch->preorder();
    }
    void inorder(){
        if(lch != nullptr)lch->inorder();
        cout << ' ' << val;
        if(rch != nullptr)rch->inorder();
    }
    int level(){
        int lv = 0;
        if(lch != nullptr)lv = max(lv, lch->level());
        if(rch != nullptr)lv = max(lv, rch->level());
        return lv+1;
    }
    void build_code(string s=""){
        if(lch == nullptr && rch == nullptr){
            code[ch-'a'] = s;
        }else{// two children
            lch->build_code(s+'0');
            rch->build_code(s+'1');
        }
    }
    char decode(string &s){
        if(lch == nullptr && rch == nullptr){
            return ch;
        }else if(s[0] == '0'){
            s.erase(0, 1);
            lch->decode(s);
        }else if(s[0] == '1'){
            s.erase(0, 1);
            rch->decode(s);
        }
    }
};

struct heap_node{
    tree_node *tree;
    int val;
    heap_node *lch, *rch;
    heap_node(int v, tree_node *T){
        tree = T;
        val = v;
        lch = rch = nullptr;
    }
};

// heap start from 1
heap_node *heap[100];
int heap_size = 0;

void Insert(heap_node *N){
    heap[++heap_size] = N;
    int cur = heap_size;
    while(cur > 1 && heap[cur]->val < heap[cur/2]->val){
        swap(heap[cur], heap[cur/2]);
        cur /= 2;
    }
}

heap_node *Pop(){
    heap_node *ret = heap[1];
    heap[1] = heap[heap_size];
    heap[heap_size--] = nullptr;
    int cur = 1;
    while(heap[cur*2] != nullptr){
        if(heap[cur*2+1] == nullptr){
            if(heap[cur]->val <= heap[cur*2]->val){
                break;
            }else{
                swap(heap[cur], heap[cur*2]);
                cur = cur*2;
            }
        }else if(heap[cur*2+1] != nullptr){
            if(heap[cur]->val <= heap[cur*2]->val
            && heap[cur]->val <= heap[cur*2+1]->val){
                break;
            }else if(heap[cur*2]->val <= heap[cur*2+1]->val){
                swap(heap[cur], heap[cur*2]);
                cur = cur*2;
            }else if(heap[cur*2]->val > heap[cur*2+1]->val){
                swap(heap[cur], heap[cur*2+1]);
                cur = cur*2+1;
            }
        }
    }
    return ret;
}


int main(){
    string s, cipher;
    cin >> s >> cipher;
    int cnt[26] = {0};
    for(int i = 0; i < s.size(); ++i){
        ++cnt[s[i]-'a'];
    }
    cout << "Symbol:";
    for(int i = 0; i < 26; ++i){
        if(cnt[i] != 0){
            cout << ' ' << (char)('a'+i);
        }
    }
    cout << "\nFrequency:";
    for(int i = 0; i < 26; ++i){
        if(cnt[i] != 0){
            cout << ' ' << cnt[i];
        }
    }
    cout << endl;
    // heap-ing
    for(int i = 0; i < 26; ++i){
        if(cnt[i] != 0){
            tree_node *T = new tree_node(cnt[i], 'a'+i);
            heap_node *H = new heap_node(cnt[i], T);
            Insert(H);
        }
    }
    while(heap_size > 1){
        heap_node *H1 = Pop();
        heap_node *H2 = Pop();
        tree_node *newT = new tree_node(H1->val+H2->val, 0, H1->tree, H2->tree);
        heap_node *newH = new heap_node(H1->val+H2->val, newT);
        Insert(newH);
    }
    tree_node *tree = heap[1]->tree;
    cout << "Huffman Tree:"<<endl;
    cout << "Preorder:";
    tree->preorder();
    cout << "\nInorder:";
    tree->inorder();
    cout << "\nLevel:";
    cout << tree->level() << endl;
    cout << "Huffman Code:" << endl;
    tree->build_code();
    for(int i = 0; i < 26; ++i){
        if(cnt[i] != 0){
            cout << (char)('a'+i) << " : " << code[i] << endl;
        }
    }
    cout << "Decode Result:\n";
    while(!cipher.empty()){
        cout << tree->decode(cipher);
    }
    cout << endl;
	return 0;
}