构造哈夫曼树的全过程
时间: 2023-12-19 16:30:08 浏览: 31
以下是构造哈夫曼树的全过程:
1. 给定N个权值作为N个叶子节点。
2. 构造一个只包含N个根节点的集合F={f1,f2,...,fn},其中每个节点fi都是一棵只包含权值为wi的树。
3. 在F中选取两棵根节点的权值最小的树进行合并,并将新的树的根节点权值设为这两棵树的根节点权值之和。
4. 在F中删除这两棵树,并将新的树加入F中。
5. 重复步骤3和4,直到集合F中只剩下一棵树为止,这棵树就是哈夫曼树。
例如,给定权值为{5, 6, 8, 7, 15, 24, 17}的7个叶子节点,构造哈夫曼树的过程如下:
1. 将7个叶子节点看作7棵只包含一个节点的树,加入集合F中。
2. 从集合F中选取两棵根节点权值最小的树,即5和6,将它们合并成一棵新的树,根节点的权值为11。此时集合F中只剩下6棵树:{8, 7, 11, 15, 24, 17}。
3. 从集合F中选取两棵根节点权值最小的树,即7和8,将它们合并成一棵新的树,根节点的权值为15。此时集合F中只剩下5棵树:{11, 15, 11, 15, 24, 17}。
4. 从集合F中选取两棵根节点权值最小的树,即两棵权值为11的树,将它们合并成一棵新的树,根节点的权值为22。此时集合F中只剩下4棵树:{15, 22, 15, 24, 17}。
5. 从集合F中选取两棵根节点权值最小的树,即15和15,将它们合并成一棵新的树,根节点的权值为30。此时集合F中只剩下3棵树:{22, 30, 24, 17}。
6. 从集合F中选取两棵根节点权值最小的树,即22和24,将它们合并成一棵新的树,根节点的权值为46。此时集合F中只剩下2棵树:{30, 46, 17}。
7. 从集合F中选取两棵根节点权值最小的树,即30和17,将它们合并成一棵新的树,根节点的权值为47。此时集合F中只剩下1棵树:{46, 47}。
8. 集合F中只剩下一棵树,即为哈夫曼树,根节点的权值为93。