哈夫曼树左小右大是指什么

~ 哈弗曼（Huffman）树，也称最优树，是一类带全路径长度最短的树，在实际中有广泛的应用，也是二叉树的一个具体应用。
在哈夫曼树的定义中，涉及到了路径、路径长度、权等概念，下面先给出概念的定义。

一、概念与定义

路径：从树的一个结点到另一个结点的分支构成这两个结点之间的路径，对于哈夫曼树特指从根节点到某节点的路径。

路径长度：路径上的分支数目叫做路径长度。
树的路径长度：从树根到每一结点的路径长度之和。
权：赋予某一个事物的一个量，是对事物的某个或某些属性数值化描述。在数据结构中，包括结点和边两大类，所以对应有结点权和边权。其具体代表的意义有具体情况而定。
结点的带权路径长度：从树根到结点之间的路径长度与结点上权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和(WPL--weighted path length)。它的权值分别为，从根到各叶子结点的路径长度分别为。则其带权路径长度WPL通常记作：

WPL的计算如下所示：

对于图a：WPL=2*(9+8+1+6)=48;

对于图b：WPL=8*1+9*2+(1+6)*3=47;

对于图c：WPL=9*1+8*2+(1+6)*3=46;

由图可以看出，权值越大的结点离根节点越近。

二、哈夫曼树构造算法

哈弗曼树的构造步骤：

1、根据给定的n个权值（w1,w2,w3,....wn）,构造n棵只有根结点的二叉树，令起权值为wj；
2、在森林中选取两棵根结点权值最小的树作为左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和
3、在森林中删除这两棵树，同时将新得到的二叉树加入森林中；
4、重复上述两个步骤，最后构成的树即为哈弗曼树。
下图显示了构造一棵哈弗曼树的两种方法：
常见的构造比较简单，这里我选择了两种比较特殊的数据进行了构造：
哈弗曼树并行生长的原则：如果新形成的二叉树的根节点的值大于或等于森林中的另外两个只有根结点树的值，那么接下来的两棵树将并行生长。并不是线性的直接向上生长。

构造方法一：

构造方法二：

最后显示了哈夫曼树的编码，编码的原则左小右大。

三、哈夫曼树在编码中的应用
哈夫曼树最常应用的地方就是对报文进行编码传输通信。在数据的交流中，我们对数据是有要求的：
（1）解码结果与发送方发送的电文完全一样。也就是说发送方传输的二进制编码，到接收方解码后必须具有唯一性；
（2）为了传输的效率和网络的通信及时占用资源少，发送的二进制编码尽可能地短。
下面介绍两种编码方式：
1. 等长编码
这种编码方式的特点是每个字符的编码长度相同，编码长度就是每个编码被翻译的二进制位数。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。 若现在有一段电文为：ABACCDA，则应发送二进制序列：000100101011000111，总长度为16位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但是存在的问题是编码长度并不是最短的，不满足上面的（2）的要求，因为在大数据量的情况下，我们必须的考虑效率问题，那么如何得到最短的编码呢？使用哈夫曼树就可以解决这个问题。这里先介绍一个前缀吗的概念。
前缀码：如果在一个系统中，任意一个编码都不是其他任何编码的前缀（最左子串），则称此编码系统中的编码是前缀码。
例如：（A:110、B:111、C:10、D:0）就是前缀码。但是（A:110、B:11、C:00、D:0）就不是前缀码。0是00的前缀，11是110的前缀。如果不定长的编码不是前缀码，则在译码时会产生二义性。例如110是A呢？还是BD呢？所以对于不定长编码一定要是前缀码。
2. 不等长编码
不等长编码可以叫最优的前缀码。在传送报文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的， 使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。如何得到最优的前缀编码呢？我们就可以利用上述的哈夫曼树来设计，同常成这种编码为哈夫曼编码，它不仅减少电文的总长，还必须考虑编码的唯一性。

四、哈夫曼树中的唯一和不唯一
唯一：哈夫曼树的WPL一定是最小的，唯一，最优是不变的。
不唯一：编码不唯一（表现出来就是形态不唯一）。比如说左小右大，或者是左大右小，树枝左右顺序是可以交换的，也就是说所得的哈夫曼编码则可能不同

