5.7哈夫曼树的基本概念

5.7.1 哈夫曼树的基本概念

效率最高的判别树，就是哈夫曼树（也称最优二叉树）

  • 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径

  • 结点的路径长度：两结点间路径上的分支数。

  • 树的路径长度：从树根到没一个结点的路径长度之和。记作：TL

    • 结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树，但路径长度最短的不一定是完全二叉树

  • 权(weight)：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

  • 结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。

  • 树的带权路径长度：树中所有叶子结点的带权路径长度之和。记作：$\large WPL=\sum\limits_{k=1}^nw_kl_K$(weighted path length)

  • 哈夫曼树：最优树/最优二叉树（带权路径长度最短的树）

    • 因为构造这种树的算法是由哈夫曼教授于1952年提出的，所以被称为哈夫曼树，相应的算法称为哈夫曼算法
    • 满二叉树不一定是哈夫曼树
    • 哈夫曼树中全越大的叶子离根越近
    • 具有相同带权结点的哈夫曼树不唯一

  • 贪心算法：构造哈夫曼树时首先选择权值小的叶子结点

5.7.2 哈夫曼树的构造算法

  • 构造过程

    1. 根据给定的n个权值{$w_1.w_2.w_3,……,w_n$}，构造n棵只有根结点的二叉树，这n棵二叉树构成一个森林F。

    2. 在森林 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左 、右子树上根结点的权值之和

    3. 在森林F中删除这两棵树，同时将新得到的二叉树加入森林中。

    4. 重复2和3的步骤，直到森林中只有一棵树为止，这棵树即为哈夫曼树。

  • 口诀

    1. 构造森林全是根
    2. 选用两小造新树
    3. 删除两小添新人
    4. 重复二三剩单根

  • 总结

    1. 在哈夫曼树算法中，初始时有n棵二叉树，要经过n-1次合并最终形成哈夫曼树

    2. 经过n_1次合并产生n-1个新结点，且这n-1个新结点都是具有两个孩子的分支节点

      可见：哈夫曼树中共有n+n-1=2n-1个结点，且其所有的分支结点的度均不为1.

  • 哈夫曼树构造算法的实现

  • 采用顺序存储结构——一维结构数组 HuffmanTree H;

  • 结点类型定义

    1
    2
    3
    4
    typedef struct{
        int weight;
        int parent,lch,rch;
    }HTNode,*HuffmanTree;
    哈夫曼树中结点下标i weight parent lch rch
    1
    2
    3
    4
    ……
    2n_1

  • 构造哈夫曼树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void CreateHuffmanTree(HuffmanTree &HT,int n){
        if(n<=l) return;
    	m=2*n-l;//数组一共2n-1个元素
    	HT=new HTNode[m+l);//0号单元未用，HT[m]表示根结点
        for(i=l;i<=m;++i){//将2n-1个元素的lch/rch/parent置为0
            HT[i].parent=O;HT[i].lchild=O;HT[i].rchild=O;
        }
        for(i=l;i<=n;++i}cin>>HT[i] .weight;//输入前n个元素weight的值，初始化结束
        for (i=n+l;i<=m;++i)
            Select (HT,i-1,sl,s2);
            HT[sl] .parent=i;HT[s2] .parent=i;
            HT[i] .lchild=sl;HT [i]. rchild=s2;
            HT[i] .weight=HT[sl] .weight+HT[s2] .weight;
    }

  • 例题：

    巳知 w = (5,29,7,8,14,23,3,11), 利用算法 5.10 试构造一棵哈夫曼树， 计算树的带权路径长度， 并给出其构造过程中存储结构HT的初始状态和终结状态。

    哈夫曼树中结点下标i weight parent lch rch
    1 5 9 0 0
    2 29 14 0 0
    3 7 10 0 0
    4 8 10 0 0
    5 14 12 0 0
    6 23 13 0 0
    7 3 9 0 0
    8 11 11 0 0
    9 8 11 1 7
    10 15 12 3 4
    11 19 13 8 9
    12 29 14 5 10
    13 42 15 6 11
    14 58 15 2 12
    15 100 0 13 14

