huffman tree

[Hsue66]

include

using namespace std;

include

define MAX 100

int freq[6][2] = { {0,45000},{1,13000} ,{2,12000} ,{3,16000} ,{4,9000}, {5,5000} };

struct Node { int fre; char ch; Node left, right;

void init() {
    left = right = 0;
}

int isLeaf() {
    return (left == 0 && right == 0);
}

int hasLeft() {
    return left != 0;
}

int hasRight() {
    return right != 0;
}

};

struct minHeap { Node *heap[MAX]; int size;

void init() {
    size = 0;
}

int empty() {
    return size;
}

void push(Node *node) {
    int target = size + 1;
    while (target != 1 && heap[target / 2]->fre > node->fre) {
        heap[target] = heap[target / 2];
        target /= 2;
    }
    heap[target] = node;
    size++;
}

Node* top() {
    return heap[1];
}

void pop() {
    int parent = 1, child = 2;
    Node *temp = heap[size];
    while (child < size) {
        if (child + 1 < size && heap[child]->fre > heap[child + 1]->fre)
            child++;
        if (temp->fre <= heap[child]->fre) break;
        heap[parent] = heap[child];
        parent = child;
        child += 2;
    }
    heap[parent] = temp;
    size--;
}

void show() {
    for (int i = 1; i <= size; i++)
        cout << heap[i]->fre << " ";
    cout << endl;
}

};

struct HuffmanTree { minHeap minheap; Node nodeArr[MAX]; int size;

Node* alloc() {
    return &nodeArr[size++];
}
void init() {
    size = 0;
    minheap.init();
    for (int i = 0; i < 6; i++) {
        Node *tmp = alloc();
        tmp->init();
        tmp->ch = freq[i][0] + 'a';
        tmp->fre = freq[i][1];
        minheap.push(tmp);
        //minheap.show();
    }
}

void makeTree() {
    while (minheap.empty() > 1) {
        Node *A = minheap.top();
        minheap.pop();
        Node *B = minheap.top();
        minheap.pop();
        Node *tmp = alloc();
        tmp->init();
        tmp->fre = A->fre + B->fre;
        tmp->left = A;
        tmp->right = B;
        minheap.push(tmp);
        //minheap.show();
    }
    cout << "done" << endl;
}

void getAlpha(char *p) {
    Node *root = minheap.top();
    int i = 0;
    printf("%s :", p);

    while (p[i]) {
        if (p[i] == '0' && root->hasLeft())
            root = root->left;
        else if(p[i] == '1' && root->hasRight())
            root = root->right;
        else {
            printf(" wrong code\n", root->ch);
            return;
        }
        i++;
    }
    if (root->isLeaf())
        printf(" : %c\n", root->ch);
}

};

int main() { HuffmanTree hufftree; hufftree.init(); cout << "MAKE TREE " << endl; hufftree.makeTree(); hufftree.getAlpha((char)"0"); hufftree.getAlpha((char)"100"); hufftree.getAlpha((char)"101"); hufftree.getAlpha((char)"111"); hufftree.getAlpha((char)"1100"); hufftree.getAlpha((char)"1101"); hufftree.getAlpha((char*)"11010"); }