哈夫曼树不唯一(即左孩子右孩子放的顺序可以是左大右小也可以是左小右大)
2. 哈夫曼树的子树也是哈夫曼树
3. 哈夫曼树中无度为1的结点

---

崇义县13739723710： 哈夫曼树左右两个子节点对调有影响吗 - ？
蒙贴瑞代： 哈夫曼树构造时选择两个最小的权值点,默认小的在左边大的在右边,其实没有这样的规定,编码的长度没有变化,所以左右子树互换没有影响.

崇义县13739723710： 霍夫曼 左右子树值大小问题 - ？
蒙贴瑞代： 假设有n个权值,则构造出的哈夫曼树有n个叶子结点. n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;(3)从森林中删除选取的两棵树,并将新树加入森林;(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树. 数据结构相关书上有详细解释及实例.

崇义县13739723710： 哈夫曼树的特征是什么 - ？
蒙贴瑞代： 哈弗曼树一定要是权值小的在左边权值大的在右边.

崇义县13739723710： huffman树右分支是指什么,在树的右边吗? - ？
蒙贴瑞代： 其中的哈夫曼树同一层上左边的权值比右边的小. 始终用权值最小的两个数相加的双亲结点权值. 以此类推可很容易得出哈夫曼树的编码. Huffman编码

崇义县13739723710： 到底什么是哈夫曼树啊,求例子 - ？
蒙贴瑞代： 哈夫曼树是给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 例子: 1、将w...

崇义县13739723710： 简述哈夫曼树的性质.？
蒙贴瑞代： 哈 夫 曼 树 2.9 二叉树的应用2.9.1 哈夫曼树及应用 哈夫曼树又称最优树(二叉树),是一类带权路径最短的树.构造这种树的算法最早是由哈夫曼(Huffman)1952年提出,这种树在信息检索中很有用.结点之间的路径长度:从一个结点到另一...

崇义县13739723710： 哈夫曼树编码一定是左边为0,右边为1吗? - ？
蒙贴瑞代： 注:0和1表示左子树还是右子树没有明确规定.因此左右节点的顺序是任意的,所以构造出的哈夫曼树并不唯一,但是各个哈夫曼树的带权路径长度相同且为最优.

崇义县13739723710： 数据结构 哈夫曼树在构造时 有顺序要求吗 比如左右子树的顺序要固定什么的 必须谁左谁右之类的 ? - ？
蒙贴瑞代： 1、我们可以统一确定左子节点和右子节点的大小关系,例如所有构造都必须使得左子节点的权值不小于右子节点,免得给出相同的原始节点序列,所构造的哈夫曼树结构不同2、节点按照权值排序的规则,例如两个原始节点或者一个原始节点和...

崇义县13739723710： 12、9、18、7、14、11,设计一棵赫夫曼树,要求左孩子权值小于右孩子, - ？
蒙贴瑞代： 统一是必须的,我感觉是频度比较大的放在右孩子,左孩子小,右孩子大,频度大的用的比较少,当然放后面了

崇义县13739723710： 数据结构赫夫曼树的左右子树问题. - ？
蒙贴瑞代： 数据结构书中的建立赫夫曼树求赫夫曼编码的算法中的Select()函数是用于选择没有双亲且权值最小的两个结点,其序号分别为s1和s2.按照给定权值的顺序查找,s1不一定比s2要小或者相等.s1是赋给左子树,s2赋给右子树.例如:第一次选择,按照5,29,7,8,14,23,3,11的顺序,显然s1=5,s2=3;第二次选择,按照29,7,8,14,23,11,8(5是左子树,3是右子树形成的二叉树根结点权值)的顺序,显然s1=7,s2=8;第三次选择,按照29,14,23,11,8(5是左子树,3是右子树形成的),15(7是左子树,8是右子树形成的二叉树根结点权值)的顺序,显然s1=11,s2=8;同理,最终得到的就是书上的那个图.