如何用C++画哈夫曼树？

~

权值w={5,29,7,8,14,23,3,11},画出哈夫曼树.

个人认为, 图2的画法有不妥的地方.

问题点就是:
结点3和结点5组成新结点N8,那么新结点N8应该排在原有结点8的后面,还是前面?

个人认为,应该按照图1的做法,将新结点N8排在原有结点8的后面.

分析过程如下:

八个权值从小到大排序是: 3 5 7 8 11 14 23 29

图1 : 哈夫曼树

         N100
      /        \
    N42        N58
   /  \       /  \
  23  N19    29  N29
     /  \       /  \
   11   N8     14  N15
       /  \       /  \
      3    5     7    8

根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2
根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4
如此类推,哈夫曼树的带权路径长度(WPL)等于
29*2 + 23*2 + 14*3 + 11*3 + 8*4 + 7*4 + 5*4 + 3*4 = 271

哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
权值29: 10
权值23: 00
权值14: 110
权值11: 010
权值8 : 1111
权值7 : 1110
权值5 : 0111
权值3 : 0110


图2 : 哈夫曼树

             N100
         /          \
        N58        N42
       /   \      /   \
      N29  29    N19  23
     /  \       /  \
   14   N15    8   11
       /  \
      7   N8
         /  \
        3    5

根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2
根结点N100到结点3的路径长度是5,结点3的带权路径长度是3*5
如此类推,哈夫曼树的带权路径长度(WPL)等于
29*2 +23*2 +14*3 +11*3 +8*3 +7*4 +5*5 +3*5  = 271

哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
权值29: 01
权值23: 11
权值14: 000
权值11: 101
权值8 : 100
权值7 : 0010
权值5 : 00111
权值3 : 00110


从 WPL 的角度看,图1和图2的WPL都是等于271.

从 哈夫曼编码 的角度看:
图1, 权值29的编码是10, 权值3的编码是0110 
图2, 权值29的编码是01, 权值3的编码是00110

图2的权值29和权值3的编码长度相差大了一点.

相比下,图1的方案更加合适,所以优先选择图1的哈夫曼树.

图1和图2出现编码差异大的主要原因是:
结点3和结点5组成新结点N8,那么新结点N8应该排在原有结点8的后面,还是前面?
图1的做法是将新结点N8排在原有结点8的后面,所以结点7与原有结点8先合并.
而图2的做法是新结点将N8排在原有结点8的前面,所以结点7和新结点N8先合并了.

个人认为,应该按照图1的做法,将新结点N8排在原有结点8的后面.

另外,个人认为,图1的结点11和N8的左右位置互换一下,结点23和N19左右位置互换一下,
这样会更加合适,保证从左到右,结点是从小到大,让最后编码的时候,更加统一.


以下是详细的构建过程:

(1) 从小到大排序 3 5 7 8 11 14 23 29 (这是有序序列)
(2) 每次提取最小的两个结点,取结点3和结点5,组成新结点N8,其权值=3+5=8,
    取数值较小的结点作为左分支,结点3作为左分支,而结点5就作为右分支.
(3) 将新结点N8放入有序序列,保持从小到大排序:
    7 8 N8 11 14 23 29  [注意,新结点N8排在原结点8的后面]
(4) 重复步骤(2),提取最小的两个结点,结点7与结点8组成新结点N15,其权值=7+8=15,
    结点7的数值较小,将结点7作为左分支,结点8就作为右分支.
(5) 将新结点N15放入有序序列,保持从小到大排序:
    N8 11 14 N15 23 29
(6) 重复步骤(2),提取最小的两个结点,N8与结点11组成新结点N19,其权值=8+11=19,
    N8的数值较小,作为左分支,结点11就作为右分支.
(7) 将新结点N19放入有序序列,保持从小到大排序:
    14 N15 N19 23 29
(8) 重复步骤(2),提取最小的两个结点,结点14与N15组成新结点N29,其权值=14+15=29,
    结点14的数值较小,作为左分支,N15就作为右分支.
(9) 将新结点N29放入有序序列,保持从小到大排序:
    N19 23 29 N29  [注意,新结点N29排在原结点29的后面]
(10)重复步骤(2),提取最小的两个结点,N19与结点23组成新结点N42,其权值=19+23=42,
    N19的数值较小,作为左分支,结点23就作为右分支.
(11)将新结点N42放入有序序列,保持从小到大排序:
    29 N29 N42
(12)重复步骤(2),提取最小的两个结点,结点29与N29组成新结点N58,其权值=29+29=58,
    结点29与N29的数值相同,将原结点29作为左分支,N29就作为右分支.
(13)将新结点N58放入有序序列,保持从小到大排序:
    N42 N58
(14)重复步骤(2),提取剩下的两个结点,N42与N58组成新结点N100,其权值=42+58=100,
    数值较小的N42作为左分支,N58就作为右分支.
    最后得到"哈夫曼树":

              N100
           /       \
          N42      N58
         /   \     /  \
        N19  23   29  N29
       /  \          /  \
      N8  11       14   N15
     /  \              /  \
    3    5            7    8

