精华内容
下载资源
问答
  • 最优二叉树(哈夫曼树)
    千次阅读
    2017-10-29 21:55:54

    (1)树的路径长度: 指从树根到树中每一个结点的路径长度之和。

    (2)在结点数目相同的二叉树中,路径长度最短的是: 完全二叉树。

    (3)结点的权: 在一些应用中,赋予树中结点的一个有某种意义的实数。

    (4)带权路径长度(树的代价):结点到树根的路径  乘以  该结点上的权,

    通常记为:

    注:完全二叉树:除最后一层可能不满以外,其他各层都达到该层节点的最大数,最后一层如果不满,该层所有节点都全部靠左排;

    满二叉树:所有层的节点数都达到最大。

     

    (5)哈夫曼树的原理:

    在构造哈夫曼树的过程中,每次都是选取两棵最小权值的二叉树进行合并,因此使用的是贪心算法。

    (6)给定结点序列<ci,pi>(ci为编码字符,pi为ci的频度),哈夫曼编码的过程如下:

    .用字符ci作为叶子,pi作为ci的权,构造一棵哈夫曼树,并将树中的左分支和右分支分别标记为0和1;

    .将从根到叶子的路径上的标号依次相连,作为该叶子所表示字符的编码。该编码为最优前缀码。

    .求哈夫曼编码的具体实现过程是依次以叶子结点c[i]为出发点,向上回溯至根为止。

    .由于生成的编码与要求的编码反序,将生成的编码先从后往前依次存放在一个临时串中,并设一个指针start指示编码在该串中的首位置。

    .当某字符编码完成时,从临时串的start处将编码复制到该字符相应的位串bits中即可。

    .因为字符集大小为n,故变长编码的长度不会超过n,加上一个结束符“\0“,bits的大小应为n+1。

    (7)前缀码:(不存在一个序列是另一个序列的前缀的情况的)一个序列的集合。

    (8)最优的前缀码:平均码长或文件总长最小的前缀码。

    (9)对文件的压缩效果最佳的编码:最优的前缀码。
    (10)哈夫曼树的应用:可以优化通信管道的利用率。

     

     

    更多相关内容
  • 一、定义一些定义:节点之间的路径长度:在树中从一个结点到另一个结点所经历的分支,构成了这两个结点间的路径上的经过的分支数称为它的路径长度树的路径长度:从树的根节点到树中每一结点的路径长度之和。...

    一、定义

    一些定义:

    节点之间的路径长度:在树中从一个结点到另一个结点所经历的分支,构成了这两个结点间的路径上的经过的分支数称为它的路径长度

    树的路径长度:从树的根节点到树中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。

    结点的权:在一些应用中,赋予树中结点的一个有某种意义的实数。

    结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。

    树的带权路径长度(Weighted Path Length of Tree:WPL):定义为树中所有叶子结点的带权路径长度之和

    如下面的二叉树,叶子节点的权值分别为5、6、2、4、7,的带权路径长度计算:

    5f9c080f35fce34fcdd206a170e95e3a.png

    最优二叉树:从已给出的目标带权结点(单独的结点) 经过一种方式的组合形成一棵树.使树的权值最小.。最优二叉树是带权路径长度最短的二叉树。根据结点的个数,权值的不同,最优二叉树的形状也各不相同。它们的共同点是:带权值的结点都是叶子结点。权值越小的结点,其到根结点的路径越长。

    如,给定4个叶子结点a,b,c和d,分别带权7,5,2和4。构造如下图所示的三棵二叉树(还有许多棵),它们的带权路径长度分别为:

    1335607635_5879.jpg

    (a)WPL=7*2+5*2+2*2+4*2=36

    (b)WPL=7*3+5*3+2*1+4*2=46

    (c)WPL=7*1+5*2+2*3+4*3=35

    其中(c)树的WPL最小,可以验证,它就是哈夫曼树。

    注意:

    ① 叶子上的权值均相同时,完全二叉树一定是最优二叉树,否则完全二叉树不一定是最优二叉树。

    ② 最优二叉树中,权越大的叶子离根越近。

    ③ 最优二叉树的形态不唯一,WPL最小。

    二、构造哈夫曼树

    1) 根据给定的n个权值{w1, w2, w3, w4......wn}构成n棵二叉树的森林 F={T1 , T2 , T3.....Tn},其中每棵二叉树只有一个权值为wi 的根节点,其左右子树都为空;

    2) 在森林F中选择两棵根节点的权值最小的二叉树,作为一棵新的二叉树的左右子树,且令新的二叉树的根节点的权值为其左右子树的权值和;

    3)从F中删除被选中的那两棵子树,并且把构成的新的二叉树加到F森林中;

    4)重复2 ,3 操作,直到森林只含有一棵二叉树为止,此时得到的这棵二叉树就是哈夫曼树。

    构造过程如下图:

    1-120223213KW27.jpg

    三、Java实现

    对指定节点创建哈夫曼树:package com.liuhao.DataStructures;

    import java.util.ArrayDeque;

    import java.util.ArrayList;

    import java.util.List;

    import java.util.Queue;

    public class HuffmanTree {

    public static class Node {

    E data;

    double weight;

    Node leftChild;

    Node rightChild;

    public Node(E data, double weight) {

    super();

    this.data = data;

    this.weight = weight;

    }

    public String toString() {

    return "Node[data=" + data + ", weight=" + weight + "]";

    }

    }

    public static void main(String[] args) {

    List nodes = new ArrayList();

    nodes.add(new Node("A", 40.0));

    nodes.add(new Node("B", 8.0));

    nodes.add(new Node("C", 10.0));

    nodes.add(new Node("D", 30.0));

    nodes.add(new Node("E", 10.0));

    nodes.add(new Node("F", 2.0));

    Node root = HuffmanTree.createTree(nodes);

    System.out.println(breadthFirst(root));

    }

    /**

    * 构造哈夫曼树

    *

    * @param nodes

    * 节点集合

    * @return 构造出来的哈夫曼树的根节点

    */

    private static Node createTree(List nodes) {

    // 只要nodes数组中还有2个以上的节点

    while (nodes.size() > 1) {

    quickSort(nodes);

    //获取权值最小的两个节点

    Node left = nodes.get(nodes.size()-1);

    Node right = nodes.get(nodes.size()-2);

    //生成新节点,新节点的权值为两个子节点的权值之和

    Node parent = new Node(null, left.weight + right.weight);

    //让新节点作为两个权值最小节点的父节点

    parent.leftChild = left;

    parent.rightChild = right;

    //删除权值最小的两个节点

    nodes.remove(nodes.size()-1);

    nodes.remove(nodes.size()-1);

    //将新节点加入到集合中

    nodes.add(parent);

    }

    return nodes.get(0);

    }

    /**

    * 将指定集合中的i和j索引处的元素交换

    *

    * @param nodes

    * @param i

    * @param j

    */

    private static void swap(List nodes, int i, int j) {

    Node tmp;

    tmp = nodes.get(i);

    nodes.set(i, nodes.get(j));

    nodes.set(j, tmp);

    }

    /**

    * 实现快速排序算法,用于对节点进行排序

    *

    * @param nodes

    * @param start

    * @param end

    */

    private static void subSort(List nodes, int start, int end) {

    if (start < end) {

    // 以第一个元素作为分界值

    Node base = nodes.get(start);

    // i从左边搜索,搜索大于分界值的元素的索引

    int i = start;

    // j从右边开始搜索,搜索小于分界值的元素的索引

    int j = end + 1;

    while (true) {

    // 找到大于分界值的元素的索引,或者i已经到了end处

    while (i < end && nodes.get(++i).weight >= base.weight)

    ;

    // 找到小于分界值的元素的索引,或者j已经到了start处

    while (j > start && nodes.get(--j).weight <= base.weight)

    ;

    if (i < j) {

    swap(nodes, i, j);

    } else {

    break;

    }

    }

    swap(nodes, start, j);

    //递归左边子序列

    subSort(nodes, start, j - 1);

    //递归右边子序列

    subSort(nodes, j + 1, end);

    }

    }

    public static void quickSort(List nodes){

    subSort(nodes, 0, nodes.size()-1);

    }

    //广度优先遍历

    public static List breadthFirst(Node root){

    Queue queue = new ArrayDeque();

    List list = new ArrayList();

    if(root!=null){

    //将根元素加入“队列”

    queue.offer(root);

    }

    while(!queue.isEmpty()){

    //将该队列的“队尾”元素加入到list中

    list.add(queue.peek());

    Node p = queue.poll();

    //如果左子节点不为null,将它加入到队列

    if(p.leftChild != null){

    queue.offer(p.leftChild);

    }

    //如果右子节点不为null,将它加入到队列

    if(p.rightChild != null){

    queue.offer(p.rightChild);

    }

    }

    return list;

    }

    }以上代码中的关键步骤包括:

    (1)对list集合中所有节点进行排序;

    (2)找出list集合中权值最小的两个节点;

    (3)以权值最小的两个节点作为子节点创建新节点;

    (4)从list集合中删除权值最小的两个节点,将新节点添加到list集合中

    程序采用循环不断地执行上面的步骤,直到list集合中只剩下一个节点,最后剩下的这个节点就是哈夫曼树的根节点

    四、哈夫曼编码

    根据哈夫曼树可以解决报文编码的问题。假设需要把一个字符串,如“abcdabcaba”进行编码,将它转换为唯一的二进制码,但是要求转换出来的二进制码的长度最小。

    假设每个字符在字符串中出现频率为W,其编码长度为L,编码字符n个,则编码后二进制码的总长度为W1L1+W2L2+…+WnLn,这恰好是哈夫曼树的处理原则。因此可以采用哈夫曼树的构造原理进行二进制编码,从而使得电文长度最短。

    对于“abcdabcaba”,共有a、b、c、d4个字符,出现次数分别为4、3、2、1,相当于它们的权值,将a、b、c、d以出现次数为权值构造哈夫曼树,得到下左图的结果。

    从哈夫曼树根节点开始,对左子树分配代码“0”,对右子树分配“1”,一直到达叶子节点。然后,将从树根沿着每条路径到达叶子节点的代码排列起来,便得到每个叶子节点的哈夫曼编码,如下右图。

    2d4e2b172c055cd4934686d8d2bec3cb.png

    从图中可以看出,a、b、c、d对应的编码分别为0、10、110、111,然后将字符串“abcdabcaba”转换为对应的二进制码就是0101101110101100100,长度仅为19。这也就是最短二进制编码,也称为哈夫曼编码。

    展开全文
  • 提示:文章写完后,目录...我已此为契机,了解一下查找二叉树、完全二叉树、线索二叉树、最优二叉树的一些相关定义(此题结尾会给出答案详解) 一、查找二叉树(二叉排序树) 二叉排序树的定义: 1、若结点的左子树.


    前言

    2021年上半年 软件设计师 上午试卷中有这样一道题

    58.当二叉树的结点数目确定时,________的高度一定是最小的。
    A.二叉排序树 B.完全二叉树 C.线索二叉树 D.最优二叉树

    我已此为契机,来了解一下查找二叉树完全二叉树线索二叉树最优二叉树的一些相关定义(此题结尾会给出答案详解)

    一、查找二叉树(二叉排序树)

    二叉排序树的定义:
    1、若根结点的左子树非空时,左子树上的所有结点均要小于根节点;
    2、若根结点的右子树非空时,右子树上的所有结点均要大于根节点;
    3、根结点的左、右子树本身又各是一颗二叉排序树

    二叉排序树示例如图所示:
    在这里插入图片描述

    删除与插入
    (一)插入结点
    1、若查找二叉树为空树,则已要插入的新结点作为它的根节点
    2、如果要插入的结点已存在,则不再插入。如上图若想要插入关键字为32的结点,已经存在了,就不进行插入操作。
    3、将要插入的结点键值与插入后的父结点键值比较,如果小于则插入左子树,反之插入右子树中

    (二)删除结点
    1、若待删除结点是叶子结点(即没有左右孩子),则直接删除。例如上图中的88,,直接删除88元素。
    2、若待删除结点只有左子树而无右子树,直接将其左孩子与待删除结点的父结点直接连接,例如:41
    在这里插入图片描述
    3、若待删除结点只有右子树而无左子树,直接将其右孩子与待删除结点的父结点直接连接,例如:66
    在这里插入图片描述
    4、若待删除结点p同时存在左、右子树,可以从其左子树选择键值最大的结点s,用结点s的值代替结点p的值,然后删除结点s,例如删除:54
    在这里插入图片描述

    二、完全二叉树

    定义:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h
    层若干结点靠左对齐,就说它是完全二叉树。

    如下图所示:
    在这里插入图片描述
    上图两种都是完全二叉树,接下来我再给出不是完全二叉树的图,好做个对比
    在这里插入图片描述
    a和b都不满足完全二叉树的定义,a是因为第h层结点不满足左靠齐;b是因为除了第h层外,其它层结点个数结点未达到最大。

    需要补充一点,满二叉树也是一颗完全二叉树,但是完全二叉树不一定是满二叉树

    满二叉树定义
    一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的深度为K,且结点总数是(2^k) -1,则它就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点,要么它有两个子结点,但是反过来不成立,因为完全二叉树也满足这个要求,但不是满二叉树)

    在这里插入图片描述

    三、线索二叉树

    定义:在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索二叉树的过程称为对二叉树进行线索化。

    单看定义还是有点抽象,我们先来了解一下为什么要有线索二叉树呢?
    看下图中,我们发现在这颗树上存在着很懂指向null的指针(红色线),线索二叉树就是要让这些指针能够很好的运用上。
    在这里插入图片描述
    在二叉树存储结构中,因为每个结点中只有指向其左、右孩子的指针,所以从任一结点触发只能找到该节点的左、右孩子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。但是若想在每个结点中增加指向其前驱和后继结点的指针,将降低存储空间的效率,所以引入线索二叉树。

    对于n个结点的二叉树,在二叉链存储结构中有n+1个空链域(证明略),利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针,这些指针称为线索,加上线索的二叉树称为线索二叉树。

    总结:线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题,解决了二叉链表找左、右孩子困难的问题。

    根据线索性质的不同,线索二叉树可分为前序线索二叉树中序线索二叉树后序线索二叉树三种。

    接下来介绍其中之一 ----- 前序线索二叉树
    在这里插入图片描述
    前序二叉树,顾名思义,就是按照前序遍历的方式。。。其中,左子树结点的指针指向当前遍历当中的前序结点。右子树结点的指针指向当前遍历的后序结点。比方说,在前序遍历模式中,遍历的顺序是按照“根–左--右”的方式进行的,好比在上图的BDE中在这里插入图片描述
    前序遍历的方式,依次访问的是B、D、E。所以结点D的左孩子指针指向前序B结点,右孩子指针指向后序E结点,如上图所示。

    记住前/中/后序遍历的口诀:“前”代表根先遍历,“中”代表根中间时刻遍历,“后”代表根最后遍历。

    这样表示可能还不够直观,我们把上面前序线索二叉树的示例转换为前序遍历结果为:ABDEHCFGI
    在这里插入图片描述
    从图中可以就可以验证之前的结论,线索链表很好的解决了在某种遍历方式下查找二叉树结点的前驱和后继结点困难的问题,中序、后序线索二叉树就不展开讲了,原理都是一样的。

    四、最优二叉树(哈夫曼树)

    定义:给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

    基本概念:
    哈夫曼树又称为最优树.
    1、路径和路径长度
    在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。
    2、结点的权及带权路径长度
    若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。
    3、树的带权路径长度
    树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL。

    依旧结合图例来分别演示树的路径长度带权路径长度树的带权路径长度(树的代价)如何计算
    在这里插入图片描述

    • 树的路径长度就是图中每一根线(每根线长为1)累加起来的长度。
    • 权就不必多说了,就是每个结点中所标记的值,就是该结点权值。
    • 带权路径长度,就是路径的长度先求出来,再乘以权值。即:带权路径长度=该结点路径长度×该结点权值。比如,结点2的带权路径长度等于=(1+1)×2=4
    • 树的带权路径长度,就是所有所有叶子结点的带权路径长度之和。例如上图,WPL=2×2+3×4+3×8+1×1=41。

    哈夫曼树的构造
    定义
    假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
    (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
    (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
    (3)从森林中删除选取的两棵树,并将新树加入森林;
    (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。

    先来一个简单一点的例子,将给定权值W=(1,3,5,7)来构造一颗哈夫曼树,按照上述的算
    首先要找到两个权值最小的节点,来构造一颗新的二叉树,如下
    在这里插入图片描述
    现在还剩下的权值是:4,5,7
    继续上面的操作
    在这里插入图片描述
    最终这颗树就构造完了
    在这里插入图片描述
    这棵树的带权路径长度为WPL=3×1+3×3+2×5+1×7=29

    哈夫曼编码
    定义:哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。

    使用场景:在数据通信中,经常需要将传送的文字转换为二进制字符0和1组成的二进制字符串,称这个过程为编码。显然,我们希望电文编码的代码长度最短。哈夫曼树可用于构造使电文编码的代码长度最短的编码方案。

    !!!做题时,只需要记住的一点:哈夫曼树中的左分支为0、右分支为1。则从根结点到每个叶子结点所经过的分值对应的0和1组成的序列便是该结点对应的字符的编码。这样的编码成为哈夫曼编码

    直接上题!!

    【2021年下半年 软件设计师 上午试卷】已知一个文件中出现的各字符及其对应的频率如下表所示。采用Huffman编码,则该文件中字符a和c的码长分别为__(64)A__。若采用Huffman编码,则编码序列110001001101对应的字符应为__(65)A__。
    在这里插入图片描述
    (64)A. 1和3 B. 1和4 C. 3和3 D. 3和4
    (65)A. face B. bace C. acde D. fade

    解题过程:
    1、先构造一颗哈夫曼树
    根据题干所给出的权值(频率)={45,13,12,16,9,5}进行构造
    每次选取权值最小的两个结点构造一颗二叉树,并将根结点放入权值序列中,一直重复这个步骤即可。
    下面是最终构造出来的树↓
    在这里插入图片描述
    然后以“哈夫曼树中的左分支为0、右分支为1”规则,进行编码。
    在这里插入图片描述
    这样就可以求得每个字符的编码:a(0),b(101),c(100),d(111),e(1101),f(1100),从而可知编码序列“110001001101”代表的是字符“face”

    在这颗树的构造上有一个容易出错的地方,一定要记得在每次构造树的时候选出两个权值最小的来构造一颗二叉树。比方说在5、9和14这颗树构造完后,还剩下的权值则为{12,13,14,16,45},那么有些人会只选取12继续和14一起组成一颗二叉树,接下来的树就会变为大致这样。
    在这里插入图片描述
    一定要记得每轮选取的是最小两个,所以我们在这轮选取的应该是12和13,构造一颗12、13、25的树,在进行下一轮最小两权值的构造,以此类推,最终就能构造一颗真正的哈夫曼树!


    文章大致内容就这么多,回到开头题目,就变得很清晰了。(虽然内容已经偏题~)

    当二叉树的结点数目确定时,__完全二叉树___的高度一定是最小的。
    因为,完全二叉树每层都尽量排满,因此树的高度相对其他来说一定是最小的。查找二叉树跟要插入的值大小相关,和树的高度不直接相关。线索二叉树是通过增设指针去保存结点的前驱后继关系,无法保证树的高度最小。最优二叉树是带权路径长度最短的一种二叉树,和树的高度没有必然的联系。


    参考视频:https://www.bilibili.com/video/BV1xA411T7UM?p=15

    参考资料:《数据结构教程(第版)》

    展开全文
  • 简述最优二叉树(赫夫曼树)

    千次阅读 2020-11-16 19:59:32
    给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离较近。 哈夫曼树被...

    什么是哈夫曼树:
    给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

    哈夫曼树被用来进行哈夫曼编码,下面来介绍哈夫曼编码:
    假设需要传送的电文为“ABACCDA”,它只有四种字符,只需要用两个字符的串就可以分辨,假设A,B,C,D的编码分别是00,01,10,11,则该电文的编码便是:“00010010101100”,总长为14位,对方接收时,只需要二位一分就可以进行译码。在现实中尽可能希望编码总长尽可能短,如果采用对每个字符设计长度不同的编码,那么让电文中出现次数较多的字符尽可能采用短的编码,那么电文总长就可以减少。比如设计A,B,C,D的编码为0,00,1,01,则上述电文可转换为:“000011010”,总长为9。但是这样的电文无法翻译,例如“0000”就有多种译法。或是“AAAA”,或者是“ABA”,又或者是“BB”等,因此,若要设计长度不等的编码,则必须是任一个字符的编码都不是另一个字符的编码的前缀,这种编码称为前缀编码

    那么如何得到电文长度最短的二进制前缀编码呢?设计电文总长度最短的二进制前缀编码即为以n种字符出现的频率做权值,设计一棵哈夫曼树的问题,由此得到的二进制前缀编码称为哈夫曼码

    下面就来说说如何创建一棵赫夫曼树。

    对于如何构造哈夫曼树,哈夫曼最早就给出了一个带有一般规律的算法,俗称哈夫曼算法:

    (1)根据给定的n个权值{ w 1 w_1 w1, w 2 w_2 w2……, w n w_n wn}构成n棵二叉树的集合F = { T 1 T_1 T1, T 2 T_2 T2……, T n T_n Tn},其中每棵二叉树中的 T i T_i Ti中只有一个带权为 w i w_i wi的根节点,其左右子树均为空。

    (2)在F中选取两棵根节点的权值最小的树作为左右子树构成一棵新的二叉树,且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和;

    (3)在F中删除这两棵树,同时将新得到的二叉树加入F中;

    (4)重复(2),和(3)步骤,直到F只含有一棵树为止。则这棵树就是哈夫曼树。

    下面来看一个简单的案例:字母{a,b,c,d},出现的次数为{7,5,2,4},构建出哈夫曼树:

    我们按照哈夫曼算法来构建哈夫曼树。
    第一步选取其中最小的两个构建成二叉树:
    在这里插入图片描述
    第二步将6添加至权值序列中,删除之前的2和4:
    权值列表变成{7,5,6}
    重复第一二步,直到构建完成:
    在这里插入图片描述
    权值列表:{7,11}
    在这里插入图片描述
    至此,哈夫曼树构建完成:
    在这里插入图片描述
    带权路径长度为:WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35
    当然,哈夫曼树不是唯一的,比如上面的哈夫曼树也可以为:
    在这里插入图片描述
    带权路径长度为:WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35

    但是不管哈夫曼树怎样构造,最短带权路径长度只有一个。

    由于哈夫曼树中没有度为1的结点(又叫做正则二叉树),则一棵有n个叶子结点的哈夫曼树共有2n-1个结点,可以存储在哎一个大小为2n-1的一维数组中。

    下面来看一个复杂的例题:
    已知某系统的通信联络中只可能出现8中字符,次数别为w= {5,29,7,8,14,23,3,11}
    按照哈夫曼算法来构建哈夫曼树:
    权值列表:{3,5,7,8,11,14,23,29}
    在这里插入图片描述

    权值列表:{7,8,8,11,14,23,29}
    在这里插入图片描述
    权值列表:{8,11,14,15,23,29}
    在这里插入图片描述
    权值列表:{14,1519,23,29}
    在这里插入图片描述
    权值列表:{19,23,29,29}
    在这里插入图片描述
    权值列表:{29,2942}
    在这里插入图片描述
    权值列表:{4258}
    在这里插入图片描述
    至此,哈夫曼树已经构建完成。我们来算算其带权路径:
    WPL = 23x2 + 11x3 + 5x4 + 3x4 + 29x2 + 14x3 + 7x4 + 8x4 = 271
    我们规定向左为0,向右为1,则,该哈夫曼树为:
    在这里插入图片描述
    则这八种字符的编码分别为:{0110,10,1110,1111,110,00,011,010}

    当然构造出的哈夫曼树不止一种,也可能为:
    在这里插入图片描述该图的带权路径为:
    WPL = 29x2 + 14x3 + 7x4 + 3x5 + 5x5 + 23x2 + 8x3 + 11x3 = 271
    由此看出,哈夫曼树可能不同,但是带权路径一定是同一个最小值。

    已经了解了思想了,现在该如何实现了。

    class Node:
        def __init__(self, name, weight):
            self.name = name #节点名
            self.weight = weight #节点权重
            self.left = None #节点左孩子
            self.right = None #节点右孩子
            self.father = None # 节点父节点
        #判断是否是左孩子
        def is_left_child(self):
            return self.father.left == self
    
    #创建最初的叶子节点
    def create_prim_nodes(data_set, labels):
        if(len(data_set) != len(labels)):
            raise Exception('数据和标签不匹配!')
        nodes = []
        for i in range(len(labels)):
            nodes.append( Node(labels[i],data_set[i]) )
        return nodes
    
    
    # 创建huffman树
    def create_HF_tree(nodes):
        #此处注意,copy()属于浅拷贝,只拷贝最外层元素,内层嵌套元素则通过引用,而不是独立分配内存
        tree_nodes = nodes.copy()
        while len(tree_nodes) > 1: #只剩根节点时,退出循环
            tree_nodes.sort(key=lambda node: node.weight)#升序排列
            new_left = tree_nodes.pop(0)
            new_right = tree_nodes.pop(0)
            new_node = Node(None, (new_left.weight + new_right.weight))
            new_node.left = new_left
            new_node.right = new_right
            new_left.father = new_right.father = new_node
            tree_nodes.append(new_node)
        tree_nodes[0].father = None #根节点父亲为None
        return tree_nodes[0] #返回根节点
    
    #获取huffman编码
    def get_huffman_code(nodes):
        codes = {}
        for node in nodes:
            code=''
            name = node.name
            while node.father != None:
                if node.is_left_child():
                    code = '0' + code
                else:
                    code = '1' + code
                node = node.father
            codes[name] = code
        return codes
    
    
    if __name__ == '__main__':
        labels = ['A','B','C','D','E','F','G','H']
        data_set = [5,29,7,8,14,23,3,11]
        nodes = create_prim_nodes(data_set,labels)#创建初始叶子节点
        root = create_HF_tree(nodes)#创建huffman树
        codes = get_huffman_code(nodes)#获取huffman编码
        #打印huffman码
        for key in codes.keys():
            print(key,': ',codes[key])
    
    

    运行结果:

    A :  0001
    B :  10
    C :  1110
    D :  1111
    E :  110
    F :  01
    G :  0000
    H :  001
    

    代码参考自:哈夫曼树代码

    展开全文
  • 算法之最优二叉树搜索

    千次阅读 2020-12-17 20:54:00
    节点从小到大排序:p1,p2,p3,p4,p5那么一定有某个搜索值在两个相邻节点之间,不在树内则搜索失败,假设其搜索失败的概率为Q则可将所有数进行一个排列:Q0,p1,Q1,p2,Q2,p3,Q3,p4,Q4,p5,Q5(此处大写Q是为了容易看) ...
  • 用 r 来表示根节点搜索二叉树 用 small 来表示查找的平均概率 */ #include <iostream> using namespace std; struct Node { double small; int r; }; int main() { /* 对角线为本身概率 由于是...
  • 动态规划实现最优二叉树

    千次阅读 2020-10-20 13:12:39
    已知二叉搜索树中每个结点的访问概率,问这颗树整体的搜索时间最短是多少(此时称为最优二叉搜索树)。 例: 分别以概率:0.1, 0.2, 0.4, 0.3查找四个键:A, B, C, D。 第一颗树:0.11 + 0.22 + 0.43 + 0.34 = 2.9...
  • 哈夫曼树(最优二叉树)(c/c++)

    千次阅读 2020-02-10 21:45:10
    huffman coding哈夫曼编码的核心是构造哈夫曼树─即最优二叉树,带权路径长度最小的二叉树。它会使出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,...
  • 哈夫曼树(带权最优二叉树

    万次阅读 多人点赞 2018-05-24 19:52:34
      哈夫曼树(Huffman)树又称最优二叉树,是指对于一组带有确定权值的叶子结点所构造的具有带权路径长度最短的二叉树。从树中一个结点到另一个结点之间的分支构成了两结点之间的路径,路径上的分支个数称为路径长度。...
  • 一、满二叉树  一棵二叉树的结点要么是叶子结点,要么它有两个子结点(如果一个二叉树的层数为K,且结点总数是(2^k) -1,则它就是满二叉树。) 二、完全二叉树 ...四、最优二叉树(哈夫曼树)  .
  • 每个字符的二进制编码为(从根节点 数到对应的叶子节点,路径上的值拼接起来就是叶子节点字母的应该的编码) A:10 B:01 C:0011 D:11 E:000 F:00101 G:00100 那么当我想传送 ABC时,...
  • 动态规划--最优二叉树问题

    万次阅读 2015-01-19 20:38:34
    是一个有序集合,且x1, x2, ···, xn表示有序集合的二叉搜索树利用二叉树的顶点存储有序集中的元素,而且具有性质:存储于每个顶点中的元素x 大于其左子树中任一个顶点中存储的元素,小于其右子树中任意顶点中...
  • 哈夫曼树一、哈夫曼树基本概念二、哈夫曼树的构造算法 一、哈夫曼树基本概念 (1)路径:从树中的一个结点到另一个结点之间的分支...(5)结点的带权路径长度:从结点到该结点之间的路径长度与该结点的权的乘...
  • 3.5最优二叉树

    2018-06-20 00:46:50
    最优二叉树:即bi表示找到结点的概率,a0表示找到区间(负无穷,x1)的概率ai表示找到区间(xi,xi+1)的概率an表示找到区间(xn,正无穷)的概率对于二叉树中不能搜索到的结点(区间)我们称它伪结点,若树的根节点深度是...
  • 哈夫曼树(最优二叉树) 定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离...
  • 最优二叉树

    2018-06-10 17:21:37
    //根节点 cout 是根" ; if (s[i][root - 1]>0) { cout 的左孩子是s" [i][root - 1] ; } if (s[root + 1][j]>0) { cout 的右孩子是s" [root + 1][j] ; } T(i, root - 1, s); T(root + 1, ...
  • 最优erchasoushuo算法的java实现(动态规划法) 具体问题描述以及C/C++实现参见网址 http://blog.csdn.net/liufeng_king/article/details/8683136
  • 动态规划之最优二叉树

    千次阅读 2017-04-19 19:22:52
    一、什么是最优二叉查找树 最优二叉查找树: 给定n个互异的关键字组成的序列K=,且关键字有序(k1 图一显示了给定上面的概率分布pi、qi,生成的两个二叉查找树的例子。图二就是在这种情况下一棵最优二叉...
  • 一、什么是最优二叉查找树最优二叉查找树:给定n个互异的关键字组成的序列K=,且关键字有序(k1图一显示了给定上面的概率分布pi、qi,生成的两个二叉查找树的例子。图二就是在这种情况下一棵最优二叉查找树。 概率...
  • 本文学习二叉树的一些典型应用,包括二叉排序树、平衡二叉树最优带权二叉树,具体内容见文。
  • Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)为什么哈夫曼编码能够实现文件的压缩如果我们...
  • 最优二叉查找树—动态规划C++

    千次阅读 2020-12-26 00:35:34
    最优二叉查找树欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...
  • 展开全部import java.util.ArrayList;// 树的一e69da5e887aa62616964757a686964616f31333264643761个节点class TreeNode {Object _value = null;... // 他的父节点,根节点没有PARENTArrayList _childList = ...
  • Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码) 为什么哈夫曼编码能够实现文件的压缩 如果...
  • System.out.println("根节点表如下"); print(root); System.out.println("整棵树的树根是" + root[1][n]); treeRoot(root, 1, n); } static void treeRoot(int[][] root, int i,int j) { if(i > j) System.out....
  • 算法思想:动态规划实际问题:最优二叉搜索树编写语言:Java问题描述二叉搜索树的定义:满足以下任意两个条件的一个,就可称这棵树为二叉搜索树:它是一棵空树该树是一颗二叉树,非空,且满足下列两个条件:若它的左...
  • 1.先来看一下最优二叉树: 2.举个例子: 平局比较次数: 计算比较的平均次数: 3.其中最主要的推导公式: 其中:C[i][j]表示二叉查找树T(i,j)的平均比较次数;R[i][j]表示二叉查找树T(i,j)中作为根节点的...
  • 1、概念引入基于统计先验知识,我们可统计...这就是最优二叉查找树问题:查找过程中键值比较次数最少,或者说希望用最少的键值比较次数找到每个关键码(键值)。为解决这样的问题,显然需要对集合的每个元素赋予一个特...
  • DP之最优二叉树(算法导论学习)

    千次阅读 2012-05-05 15:04:19
    首先介绍下最优二叉树查找: 在二叉树中查找想要的关键字的话,我们想要得到的查找的消耗最少,对于查找某一个关键字的结点而言,查找该关键字过程中所查找过的结点的数目就是等于该结点的深度在加上1(对自己解释...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,498
精华内容 2,199
关键字:

最优二叉树的根节点是概率最大的吗

友情链接: sqlitfile.rar