【树】哈夫曼树左右子树的大小有规定吗哈夫曼左右子树如何确定

【【树】哈夫曼树左右子树的大小有规定吗哈夫曼左右子树如何确定】 哈夫曼树编码里面的父节点的两个子结点是没有顺序要求的，所以s1既可以是左子结点，也可以是右子结点，当然你也可以自己定一个标准来做，但是没有特别的要求的，因为就算不一样，只要在同一层，整棵树的总权值仍然是最小的。

文章插图

数据结构书中的建立赫夫曼树求赫夫曼编码的算法中的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；同理，最终得到的就是书上的那个图。