创建一颗最优二叉树（哈夫曼树）

哈夫曼树是带权路径最小的一种特殊二叉树，所以也称最优二叉树。 在这里不讨论基本概念如如何计算路径等，而只着重于树的创建，具体过程让我们举例而言。

其基本的原理为：将所有节点一开始都视为森林，每次从森林中选取两个根节点权值最小的树合并为一棵新树，新树的根节点大小为两个子节点大小的和，并将这棵新树重新加入到森林中。 如此一来每一轮操作都可以简化为两个基本操作：合并两棵树、插入新树，直到森林中只剩下一棵树，即是哈夫曼树。

以7个节点的权值分别为 1 3 7 9 12 18 25而言 创建的第一步：合并1、3，新增4

创建的第二步：合并4、7，新增11

创建的第三步：合并9、11，新增20

创建的第四步：合并12、18，新增30

创建的第五步：合并20、25，新增45

合并最后两棵树，得到哈夫曼树

在程序中我们实际运行来创建这棵树后，进行先序遍历的结果如下：

可以看到所有操作是符合结果的

在创建的过程中，很重要的一个过程是：每次都必须从森林中选出节点权值最小的两棵树进行合并，然后插入森林中，这个过程我们可以用最大最小堆的插入和删除来实现，关于最大最小堆的实现和讲解可以看dalao的这篇客： http://blog.csdn.net/ava1anche/article/details/46965675

实现代码

/* 时间：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; //每次都需要判断子节点是否还有子节点，没有的话就上浮保存最后一个节点用于补位 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博客