题目
有权值分别为2,3,5,8,7,4的叶子结点生成一棵哈夫曼树,其带权路径长度为()A. 36B. 72C. 96D. 120
有权值分别为2,3,5,8,7,4的叶子结点生成一棵哈夫曼树,其带权路径长度为()
- A. 36
- B. 72
- C. 96
- D. 120
题目解答
答案
B
解析
步骤 1:构建哈夫曼树
哈夫曼树是一种带权路径长度最短的二叉树。构建哈夫曼树的步骤如下:
1. 将所有叶子结点按照权值从小到大排序。
2. 选择两个权值最小的结点,创建一个新结点,其权值为这两个结点权值之和。
3. 将新结点加入到结点集合中,重复步骤2,直到所有结点合并成一个树。
步骤 2:计算带权路径长度
带权路径长度是所有叶子结点的权值乘以其到根结点的路径长度之和。
步骤 3:计算最终结果
根据哈夫曼树的构建过程,计算出带权路径长度。
哈夫曼树是一种带权路径长度最短的二叉树。构建哈夫曼树的步骤如下:
1. 将所有叶子结点按照权值从小到大排序。
2. 选择两个权值最小的结点,创建一个新结点,其权值为这两个结点权值之和。
3. 将新结点加入到结点集合中,重复步骤2,直到所有结点合并成一个树。
步骤 2:计算带权路径长度
带权路径长度是所有叶子结点的权值乘以其到根结点的路径长度之和。
步骤 3:计算最终结果
根据哈夫曼树的构建过程,计算出带权路径长度。