数据结构与算法 －判定树和哈夫曼树

分类与判定树

判定树是用于描述分类过程的二叉 树，每个非终端结点包含一个条件，对应一次比较；每个终端结点 包含一个种类标记， 对应于一种分类结果。

设有n个学生，现要根据他们的成绩将其划分为5类：

第一类：小于60分，不及格，学生概率为5%；

第二类：大于等于60分，但小于70分，及格，学生概率为15%；

第三类：大于等于70分，但小于80分，中等，学生概率为40%；

第四类：大于等于80分，但小于90分，良好，学生概率为30%；

第五类：大于等于90分，优秀，学生概率为10%；

若按顺序判，得下列判断过程：

因为大多数元素属于中和良，如果按上图这样判断，大多数数据都得通过3至4次判断，这样总的判断次数就多，花费的时间也较多，所以需要对判断树进行改进。

通过对判断树的改进，由于属于中、良的数最多， 而检验它们的判断少了，因此总的判断次数也减少了。

如何构造时间性能最高的判定树？这就是我们要研究的哈夫曼树。

 

哈夫曼树与哈夫曼算法

1. 带权路径长度

将一组带权的实数放在二叉树的每个叶子节点上。该结点的带权路径长度为：结点所占权重乘以结点祖先个数。由带权节点所构成的二叉树的路径长度为：所有带权结点路径长度之和。

如上图所示：a节点的带权路径长度为14，b节点为10，c节点为4，d结点为8，二叉树的路径长度为 36

 

2. 哈夫曼树

带权路径长最小的二叉树即为哈夫曼树，其特征是权大的叶子离根近，权小的叶子离根远。

 如上图所示：第一棵树的带权路径为36，第二棵为46，第三棵为35，所以第三棵树为最优二叉树，即哈夫曼树。

 

3. 哈夫曼算法

生成哈夫曼方法步骤如下：

(1). 将多棵带权的二叉树或节点T按权重从小到大排列形成森林F。

(2). 取森林F中权重最小的二棵生成一棵二叉树T，T为根，T1和T2分别为T的左、右子树，T的权 ＝ T1的权+T2的权。

(3). 将T按从小到大插入到森林F中。

(4). 重复以上操作，至到F＝ T ，成为一棵二叉树，此时，T即为哈夫曼树。

初始森林共有n棵二叉树，每棵树中都仅有一个孤立的结点，要进行n-1次合并才能得到哈夫曼树，每次合并产生一个新结点， 最终由2n-1个结点。

哈夫曼节点的类型定义：

const int n=10;
typedef struct{ 
    // w为结点的权值
    float w; 
    // 父结点和左、右孩子所在数组的下标
    int parent, lchild,rchild; 
}node;

typedef node hfTree[2*n-1];

哈夫曼算法定义步骤：

1. 将表示哈夫曼树的数组T中的2k-1结点初始化；

2. 读入k个权值到数组T的前k个分量中，它们是初始森林中的k个孤立的根结点的权值；

3. 对森林中的树进行k-1次合并，共产生k-1个新结点，依次放入数组T的第i个分量重(k<=i<2*k-1)。每次合并的步骤如下：

(1). 从当前森林的所有结点 T[j](0<=j<=i-1) 中选取具有最小权值和次小权 值的两个根结点，分别用x和y记住这两个根结点在数组T中的下标。

(2). 将根为T[x]和T[y]的两棵树合并，使它们分别成为新结点T[i]的左右孩子，得到一棵以新结点T[i]为根的二叉树。同时修改T[x]和T[y]的双亲域 parent，使其指向新结点T[i]，将T[x]和T[y]的权值相加后作为新结点T[i]的权值。

void Huffman(int k,float w[],hftree T){
    int i,j,x,y;
    float m,n;
    // 初始化状态
    for( i=0;i<2*k-1;i++){
        T[i].parent = -1;
        T[i].lchild = -1;
        T[i].rchild = -1;
        if(i<k){
            T[i].w = w[i]
        }else{
            T[i].w = 0;
        };
    };

    // 构造新的二叉树
    for(i=0;i<k-1;i++){
        // MAX为计算机能表示的一个较大值
        x = 0;y = 0;m = MAX;n = MAX;
        // 找权值最小的两棵二叉树
        for(j=0;j<k+i;j++){
            if((T[j].w<m) && (T[j].parent ==-1)){
                n = m; y = x; m = T[j].w; x = j;
            }else if((T[j].w<n) && (T[j].parent ==-1)){
                n = T[j].w; y = j;
            }
        };
        // 合并成一个新的二叉树
        T[x].parent  = k+i;
        T[y].parent = k+i;
        T[k+i].w = m+n;
        T[k+i].lchild = x;
        T[k+i].rchild = y;
    }
}

 

4. 哈夫曼编码

二叉树中从根到每个叶子都有一条路径，对路径上的各 分支约定指向左子树根的分支表示“0”码，指向右子树 的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，我们可以以此作为通信的二进制编码，这就是哈夫曼编码。

设某通信系统中一个待传输的文本有6个不同字符，它们的出现频率分别是0.5，0.8，1.4，2.2，2.3，2.8，试设计哈夫曼编码。

分析：由题意，共有n=6个不同的字符，字符的频率序列为p={0.5，0.8，1.4，2.2，2.3，2.8}，以这些频率作为权值，构造一棵哈夫曼树，结果如下：