/* project name:哈夫曼树 Time Complexity: O(n²) */ #include <iostream>
using namespace std; //最大字符编码数组长度
#define MAXCODELEN 100
//最大哈夫曼节点结构体数组个数
#define MAXHAFF 100
//最大哈夫曼编码结构体数组的个数
#define MAXCODE 100
#define MAXWEIGHT 10000; typedef struct Haffman { //权重
    int weight; //字符
    char ch; //父节点
    int parent; //左儿子节点
    int leftChild; //右儿子节点
    int rightChild; } HaffmaNode; typedef struct Code { //字符的哈夫曼编码的存储
    int code[MAXCODELEN]; //从哪个位置开始
    int start; } HaffmaCode; HaffmaNode haffman[MAXHAFF]; HaffmaCode code[MAXCODE]; void buildHaffman(int all) { //哈夫曼节点的初始化之前的工作, weight为0,parent,leftChile,rightChile都为-1
    for (int i = 0; i < all * 2 - 1; ++i) { haffman[i].weight = 0; haffman[i].parent = -1; haffman[i].leftChild = -1; haffman[i].rightChild = -1; } std::cout << "请输入需要哈夫曼编码的字符和权重大小" << std::endl; for (int i = 0; i < all; i++) { std::cout << "请分别输入第个" << i << "哈夫曼字符和权重" << std::endl; std::cin >> haffman[i].ch; std::cin >> haffman[i].weight; } //每次找出最小的权重的节点,生成新的节点,需要all - 1 次合并
    int x1, x2, w1, w2; for (int i = 0; i < all - 1; ++i) { x1 = x2 = -1; w1 = w2 = MAXWEIGHT; //注意这里每次是all + i次里面便利
        for (int j = 0; j < all + i; ++j) { //得到最小权重的节点
            if (haffman[j].parent == -1 && haffman[j].weight < w1) { //如果每次最小的更新了，那么需要把上次最小的给第二个最小的
                w2 = w1; x2 = x1; x1 = j; w1 = haffman[j].weight; } //这里用else if而不是if,是因为它们每次只选1个就可以了。
            else if (haffman[j].parent == -1 && haffman[j].weight < w2) { x2 = j; w2 = haffman[j].weight; } } //么次找到最小的两个节点后要记得合并成一个新的节点
        haffman[all + i].leftChild = x1; haffman[all + i].rightChild = x2; haffman[all + i].weight = w1 + w2; haffman[x1].parent = all + i; haffman[x2].parent = all + i; std::cout << "x1 is" << x1 << " x1 parent is" << haffman[x1].parent << " x2 is" << x2 << " x2 parent is " << haffman[x2].parent << " new Node is " << all + i << "new weight is"
                  << haffman[all + i].weight << std::endl; } } //打印每个字符的哈夫曼编码
void printCode(int all) { //保存当前叶子节点的字符编码
 HaffmaCode hCode; //当前父节点
    int curParent; //下标和叶子节点的编号
    int c; //遍历的总次数
    for (int i = 0; i < all; ++i) { hCode.start = all - 1; c = i; curParent = haffman[i].parent; //遍历的条件是父节点不等于-1
        while (curParent != -1) { //我们先拿到父节点，然后判断左节点是否为当前值，如果是取节点0 //否则取节点1,这里的c会变动，所以不要用i表示，我们用c保存当前变量i
            if (haffman[curParent].leftChild == c) { hCode.code[hCode.start] = 0; std::cout << "hCode.code[" << hCode.start << "] = 0"
                          << std::endl; } else { hCode.code[hCode.start] = 1; std::cout << "hCode.code[" << hCode.start << "] = 1"
                          << std::endl; } hCode.start--; c = curParent; curParent = haffman[c].parent; } //把当前的叶子节点信息保存到编码结构体里面
        for (int j = hCode.start + 1; j < all; ++j) { code[i].code[j] = hCode.code[j]; } code[i].start = hCode.start; } } int main() { std::cout << "请输入有多少个哈夫曼字符" << std::endl; int all = 0; std::cin >> all; if (all <= 0) { std::cout << "您输入的个数有误" << std::endl; return -1; } buildHaffman(all); printCode(all); for (int i = 0; i < all; ++i) { std::cout << haffman[i].ch << ": Haffman Code is:"; for (int j = code[i].start + 1; j < all; ++j) { std::cout << code[i].code[j]; } std::cout << std::endl; } return 0; }