关于哈夫曼树其基本定义我就在这不多说了。我写的这个哈夫曼树没有太多的功能，就是我们參考书上的一个作业，就俩个功能，一个是表示孩子双亲表示法。，还有就是吧这个最有二叉树给画出来。其它的就没有了。另外在今天我调试的时候发现我的代码还是有非常多欠缺的地方的。比方哦说我的绘图功能中就没有办法完整的输出。而是无法输出最后四个结点。
原因我还在寻找。
以下就哈夫曼树我来谈谈我当时的构思：
首先我是吧他当作一个二叉树来写的。我首先申明一个结点构造的结点函数element，在element中我所有都是用的int 来定义的，由于在哈发满树中我们须要的是每一个节点的权值，所以我们就不须要用到类模板 了，而是直接用int来解决这个类。
然偶就是在这个类中添砖加瓦的事情了。自己想要什么函数，在里面申明解释即可了。
我在构造函数的时候当中有selected和绘图函数比較难搞。
以下#ifndef HFMTREE_H
#define HFMTREE_H const int Max = 100; #include"BiTree.h" #include<iostream> using namespace std; struct element { int weight; int lchild, rchild, parent; }; class HfmTree { public: HfmTree(int size); void Creat(int n); void SeLect(int k, int &s1, int &s2 ,int z); void reset(int size); void print(int size); void Makeary(int size); void printInl(int size, int i); void printInr(int size, int i); void Build(int size); private: int m1; int top = 0; element *root; int maxsize; int *pz; element *root3; };void HfmTree::reset(int size)
{ int m; m = 2 * size - 1; pz = new int[m]; int i; pz[0] = root[m].weight; for (i = 1; i < m; i++) pz[i] = 0; } void HfmTree::Build(int size) { BiTree<int> zxh1(pz, 2 * size - 1, 0); cout << zxh1; } void HfmTree::printInl(int m, int i) { if (m == -1)return; if (m!=-1) { //pz[i - 1] = root[m].weight; pz[2 * i - 1] = root[root[m].lchild].weight; pz[2 * i] = root[root[m].rchild].weight; m = root[m].lchild; printInl(m, 2 * i); m = root[m].lchild; } } void HfmTree::printInr(int m, int i) { if (m == -1)return; if (m!=-1) { //pz[i - 1] = root[m].weight; pz[2 * i - 1] = root[root[m].lchild].weight; pz[2 * i] = root[root[m].rchild].weight; m = root[m].rchild; printInr(m, 2*i+1); m = root[m].rchild; } } void HfmTree::Makeary(int size) { int m; m = 2 * size - 1; pz = new int[m]; int i; for (i = 1; i <= m; i++) pz[i] = 0; i = 1; while (root[m].parent != size-1) { if (m == -1)break; pz[i-1] = root[m].weight; i=2*i; m = root[m].lchild; } m = 2 * size - 1; i = 1; while (root[m].parent != size-1) { if (m == -1)break; pz[i-1] = root[m].weight; i = 2 * i + 1; m = root[m].rchild; } BiTree<int> zxh1(pz, 2*size+1, 0); cout << zxh1; } void HfmTree::SeLect(int k, int &s1, int &s2 ,int z) { int w1, w2, i = 1,j; w1 = w2 = Max; //s1 = s2 = i; for (i = 1; i <= k; i++) { //if (i == s1 || i == s2)continue; if (root[i].parent==-1) { if (root[i].weight < w1) { w2 = w1; w1 = root[i].weight; s2 = s1; s1 = i; //w1,s1是相应的，且他们的weight是较小者 } else if (root[i].weight < w2) { w2 = root[i].weight; s2 = i; } } } } void HfmTree::Creat(int n) { int *w1; int i,m,*w,s1,s2; element *p; if (n < 1)throw"构建有误！";
w = new int[2 * n - 1]; w1 = new int[2 * n - 1]; m = 2 * n - 1; //n个结点过程中有2*n-1个结点 m1 = m; root = new element[m + 1]; for (i =1; i <= 2 * n - 1; i++) { //root[i].weight = NULL; root[i].lchild = -1; root[i].rchild = -1; root[i].parent = -1; } for (p = root + 1, i = 1; i <= n; i++, p++) { cout << "请输入全职:" << endl; cin >> w[i]; p->weight = w[i]; p->lchild = -1; p->rchild = -1; p->parent = -1; } for (i = n+1 ; i <= m; i++, p++) { p->weight = NULL; p->lchild = -1; p->rchild = -1; p->parent = -1; } for (i = n+1 ; i <= m; i++) { SeLect(i-1 , s1, s2,m); root[s1].parent = i-1; root[s2].parent = i-1; root[i].weight = root[s1].weight + root[s2].weight; root[i].lchild = s1; root[i].rchild = s2; } for (int i = 1; i <= n; i++) { w1[i-1] = w[n - i + 1]; } }HfmTree::HfmTree(int size)
{ Creat(size); } void HfmTree::print(int size) { int m, i; m = 2 * size - 1;//树结点总个数。 cout << "构建的哈夫曼树为" << endl; cout << "no" <<" "<< "weight" <<" "<<"Parent"<<" "<< "lchild" <<" "<< "rchild" << endl; for (i = 1; i <= m; i++){ cout << i <<" "<< root[i].weight <<" "<<root[i].parent<<" "<< root[i].lchild <<" "<< root[i].rchild << endl; } } #endif —————————————————————————————————————————————————————————————————————— #include"HfmTree.h" //#include"BiTree.h" #include<iostream> using namespace std; void main() { int num; cout << "请输入您想构造的哈夫曼树的结点个数(num):"; cin >> num; HfmTree zxh(num); zxh.print(num); //zxh.Makeary(num); zxh.reset(num); zxh.printInl(2*num-1,1); zxh.printInr(2*num-1, 1); zxh.Build(num); }主要用代码解释