|
平衡化方法 LL型右旋一次 RR型左旋一次 LR型左旋一次右旋一次 RL型右旋一次左旋一次 哈夫曼树和哈夫曼编码 叶子结点的权值对叶子结点赋予的一个有意义的数值量 二叉树的带权路径长度设二叉树具有n个带权值的叶子结点从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和 哈夫曼树给定一组具有确定权值的叶子结点带权路径长度最小的二叉树 【记】带权路径最小的树 哈夫曼算法基本思想 （）初始化由给定的n个权值{ww…wn}构造n棵只有一个根结点的二叉树从而得到一个二叉树集合F＝{TT…Tn} （）选取与合并在F中选取根结点的权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树这棵新二叉树的根结点的权值为其左右子树根结点的权值之和 （）删除与加入在F中删除作为左右子树的两棵二叉树并将新建立的二叉树加入到F中 （）重复⑵⑶两步当集合F中只剩下一棵二叉树时这棵二叉树便是哈夫曼树 返回《数据结构》考研复习精编 [] [] [] [] [] [] [] [] [] [] |
