2019考研计算机：数据结构赫夫曼树复习重点

考研网

《数据结构(C语言版)》复习重点在二、三、六、七、九、十章，考试内容两大类：概念，算法，自从计算机专业课统考以后，专业课考试题型分为2类，一类选择题，一类综合应用题。接下来是新东方在线整理的数据结构(C语言版)赫夫曼树复习重点。
    1、赫夫曼树：又称最优树，是一类带权路径长度最短的树。
   

9163154466167928.png

    a) 两个最小数值组成一对，小的在前，大的在后;如上图中2与4最小，2在前，4在后。
    b) 将两个最小数值的和算作一个数，再与其他数重复a)步骤;如上图中2与4的和为6，5与6最小，5在前，6在后。
    c) 最后计算WPL，它等于每个数值乘以从根结点到这个数值的连线个数的积之和;如上图中WPL=2*3+4*3+5*2+7*1=35。
    2、 赫夫曼编码：
    a) 在赫夫曼树上，左分支代表0，右分支代表1。
    b) 由根结点到指定结点的路径(从上到下把0、1连起来)，就是该结点的赫夫曼编码;如上图(d)中a为0，b为10，c为110，d为111。