带权路径长度(WPL):
根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2
根结点N100到结点23的路径长度是2,结点23的带权路径长度是23*2
根结点N100到结点14的路径长度是3,结点14的带权路径长度是14*3
根结点N100到结点11的路径长度是3,结点11的带权路径长度是11*3
根结点N100到结点8的路径长度是4,结点8的带权路径长度是8*4
根结点N100到结点7的路径长度是4,结点7的带权路径长度是7*4
根结点N100到结点5的路径长度是4,结点5的带权路径长度是5*4
根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4
所以,哈夫曼树的带权路径长度(WPL)等于
29*2 + 23*2 + 14*3 + 11*3 + 8*4 + 7*4 + 5*4 + 3*4 = 271

哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N100到结点29,先经历右分支,再经历左分支,结点29的编码就是10
从根结点N100到结点23,先经历左分支,再经历右分支,结点23的编码就是01
从根结点N100到结点14,经历两次右分支,再经历左分支,结点14的编码就是110
如此类推,得出所有结点的"哈夫曼编码":
权值29: 10
权值23: 01
权值14: 110
权值11: 001
权值8 : 1111
权值7 : 1110
权值5 : 0001
权值3 : 0000

---

广阳区17713313551： 数据结构C++实现哈夫曼树 - ？
颜黎补中： 看程序代码: #include＂stdlib.h＂ #include <iostream.h>#include <iomanip.h> const int n=10;//字符的最大个数 struct hufnode {char elem;int m_weight;int parent,lchild,rchild; //两个叶子节点回溯到跟节点 }; typedef struct hufnode htnode; ...

广阳区17713313551： 用C++写一个哈夫曼树的程序 - ？
颜黎补中： #include <iostream> #include <stdlib.h>using namespace std; const int MaxValue = 10000; //初始设定的权值最大值 const int MaxBit = 4; //初始设定的最大编码位数 const int MaxN = 10; //初始设定的最大结点个数 struct HaffNode //哈夫...

广阳区17713313551： 用C++编写Huffman码 - ？
颜黎补中： 使用说明:首先建立哈夫曼树,输入你的信号源的个数,然后输入每个信号的符号及其相应的频率(最后乘以100不要出现小数的为好)我的输入文件名为Myinput.txt即在C盘下建立文本文档取名为Myinput.txt然后输入你的信号的符号以空格结束...

广阳区17713313551： 试编写实现哈夫曼树和哈夫曼编码的算法?这是数据结构里的问题,要求用C++6.0来实现 - ？
颜黎补中： #include <stdio.h> #include <malloc.h> #include<math.h> struct hf { char data; int weight; struct hf *lc; struct hf *rc; struct hf *pc; int hcd[30]; } *hc[30]; int n;main() {struct hf creat(); struct hf bian(struct hf *hc[30]); struct hf print(struct hf *hc[30]);int m;do ...

广阳区17713313551： 哈夫曼树和编码应用用C++实现 - ？
颜黎补中： #include <stdio.h> #define MAXBIT 10 /*定义哈夫曼编码的最大长度*/ #define MAXVALUE 10000 /*定义最大权值*/ #define MAXLEAF 30 /*定义哈夫曼树中最多叶子节点个数*/ #define MAXNODE MAXLEAF*2-1 /*哈夫曼树最多结点数*/ typedef ...

广阳区17713313551： 谁能帮我用c++语言构建一个哈夫曼树 非常急 非常感谢？
颜黎补中： ================================================ 程序代码: ================================================ #include<stdio.h> #include<stdlib.h> #define MAXLEN 100 typedef struct Huffmantree { char ch; /*键值*/ int ...

广阳区17713313551： 哈夫曼树的建立及应用？
颜黎补中： 给你个我写的哈夫曼函数: void HuffmanTree(HuffmanTree &HT, int * w, int n) { //w 存放n 个字符的权值(均>0),构造赫夫曼树HT if (n<=1) return; m=2* n-1; HT=(HuffmanTree)malloc(m+1) * sizeof(HTNode); //分配存储空间 //用给定的n个权...

广阳区17713313551： 霍夫曼树及编码的c++程序算法 - ？
颜黎补中： #include <iostream>#include <fstream>#include <string> using namespace std; template <class T> class MinHeap { private: T * heapArray; int CurrentSize; int MaxSize;void BuildHeap(); public: MinHeap(const int n);~MinHeap(){delete []...

广阳区17713313551： 数据结构题目,关于哈弗曼编码,用C语言来做(非常急的,谢谢了) - ？
颜黎补中： void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) { // w存放n个字符的权值(均>0),构造哈夫曼树HT, // 并求出n个字符的哈夫曼编码HC int i, j, m, s1,s2; char *cd; int p; int cdlen; if (n m = 2 * n - 1; HT = (HuffmanTree)...

广阳区17713313551： 急求一个C++程序 哈夫曼编码 - ？
颜黎补中： #include <fstream.h>#include <stdlib.h>#include <string.h>#define CAPS ch>=65&&ch<=90 //定义宏,用于判断大小写#define LOWS ch>=97&&ch<=122 struct Huffman{ Huffman *pnext,*pl,*pr; //pnext用于建立链表,pl、pr用于建立哈夫曼树 char ...