哈夫曼树是权重路径最小的特殊二叉树，也叫最优二叉树。
在此不讨论路径的计算方法等基本概念，而是聚焦于树的制作，并以具体过程为例进行说明。
其基本原理是将所有节点最初视为森林，每次从森林中选择根节点权重最小的两棵树合并为一棵新树，将新树的根节点大小为两个子节点大小之和，然后将该新树再次添加到森林中
这样，每个操作都可以简化为两个基本操作。 也就是说，合并两棵树，插入新树，直到森林中只剩下一棵树，也就是哈夫曼树。
如果将7个节点的权重分别设为1379121825
创建的第一步：合并1、3并添加4
合并创建的步骤2:4、7，添加11
合并创建的步骤3:9、11，添加20
合并创建的步骤4:12、18，添加30
合并创建的步骤5:20、25，添加45
合并最后两棵树，得到哈夫曼树
在程序中实际运行并创建此树后，进行了第一次遍历，结果如下：
你会发现所有的操作都符合结果
在创建过程中，一个重要的过程是每次都必须从森林中选择节点权重最小的两棵树合并并插入森林中。 这个过程可以通过插入和删除最小山来实现。 关于最大最小山的实现和说明，可以看到dalao的这个客人：
3358 blog.csdn.net/ava1anche/article/details/46965675
实现代码/*时间： 2015.7.20名称：哈夫曼树操作：哈夫曼树的制作、哈夫曼树的层序遍历(易懂)、哈夫曼树的森林相关操作)最大最小堆的操作)、树的中序遍历简单int cost=0； const int MAX_CAPACITY=100000； //森林最大容纳量enum type{Maxiumn，Miniumn}； //表示森林类型是因大而小，还是因小而大的typedef struct Node//树的节点结构{ int weight； //定义权重的Node* Leftchild； //定义左子树Node* Rightchild； //定义右边的子树； 节点标志； //森林的第一个哨兵节点typedef struct Huffmantree//哈夫曼树的森林结构{ int size； //森林的当前大小Node *tree[MAX_CAPACITY]； //森林的最大容量； Huffmantree Trees； //哈夫曼树森林voidinsertmax(node*insertnode ) ) /按从大到小的顺序插入森林)插入最大的山中({ int pos= Trees.size； //用临时变量指向末尾，整体容量加1； for (； trees.tree [ pos/2 ]-weightinsertnode-weight； pos/=2(/每次与对应的父节点进行比较，寻找插入位置(trees.tree [ pos ]=trees.tree [ pos/2 ] )； //不满足插入条件而下沉的对应父节点} Trees.tree[pos]=insertNode； //找到插入位置插入}voidinsertmin(node*insertnode )//插入从小到大的森林(插入最小堆) { int pos= Trees.size； //用临时变量指向末尾，整体容量加1； for (； trees.tree [ pos/2 ]-weightinsertnode-weight； pos/=2({ trees.tree [ pos ]=trees.tree [ pos/2 ] )； //不满足插入条件而下沉的对应父节点} Trees.tree[pos]=insertNode； //找到插入位置后插入}Node* deleteMax ()//删除按大小顺序排列的森林(删除最大的山) { int parent=1，child=1； //指向父节点和子节点的游标Node* maxNode=Trees.tree[1]； //用于保存删除的最大节点node * lastnode=trees.tree [ trees.size ]； //用于保存最后一个节点--Trees.size； //减少一个数量的for(parent=1； parent * 2=Trees.size； parent=child ) { child=parent * 2； if (神盾局！=Trees.size防止越境if(trees.tree[child]-weight
Trees.tree[child + 1]->weight)//选中较大的子节点 ++child; //每次都需要判断子节点是否还有子节点，没有的话就上浮保存最后一个节点用于补位 if (lastNode->weight <= Trees.tree[parent]->weight)//此时代表需要上浮最后一个节点用于补位，循环结束 if (lastNode->weight>Trees.tree[child]->weight) break; else Trees.tree[parent] = Trees.tree[child];//上浮较大的节点 } Trees.tree[parent] = lastNode; return maxNode;}Node* deleteMin()//从小到大排列的森林的删除 （最小堆的删除）{ int parent = 1, child = 1;//用于指向父节点和子节点的游标 Node* minNode = Trees.tree[1];//用于保存删除的最小节点 Node* lastNode = Trees.tree[Trees.size];//用于保存最后一个节点 --Trees.size;//数量减一 for (parent = 1; parent * 2 <= Trees.size; parent = child) { child = parent * 2; if (child != Trees.size)//防止越界 if (Trees.tree[child]->weight > Trees.tree[child + 1]->weight)//选中较小的子节点 ++child; //每次都需要判断子节点是否还有子节点，没有的话就上浮保存最后一个节点用于补位 if (lastNode->weight >= Trees.tree[parent]->weight)//此时代表需要上浮最后一个节点用于补位，循环结束 if (lastNode->weight<Trees.tree[child]->weight) break; else Trees.tree[parent] = Trees.tree[child];//上浮较小的节点 } Trees.tree[parent] = lastNode; return minNode;}int isFull()//判断森林是否已满{ if (Trees.size == MAX_CAPACITY) return 1; else return 0;}int isEmpty()//判断森林是否已空{ if (Trees.size == 0) return 1; else return 0;}Node* CreateTree_a()//创建树{ while (Trees.size != 1)//直到只剩下一棵树 { Node* one = deleteMin();//每次删除两棵树合并为一棵新的树 Node* two = deleteMin(); Node* newNode=new Node(); newNode->weight = one->weight + two->weight; newNode->Leftchild=one; newNode->Rightchild = two; insertMin(newNode); } return Trees.tree[1];}void preTraversal(Node* root){ cout << root->weight << ' '; if (root->Leftchild!=NULL) preTraversal(root->Leftchild); if (root->Rightchild!=NULL) preTraversal(root->Rightchild);}int main(){ //主函数部分是测试用代码，可以无视 int N; Node *flag = new Node(); Node *hufftree=NULL; flag->weight = -1000; flag->Leftchild = NULL; flag->Rightchild = NULL; Trees.size = 0; Trees.tree[0] = flag; cin >> N; for (int i = 0; i < N; i++) { Node* newnode=new Node(); cin >> newnode->weight; newnode->Leftchild = NULL; newnode->Rightchild = NULL; insertMin(newnode);//插入小根堆 //insertMax(newnode); } preTraversal(CreateTree_a()); return 0;}转自 dalao博客