5.7.3 哈夫曼编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
    HC=nuw char*[n+1];										//分配n个字符编码的头指针矢量
    cd=new char[n];											//分配临时存放编码的动态数组空间
    cd[n-1]='\0';											//编码结束符
    for(i=1;i<=n;++i){										//逐个字符求哈夫曼编码
        start=n-1;c=i;f=HT[i].parent;
        while(f!=0){										//从叶子结点开始向上回溯，直到根节点
            --start;										//回溯一次start向前指一个位置
            if
                (HT[f].lchild==c)cd[start]='0';				//结点c是f的左孩子，则生成代码0
            else				 cd[start]='1';				//结点c是f的右孩子，则生成代码1
                c=f;f=HT[f].parent;							//继续向上回溯
        }													//求出第i个字符的编码
        HC[i]=new char[n-start];							//为第i个字符串编码分配空间
        strcpy(HC[i],&cd[start]);							//将求得的编码从临时空间cd复制到HC的当前行中
    }
   delete cd;												//释放临时空间
}															//creatHuffmanCode
  1. 编码：
    1. 输入各字符及其权值
    2. 构造哈夫曼树——HT[i] n+n-1个
    3. 进行哈夫曼编码——HC[i]
    4. 查HC[i]，得到各字符的哈夫曼编码
  2. 解码：
    1. 构造哈夫曼树
    2. 依次读入二进制码
    3. 读入0，则走向左孩子，读入1，则走向右孩子
    4. 一旦到达某叶子时，即可译出字符
    5. 然后再从根出发继续译码，直到结束

6 图

图是一种比线性表和树更为复杂的数据结构。

6.1 图的定义和基本术语

6.1.1 图的定义

  • 图：G=（V.E）

    • V：顶点（数据元素）的有穷非空集合；
    • E：边的有穷集合

  • 无向图：每条边都是无方向的

  • 有向图：每条边都是有方向的

  • 完全图：任意两个点都有一条边相连

  • 稀疏图：有很少边或弧的图（$e<nlog_2n$）

  • 稠密图：有较多边或弧的图

6.1.2 图的基本术语

  • 网，边/弧带权的图

  • 邻接：有边/弧相连的两个顶点之间的关系。

    • 存在（$v_i,v_j$）,则称为$v_i和v_j$互为邻接点
    • 存在<$v_i,v_j$>，则称$v_i$邻接到$v_j$,$v_j$邻接于$v_i$,

  • 关联（依附）：边/弧与顶点之间的关系。

    • 存在（$v_i,v_j$）/<$v_i,v_j$>，则称该边/弧关联于$v_i$和$v_j$

  • 顶点的度：与该顶点相关联的边的数目，记为TD（v）

    • 在有向图中，顶点的度等于该顶点的入度和出度之和。

    • 顶点v的入度是以v为终点的有向边的条数，记作ID（v）

    • 顶点v的出度是以v为始点的有向边的条数，记作OD（v）

  • 路径：连续的边构成的顶点序列

  • 路径长度：路径上边或弧的数目/权值之和

  • 回路（环）：第一个顶点和最后一个顶点相同的路径

  • 简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径

  • 简单回路（环）：除路径起点和终点相同外，其余顶点均不相同的路径

  • 连通图（强连通图）：在无（有）向图G=(V,{E})中，若对任意两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）

  • 权与网：

    • 图中边或弧所具有的相关数称为权，表明从一个顶点到另一个顶点的距离或耗费。
    • 带权的图称为网

  • 子图：设有两个图$G=（V，{E}）、G_1=(V_1,{E_1})$,若$V_1属于V，E_1属于E$则称$G_1是G$的子图

  • 连通分量（强连通分量）

    • 无向图G的极大联通子图称为G的连通分量

      • 极大连通子图意思是：该子图是G联通子图，将G的任何不在该子图汇总的顶点加入，子图不再连通

    • 有向图G的极大连通子图称为G的强连通分量

      • 极大强连通子图意思是: 该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。

    • 极小联通子图：该子图是G的连通子图，在该子图中删除任何一条边，联通子图不再连通

    • 生成树:包含无向图G所有顶点的极小连通子图

    • 生成森林:对非连通图，由各个连通分量的生成树的集合

6.2 案例引入

6.2.1 六度空间理论

理论又称作六度分隔论 (Six Degrees of Separation)。六度空间理论是20世纪60年代由美国的心理学家米格兰姆(Stanley Milgram)提出的，理论指出：“你和任何一个陌生人之间所间隔的人不会超过六个”

6.3 图的类型定义

图的抽象数据类型定义如下：

1
2
3
4
5
ADT Graph{
    数据对象V：具有相同特性的数据元素的集合，称为顶点集。
    数据关系R：R{VR}
    	VR={<V,W>|<V,W>|V,W属于V^p(v,w)}， <v, w>表示从v到w的弧，P (v, w)定义了弧<v, w>的信息
}

  • 基本操作：

    • CreateGraph{&G,V,VR}

      初始条件：V是图的顶点集，VR是图中弧的集合。

      操作结果：按V和VR的定义构造图G。

    • DFSTraverse(G)

      初始条件：图G存在。

      操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点访问一次。

    • BFSTraverse(G)

      初始条件：图G存在。

      操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点访问一次.