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

大家好，欢迎来到IT知识分享网。

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

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

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

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

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

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

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

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

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

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

在创建的过程中，很重要的一个过程是：每次都必须从森林中选出节点权值最小的两棵树进行合并，然后插入森林中，这个过程我们可以用最大最小堆的插入和删除来实现，关于最大最小堆的实现和讲解可以看我的这篇客：
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;
}