哈夫曼树是带权路径最小的一种特殊二叉树，所以也称最优二叉树。 在这里不讨论基本概念如如何计算路径等，而只着重于树的创建，具体过程让我们举例而言。
其基本的原理为：将所有节点一开始都视为森林，每次从森林中选取两个根节点权值最小的树合并为一棵新树，新树的根节点大小为两个子节点大小的和，并将这棵新树重新加入到森林中。 如此一来每一轮操作都可以简化为两个基本操作：合并两棵树、插入新树，直到森林中只剩下一棵树，即是哈夫曼树。
以7个节点的权值分别为 1 3 7 9 12 18 25而言 创建的第一步：合并1、3，新增4
创建的第二步：合并4、7，新增11
创建的第三步：合并9、11，新增20
创建的第四步：合并12、18，，新增30
创建的第五步：合并20、25，新增45
合并最后两棵树，得到哈夫曼树
在程序中我们实际运行来创建这棵树后，进行先序遍历的结果如下：
可以看到所有操作是符合结果的
在创建的过程中，很重要的一个过程是：每次都必须从森林中选出节点权值最小的两棵树进行合并，然后插入森林中，这个过程我们可以用最大最小堆的插入和删除来实现，关于最大最小堆的实现和讲解可以看我的这篇客：
以下是具体的代码和注释，部分操作不做解释，看注释就行了
/*时间：2015.7.20名称：哈夫曼树操作：哈夫曼树的创建、哈夫曼树的层序遍历（方便查看）、哈夫曼树的森林的相关操作（最大最小堆的操作）、树的中序遍历简述：通过一个哈夫曼树的森林来创建哈夫曼树、每次建立树都从森林中删除两棵树、然后加入一棵新树、为了使加入和删除更有效率，森林由最大最小堆实现。*/#include<iostream>using namespace std;int cost = 0;const int MAX_CAPACITY = 100000;//森林的最大容纳量enum type{Maxiumn，Miniumn};//代表森林的类型是从大到小还是从小到大typedef struct Node//树的节点的结构{int weight;//定义权重Node* Leftchild;//定义左子树Node* Rightchild; //定义右子树};Node flag;//森林的第一个哨兵节点typedef struct Huffmantree//哈夫曼树森林结构{int size;//森林的当前大小Node *tree[MAX_CAPACITY];//森林的最大容量};Huffmantree Trees;//哈夫曼树的森林void insertMax(Node* insertNode)//从大到小排列的森林的插入（最大堆的插入）{int pos = ++Trees.size;//用临时变量指向末尾，且整体容量加一;for (; Trees.tree[pos / 2]->weight < insertNode->weight; pos /= 2)//每次与对应的父节点进行比较，寻找插入位置{Trees.tree[pos] = Trees.tree[pos / 2];//不符合插入条件就下沉对应的父节点}Trees.tree[pos] = insertNode;//找到插入位置后插入}void insertMin(Node* insertNode)//从小到大排列的森林的插入（最小堆的插入）{int pos = ++Trees.size;//用临时变量指向末尾，且整体容量加一;for (; Trees.tree[pos / 2]->weight>insertNode->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 (child != Trees.size)//防止越界if (Trees.tree[child]->weight < Trees.tree[child + 1]->weight)//选中较大的子节点++child;(lastNode->weight>Trees.tree[child]->weight)break;elseTrees.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;(lastNode->weight<Trees.tree[child]->weight)break;elseTrees.tree[parent] = Trees.tree[child];//上浮较小的节点}Trees.tree[parent] = lastNode;return minNode;}int isFull()//判断森林是否已满{if (Trees.size == MAX_CAPACITY)return 1;;}int isEmpty()//判断森林是否已空{if (Trees.size == 0)return 1;;}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;}
一个能从别人的观念来看事情，能了解别人心灵活动的人，永远不必为自己的前途担心。
