数据结构第五周笔记——树(下2)(慕课浙大版本--XiaoYu)

5.2 哈夫曼树与哈夫曼编码

5.2.1 什么是哈夫曼树(Huffman Tree)

[例]将百分制的考试成绩转换成五分制的成绩

if(score<60 ) grade=1;

elseif(score<70) grade=2;

elseif(score<80) grade=3;

elseif(score<90) grade=4;

elsegrade=5;

上述代码中，其实对应着就有一棵树，如下图：

优化后的效率：

if(score<80)

{

   if(score<70 )

       if(score<60) grade=1;

   elsegrade=2;

}elseif(score<90 )grade=4;

elsegrade=5;

如何根据结点不同的查找频率构造更有效的搜索树？

哈夫曼树的定义

最优二叉树或哈夫曼树就是WPL最小的二叉树

一棵二叉树每一个叶结点的频率或者权重乘以这个叶结点到根结点的这个路径的长度就是带权路径的长度

权值 = 频率

[例]有五个叶子结点，它们的权值为{1，2，3，4，5}，用此权值序列可以构造出形状不同的多个二叉树

是50

5.2.2 哈夫曼树的构造

1. 每次把权值最小的两颗二叉树合并
   
2. 网络异常，图片无法展示

   |
   
   
3. 代码实现(如何选取两个最小的？)

typedefstructTreeNode*HuffmanTree;

structTreeNode{

   intWeight;

   HuffmanTreeLeft,Right;

}

HuffmanTreeHuffman(MinHeapH)

{

   //假设H->Size个权值已经存在H->Elements[]->Weight里

   inti; HuffmanTreeT;

   BuildMinHeap(H);//将H->Elements[]按权值调整为最小堆

   for(i=1;i<H->Size; i++){//做H->Size-1次合并

       T=malloc(sizeof(structTreeNode));//建立新结点

       T->Left=DeleteMin(H);//从最小堆中删除一个结点，作为新T的左子结点

       T->Right=DeleteMin(H);//从最小堆中删除一个结点，作为新T的右子结点

       T->Weight=T->Left->Weight+T->Right->Weight;//计算新权值

       Insert(H,T);//将新T插入最小堆

   }

   T=DeleteMin(H);

   returnT;

}

整体复杂度为O(NlogN)

1. 哈夫曼树的特点：

1. 没有度为1的结点;
   
2. n个叶子结点的哈夫曼树共有2n-1个结点

1. n0：叶结点总数
   
2. n1：只有一个儿子的结点总数
   
3. n2：有2个儿子的结点总数
   
4. n2 = n0 - 1
   

3. 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树;
   
4. 网络异常，图片无法展示

   |
   
   

5.2.3 哈夫曼编码

给定一段字符串，如何对字符进行编码，可以使得该字符串的编码存储空间最少？

分析：

1. 用等长ASCII编码：58×8 = 464位
   
2. 用等长3位编码：58×3 = 174位;
   
3. 不等长编码：出现频率高的字符用的编码短些，出现频率低的字符则可以编码长些？
   

怎么进行不等长编码？

如何避免二义性(就是你这个编码不止一个意思)

1. 前缀码prefix code：任何字符的编码都不是另一字符编码的前缀

1. 可以无二义地解码(你的这个编码不能是其他编码的前缀)
   

2. 二叉树用于编码：

1. 左右分支：0、1
   
2. 字符只在叶结点上
   
3. 网络异常，图片无法展示

   |
   
   
4. 网络异常，图片无法展示

   |
   
   
5. 网络异常，图片无法展示

   |
   
   
6. 怎么构造一颗编码代价最小的二叉树？

1. 网络异常，图片无法展示

   |
   
   

小测验：哈夫曼树

5.3 集合及运算

5.3.1 集合的表示及查找

1. 集合运算：交，并，补，差，判定一个元素是否属于某一集合
   
2. 并查集：集合并、查某元素属于什么集合
   
3. 并查集问题中集合存储如何实现？

1. 可以用树结构表示集合，树的每个结点代表一个集合元素
   
2. 网络异常，图片无法展示

   |
   对这样三棵树的存储方法

1. 采用数组存储形式
   
2. 网络异常，图片无法展示

   |
   
   
3. 上图中没有父节点的用负数来表示，Parent是它父节点的下标
   

[例]：有10台电脑{1，2，3，.....，9，10}，已知下列电脑之间已经实现了连接：

1和2、2和4、3和5、4和7、5和8、6和9、6和10

问：2和7之间，5和9之间是否是连通的？

2和7是连通的，5和9不连通

1. 网络异常，图片无法展示

   |

集合运算

(1)查找某个元素所在的集合(用根结点表示)

intFind(SetTypeS[],ElementTypeX)

{

   //在数组S中查找值为X的元素所属的集合

   //MaxSize是全局变量，为数组S的最大长度

   inti;

   for(i=0;i<MaxSize&&S[i].Data!=X; i++);

   if(i>=MaxSize) return-1;//未找到X,返回-1

   for(;S[i].Parent>=0; i=S[i].Parent);//Parent的值为-1的时候就是找到根结点。i = S[i].Parent：原本指向i的位置现在跳到了s[i].Parent

   returni;//找到X所属集合，返回树根结点在数组S中的下标

}

5.3.2 集合的并运算

(2)集合的并运算

1. 分别找到X1和X2两个元素所在集合树的根结点
   
2. 如果它们不同根，则将其中一个根结点的父结点指针设置成另一个根结点的数组下标

1. Union实现代码
   

voidUnion(SetTypeS[ ],ElementTypeX1,ElementTypeX2 )

{

   intRoot1,Root2;

   Root1=Find(S,X1);//得到X1与X2对应的树根

   Root2=Find(S,X2);

   if( Root1!=Root2 ) S[Root2].Parent=Root1;//判断如果不是本身就是同一个集合的，如果是同一个集合的话就不需要做这个并的操作。不同则合并

}

1. 为了改善合并以后的查找性能，可以采用小的集合合并到相对大的集合中。(修改Union函数)。也许树的高度不会增加

小测验：集合

已知a、b两个元素均是所在集合的根结点，且分别位于数组分量3和2位置上，其parent值分别为-3,-2。问：将这两个集合按集合大小合并后，a和b的parent值分别是多少？

-5，3

集合的定义与并查

#define MAXN 1000                  /* 集合最大元素个数 */

typedefintElementType;           /* 默认元素可以用非负整数表示 */

typedefintSetName;               /* 默认用根结点的下标作为集合名称 */

typedefElementTypeSetType[MAXN]; /* 假设集合元素下标从0开始 */

voidUnion( SetTypeS, SetNameRoot1, SetNameRoot2 )

{ /* 这里默认Root1和Root2是不同集合的根结点 */

   /* 保证小集合并入大集合 */

   if ( S[Root2] <S[Root1] ) { /* 如果集合2比较大 */

       S[Root2] +=S[Root1];     /* 集合1并入集合2  */

       S[Root1] =Root2;

   }

   else {                         /* 如果集合1比较大 */

       S[Root1] +=S[Root2];     /* 集合2并入集合1  */

       S[Root2] =Root1;

   }

}

SetNameFind( SetTypeS, ElementTypeX )

{ /* 默认集合元素全部初始化为-1 */

   if ( S[X] <0 ) /* 找到集合的根 */

       returnX;

   else

       returnS[X] =Find( S, S[X] ); /* 路径压缩 */