输出哈夫曼树各叶子结点的编码 | inSoraSky BLOG

#include <iostream>
using namespace std;
struct Node{
    int data;
    Node *lchild, *rchild;
};
bool compare(Node *p, Node *q){
    return p->data > q->data;
}
void setup(Node *arr[], int count){
    Node *p;
    while(count > 1){
        sort(arr, arr + count, compare);
        p = new Node;
        p->data = arr[count - 1]->data + arr[count - 2]->data;
        p->lchild = arr[count - 1];
        p->rchild = arr[count - 2];
        arr[(count--) - 2] = p;
    }
}
void show(Node *head, int n){
    if(head->lchild == NULL && head->rchild == NULL){
        cout << head->data << endl;
    }
    if(head->lchild != NULL) show(head->lchild, n + 1);
    if(head->rchild != NULL) show(head->rchild, n + 1);
}
int main(){
    int numbers[10] = {2,3,5,7,9,10,12,15,18,20};
    Node *arr[10];
    for(int i = 0; i < 10; i++){
        arr[i] = new Node;
        arr[i]->data = numbers[i];
        arr[i]->lchild = NULL;
        arr[i]->rchild = NULL;
    }
    setup(arr, 10);
    show(arr[0], 1);
    return 0;
}