哈夫曼树

哈夫曼树(Huffman)树又称最优二叉树,是指对于一组带有确定权值的叶子结点所构造的具有带权路径长度最短的二叉树。从树中一个结点到另一个结点之间的分支构成了两结点之间的路径，路径上的分支个数称为路径长度。二叉树的路径长度是指由根结点到所有叶子结点的路径长度之和。如果二叉树中的叶子结点都有一定的权值，则可将这一概念拓展:设二叉树具有n个带权值的叶子结点,则从根结点到每一个叶子结点的路径长度与该叶子结点权值的乘积之和称为二叉树路径长度,记做：

WPL=W1L1+W2L2+......+WnLn;

其中：n为二叉树中叶子结点的个数；Wk为第k个叶子的权值;Lk为第k个叶子结点的路径长度。

 

若给定n个权值，如何构造一棵具有n个给定权值叶子结点的二叉树，使得其带权路径长度WPL最小？哈夫曼根据"权值大的结点尽量靠近根"这一原则，给出了一个带有一般规律的算法，称为"哈夫曼"算法，哈夫曼算法如下： 

(1)根据给定n个权值{w1,w2,....,wn}构成n棵二叉树的集合F={T1,T2,.....,Tn};其中,每棵二叉树Ti(1<=i<=n)只有一个带权值wi的根结点,其左、右子树均为空。

(2)在F中选取两棵根结点权值最小的二叉树作为左、右子树来构造一棵新的二叉树,且置新的二叉树根结点权值为其左右子树根结点的权值之和。

(3)在F中删除这两棵树,同时将生成新的二叉树加入到F中。

(4)重复(2)(3)，直到F中只剩下一棵二叉树加入到F中。

 

从哈夫曼算法可以看出,初始化共有n棵二叉树,且均只有一个根结点。在哈夫曼树的构造过程中,每次都是选取两棵根结点权值最小的二叉树合并成一棵新的二叉树,为此需要增加一个结点作为新的根结点,而这两棵权值最小的二叉树最终合并成一棵新的二叉树,为此需要增加一个结点作为新二叉树的根结点,而这两棵权值最小的二叉树则作为根结点的左、右子树。由于要进行n-1次合并才能使初始化的n棵二叉树最终合并为一棵二叉树,因此n-1次合并共产生了n-1个新结点,即最终生成的哈夫曼树共有2n-1个结点。由于每次都是将两棵权值最小的二叉树合并生成一棵新二叉树,所以生成的哈夫曼树中没有度为1的结点:并且,两棵权值最小的二叉树合并生成一棵新的二叉树,所以生成的哈夫曼树中没有度为1的结点;并且，两棵权值最小的二叉树那棵作为作为左子树、那棵作为右子树，哈夫曼算法并没有要求,故最终构造出来的哈夫曼树并不唯一，但是最小的WPL值是唯一的。所以，哈夫曼具有如下几个特点：

(1)对给定的权值，所构造的二叉树具有的最小WPL;

(2)权值大的结点离根近，权值小的结点离根远;

(3)所生成的二叉树不唯一

(4)没有度为1的结点

 

        哈夫曼树与哈夫曼编码1

概述

 为了构造哈夫曼树,首先修改二叉树的存储结构。哈夫曼树除了二叉树原有的数据域data和左、右孩子指针域*lchild、*rchild外,还增加了一个指针域*next,即哈夫曼树的结点同时又是单链表的结点。在输入哈夫曼树叶子结点权值时,我们将这些权值结点链成一个升序链表。在构造哈夫曼树时,每次取升序单链表的前两个数据结点来构造一个哈夫曼树的树枝结点,同时删去单链表中的这两个数据结点,并将该树枝结点按升序再插入到单链表中。这种构造哈夫曼树树枝结点的过程一直持续到单链表为空为止，且最后生成的树枝结点即为哈夫曼树的树根结点。

 对所生成的哈夫曼树,我们用二叉树后序非递归方法遍历这棵哈夫曼树，遍历到叶结点时输出该叶结点的值及对应的哈夫曼编码。

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 30

typedef struct node
{
    int data;//结点数据
    struct node *lchild,*rchild;//哈夫曼树的左右孩子指针
    struct node *next;//哈夫曼树的结点同时又是单链表的结点，next为单链表的结点指针
}BSTree_Link;//二叉树及单链表结点类型

BSTree_Link *CreateLinkList(int n)//根据叶子结点的权值生成一个升序单链表
{
    BSTree_Link *link,*p,*q,*s;
    int i;
    link=(BSTree_Link*)malloc(sizeof(BSTree_Link));//生成单链表的头结点
    s=(BSTree_Link*)malloc(sizeof(BSTree_Link));//生成单链表的第一个数据结点，同时也是哈夫曼树的叶结点
    scanf("%d",&s->data);//输入叶子结点的权值
    s->lchild=NULL;
    s->rchild=NULL;//置左、右孩子指针为空的叶结点标志
    s->next=NULL;//置单链表链尾结点标志
    link->next=s;
    for(i=2;i<=n;i++)//生成单链表剩余的n-1个数据结点
    {
        s=(BSTree_Link*)malloc(sizeof(BSTree_Link));//生成一个数据结点
        scanf("%d",&s->data);//输入叶子结点的权值
        s->lchild=NULL;
        s->rchild=NULL;//置左右孩子指针为空的叶结点标志
        q=link;//将该数据结点按升序插入到单链表中
        p=q->next;
        while(p!=NULL)
            if(s->data>p->data)//查找插入位置
            {
                q=p;
                p=p->next;
            }
            else//找到插入位置后进行插入
            {
                q->next=s;
                s->next=p;
                break;
            }
            if(s->data>q->data)//插入到链尾的处理
            {
                q->next=s;
                s->next=p;
            }
    }
    return link;//返回升序单链表的头指针结点
}

