#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元起，快前往官网查看详情吧