#includeusing namespace std;


class HufTree{public:
    float weight = 0;   // 权重
    int parent = 0;     // 双亲
    int lchi = 0;       // 左孩子
    int rchi = 0;       // 右孩子
        
    void CreatHT(HufTree* &HT, int n);  // 创建哈夫曼树方法
    void Select(HufTree* &HT, int k, int &s1, int &s2); // 得到权重最小的次小的下标方法
    char** Code(HufTree* HT, int n);    //实现哈夫曼编码方法
};


void HufTree::CreatHT(HufTree* &HT, int n){int s1, s2;     // 声明权重最小的下标s1和次小的下标s2
    HT = new HufTree[2 * n];    // 定义数组长度，0号位置不用，所以数组长度定义为2n-1+1，2n+1为最终哈夫曼树的总结点数
    // 输入每个结点的权重
    for(int i = 1; i< n + 1; ++i){cout<< "请输入第 "<< i<< " 个结点的权重值："<< endl;
        cin >>HT[i].weight;
    }

    for(int i = n + 1; i< 2 * n; ++i){Select(HT, i - 1, s1, s2);      // 选出权重最小的两个结点
        HT[i].weight = HT[s1].weight + HT[s2].weight;   // 结合两个小结点得到一个新结点
        HT[i].lchi = s1;    // 新结点的左孩子为s1
        HT[i].rchi = s2;    // 新结点的有孩子为s2
        HT[s1].parent = i;  // s1的双亲是i
        HT[s2].parent = i;  // s2的双亲是i
    }
}


void HufTree::Select(HufTree* &HT, int k, int &s1, int &s2){// k为已有结点的长度加1（因为0号位置未使用）
    float t = 100;  // 初始化一个常数t
    // 通过比较得出s1
    for(int i = 1; i< k + 1; ++i){if(t >HT[i].weight && HT[i].parent == 0){s1 = i;
            t = HT[i].weight;
        }
    }
    t = 100;    // 重新初始化t
    // 通过跳过s1比较得到s2
    for(int i = 1; i< k + 1; ++i){if(i == s1) continue;
        if(t >= HT[i].weight && HT[i].parent == 0){s2 = i;
            t = HT[i].weight;
        }
    }
}


char** HufTree::Code(HufTree* HT, int n){char** HC = new char* [n + 1];  // 声明一个二维字符数组，用以接收原数组需要编码的字符的编码
    char* cd = new char[n];     // 声明一个一维字符数组用以储存
    cd[n - 1] = '\0';   // cd数组的最后一位加上终止符
    // 遍历原数组需要编码的每个字符
    for(int i = 1; i< n + 1; ++i){int j = i;  // j用于在while循环内实现从叶子结点找双亲
        int k = n - 2;  // k用于记录当前cd数组空的位置，由于从叶子结点找双亲的话编码顺序是反的，所以要从尾部开始存入0和1
        while(HT[j].parent != 0){// 若当前结点的双亲为0，说明已遍历到根结点，遍历完毕
            // 若该叶子的双亲结点的左孩子为该叶子结点，则cd数组计入0
            if(HT[HT[j].parent].lchi == j){cd[k] = '0';
                --k; // k指向cd数组的前一个位置
            }
            // 若该叶子的双亲结点的右孩子为该叶子结点，则cd数组计入1
            if(HT[HT[j].parent].rchi == j){cd[k] = '1';
                --k; // k指向cd数组的前一个位置
            }
            j = HT[j].parent;   // 此时遍历的结点更新为当前结点的双亲
        }
        HC[i] = new char[n - k];    // 申请一个和当前cd数组一样大小的字符数组，另二维数组中的第i个一维数组指针指向该字符数组
        strcpy(HC[i], &cd[k + 1]);  // 将cd中包括k从k之后的所有字符复制给HC的第i个字符数组
    }
    delete [] cd;   // 释放掉cd数组的空间
    return HC;  // 返回HC二维指针
}


int main()
{HufTree *a;     // 实例化一个HufTree指针a

    a->CreatHT(a, 7);   // 调用a中的创建方法创建一棵哈夫曼树

    char** p = a->Code(a, 7);   // 实例化一个二维数组指针指向哈夫曼编码数组

    // 打印二维数组
    for(int i = 1; i< 8; ++i){for(int j = 0; j< 7; ++j){cout<< p[i][j];
        }
        cout<< endl;
    }

    delete a;   // 释放掉a的空间

    // 释放掉二维数组p中的指针指向的空间
    for(int i = 0; i< 8; ++i){delete [] p[i];
    }

    delete [] p;    // 释放掉指向二维数组p的空间
    return 0;  
}

实现创建包含7个元素的哈夫曼树以及输出其对应的哈夫曼编码。如有错误的地方，还请不吝赐教。

创新互联建站凭借在网站建设、网站推广领域领先的技术能力和多年的行业经验，为客户提供超值的营销型网站建设服务，我们始终认为：好的营销型网站就是好的业务员。我们已成功为企业单位、个人等客户提供了网站设计制作、网站设计服务，以良好的商业信誉，完善的服务及深厚的技术力量处于同行领先地位。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享题目：C++创建一棵哈夫曼树以及输出其哈夫曼编码-创新互联
分享URL：http://scyanting.com/article/gooec.html