void print(BSTree_Link *h)//输出单链表
{
    BSTree_Link *p;
    p=h->next;
    while(p!=NULL)
    {
        printf("%d,",p->data);
        p=p->next;
    }
    printf("
");
}

BSTree_Link *HuffTree(BSTree_Link *link)//生成哈夫曼树
{
    BSTree_Link *p,*q,*s;
    while(link->next!=NULL)//当单链表的数据结点非空时
    {
        p=link->next;//取出升序链表中的第一个数据结点
        q=p->next;//取出升序链表中的第二个数据结点
        link->next=q->next;//使头结点的指针指向单链表的第三个数据结点
        s=(BSTree_Link*)malloc(sizeof(BSTree_Link));//生成哈夫曼树的树枝结点
        s->data=p->data+q->data;//该树枝结点的权值为取出的二个数据结点权值之和
        s->lchild=p;//取出的第一个数据结点作为该树枝结点的左孩子
        s->rchild=q;//取出的第二个数据结点作为该树枝结点的右孩子
        q=link;//将该树枝结点按升序插入到单链表中
        p=q->next;
        while(p!=NULL)
            if(s->data>p->data)
            {
                q=p;
                p=p->next;
            }
            else
            {
                q->next=s;
                s->next=p;
                break;
            }
            if(q!=link&&s->data>q->data)//插入到链尾的处理，如果q等于link则链表为空，此时*s即为根结点
            {
                q->next=s;
                s->next=p;
            }
    }
    return s;//当单链表为空时，最后生成的树枝结点即为哈夫曼树的根节点
}

void Preorder(BSTree_Link *p)//先序遍历二叉树
{
    if(p!=NULL)
    {
        printf("%4d",p->data);//访问根结点
        Preorder(p->lchild);//访问左子树
        Preorder(p->rchild);//访问右子树
    }
}

void Inorder(BSTree_Link *p)//中序遍历二叉树
{
    if(p!=NULL)
    {
        Preorder(p->lchild);//访问左子树
        printf("%4d",p->data);//访问根结点
        Preorder(p->rchild);//访问右子树
    }
}
void HuffCode(BSTree_Link *p)//后序遍历哈夫曼树并输出哈夫曼树编码
{
    BSTree_Link *stack[MAXSIZE],*q;
    int b,i=-1,j=0,k,code[MAXSIZE];
    do//后序遍历二叉树
    {
        while(p!=NULL)//将*p结点左分支上的左孩子入栈
        {
            if(p->lchild==NULL&&p->rchild==NULL)
            {
                printf("key=%3d,code:",p->data);//输出叶结点信息
                for(k=0;k<j;k++)//输出该叶结点的哈夫曼编码
                    printf("%d",code[k]);
                printf("
");
                j--;
            }
            stack[++i]=p;//指向当前结点的指针p入栈
            p=p->lchild;//p指向*p的左孩子
            code[j++]=0;//对应的左分支置编码0
        }
        //栈顶结点已没有左孩子或其左子树上的结点都已访问过
        q=NULL;
        b=1;//置已访问过的标记
        while(i>=0&&b)//栈stack不空且当前栈顶结点的左子树已经遍历过
        {
            p=stack[i];//取出当前栈顶存储的结点指针
            if(p->rchild==q)//当前栈顶结点*p无右孩子或*p的右孩子已访问过
            {
            i--;
            j--;
            q=p;//q指向刚访问过的结点*p
            }
    else//当前栈顶结点*p有右子树
        {
            p=p->rchild;//p指向当前栈顶结点*p的右孩子结点
            code[j++]=1;//对应的右分支置编码1
            b=0;//置右孩子结点未遍历过其右子树标记
            }
        }
    }while(i>=0);//当栈stack非空时继续遍历
}

void main()
{
    BSTree_Link *root;
    int n;
    printf("Input number of keys
");//输入叶子结点的个数
    scanf("%d",&n);
    printf("Input keys:
");//输入n个叶子结点的权值
    root=CreateLinkList(n);//根据叶子结点的权值生成一个升序单链表
    printf("Output list:
");//输出所生成的升序单链表
    print(root);
    root=HuffTree(root);//生成哈夫曼树
    printf("Inorder output HuffTree:
");//先序遍历输出哈夫曼树各结点的值
    Inorder(root);
    printf("
");
    printf("Preorder output HuffTree:
");//先序遍历输出哈夫曼树各结点的值
    Preorder(root);
    printf("
");
    printf("Output Code  of HuffTree:
");//后序遍历哈夫曼树构造并输出哈夫曼编码
    HuffCode(root);
}

说明：例如，对8个权值分别为7,19,2,6,32,3,21,10的叶子结点，生成的哈夫曼树由树根到树叶路径上标识的哈夫曼树示意图：

打印结果：