由权14,7,8,2,5,4,23构造Huffman树,则该树的权W(T)是
时间: 2024-03-30 09:35:31 浏览: 143
构建哈夫曼树的步骤如下:
1. 将所有权值从小到大排序,依次存放在叶子节点上;
2. 选取权值最小的两个节点构成一个新的节点,新节点的权值为这两个节点权值之和,并将这个新节点放入原来的节点集合中;
3. 重复第二步,直到所有节点合并成一个节点,构成哈夫曼树。
按照这个步骤,对于权值14,7,8,2,5,4,23,先将它们从小到大排序得到:2,4,5,7,8,14,23。
接着,选取权值最小的两个节点2和4,构造新节点,其权值为2+4=6,将6插入节点集合中,此时节点集合为:5,6,7,8,14,23。
接着,选取权值最小的两个节点5和6,构造新节点,其权值为5+6=11,将11插入节点集合中,此时节点集合为:7,8,11,14,23。
接着,选取权值最小的两个节点7和8,构造新节点,其权值为7+8=15,将15插入节点集合中,此时节点集合为:11,14,15,23。
接着,选取权值最小的两个节点11和14,构造新节点,其权值为11+14=25,将25插入节点集合中,此时节点集合为:15,23,25。
最后,选取权值最小的两个节点15和23,构造新节点,其权值为15+23=38,将38插入节点集合中,此时所有节点都合并成了一个节点,构成的哈夫曼树如下:
100
/ \
38 62
/ \
25 37
/ \ / \
11 14 7 30
/ \
14 16
根据哈夫曼树的定义,节点的权值是指该节点的所有叶子节点的权值之和,因此,根节点的权值就是所有叶子节点权值之和,即14+7+8+2+5+4+23=63。因此,该哈夫曼树的权值为63。