2019考研计算机数据结构考点：数和二叉树的应用

考研网

根据历年考试经验，数据结构所占分值为45分，所占分值比重较大;而且数据结构部分的知识比较难于理解，为方便考生更好地复习计算机专业课，新东方在线整理了考研计算机数据结构的有关内容，以供大家参考，希望对大家有所帮助。
    　　四、树与二叉树的应用
    1.概念：
    ①树的路径长度是从树根到每一结点的路径长度之和。将树中的结点赋予实数称为结点的权。
    ②结点的带权路径是该结点的路径长度与权的乘积。树的带权路径长度又称树的代价，是所有叶子的带权路径长度之和。带权路径长度最小的二叉树称最优二叉树(哈夫曼树)。
    3具有2n-1个结点其中有n个叶子，并且没有度为1的分支结点的树称为严格二叉树。
    ④对字符集编码时，要求字符集中任一字符的编码都不是其它字符的编码前缀，这种编码称前缀码。
    5字符出现频度与码长乘积之和称文件总长;字符出现概率与码长乘积之和称平均码长;
    6使文件总长或平均码长最小的前缀码称最优前缀码
    ⑦利用哈夫曼树求最优前缀码，左为0，右为1。编码平均码长最小;没有叶子是其它叶子的祖先，不可能出现重复前缀。
   

    2.哈夫曼树构造算法)
    ①根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。
    ②在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左右子树上根结点的权值之和。
    3在F中删除这两棵树，同时将新得到的二叉树加入F中。
    ④ 重复②和3，直到F只含一棵树为止。这棵树便是哈夫曼树。
    3.前缀码
    给定一个码的集合序列，若没有一个序列是另一个序列的前缀，则称这个集合中的码为前缀码。