c++哈夫曼树实现-创新互联

#include
using namespace std;

struct Tpoint {
 int weight;
 int lchild;
 int rchild;
 int parent;
};

void INIT(Tpoint* T,int n) {                        //初始化哈夫曼树
 for (int i = 1; i<= 2 * n - 1; i++) {
     T[i].lchild = 0;
     T[i].rchild = 0;
     T[i].parent = 0;
 }
 int weight;
 for (int i = 1; i<= n; i++) {
     cin >>weight;
     T[i].weight = weight;
 }
}

void Show(Tpoint* T,int n) {     //展示二叉树
 for (int i = 1; i<=  2 * n - 1; i++) {
     cout<< i<<"\t"<  }
}

void SelectMin(Tpoint* T, int n, int& m1, int& m2) {  //找到i之前且双亲为0的最小两个结点
 for (int i = 1; i<= n; i++) {
     if (T[i].parent != 0)
         continue;
     if (T[m1].weight >T[i].weight)
         m1 = i;
 }
 for (int i = 1; i<= n; i++) {
     if (T[i].parent != 0 || i == m1)
         continue;
     if (T[m2].weight >T[i].weight)
         m2 = i;
 }
}

void BuildHuffman(Tpoint* T, int n) {  //生成huffman树
 int m1=1, m2;
 for (int i = n + 1; i<= 2 * n - 1; i++) {
     m1 = 0, m2 = 0;
     SelectMin(T, i - 1, m1, m2);
     T[m1].parent = i ;
     T[m2].parent = i ;
     T[i].lchild = m1;
     T[i].rchild = m2;
     T[i].weight = T[m1].weight + T[m2].weight;
 }
}

int main() {
 Tpoint T[100];
 T[0].weight = 1000;
 int n;
 cout<< "输入哈夫曼树叶子节点数";
 cin >>n;
 cout<< endl;
 INIT(T,n);
 BuildHuffman(T, n);
 Show(T,n);
}

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