关于如何构造哈夫曼树树的一个小问题

来源：蜘蛛抓取(WebSpider) 时间：2012-06-14 14:34 标签： 哈夫曼树
当前位置： >
对n(n&2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是(& )。
A．该树一定是一棵完全二叉树
B．树中一定没有度为1的结点
C．树中两个权值最小的结点一定是兄弟结点
D．树中任一非叶结点的权值一定不小于下一层任一结点的权值
所属学科：
试题类型：客观题
所属知识点：
试题分数：2.0 分
暂无学习笔记。
&&&&&&&&&&&&&&&希赛网 版权所有 & &&09-1509-0908-1708-17
09-2008-0809-2008-08
也许你感兴趣
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.懒省事的小明
时间限制： ms &|& 内存限制：65535 KB
描述&&&&& 小明很想吃果子，正好果园果子熟了。在果园里，小明已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。小明决定把所有的果子合成一堆。 因为小明比较懒，为了省力气，小明开始想点子了:　　每一次合并，小明可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。小明在合并果子时总共消耗的体力等于每次合并所耗体力之和。 　　因为还要花大力气把这些果子搬回家，所以小明在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使小明耗费的体力最少，并输出这个最小的体力耗费值。 　　例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以小明总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
输入第一行输入整数N(0&N&=10)表示测试数据组数。接下来每组测试数据输入包括两行，第一行是一个整数n(1&＝n&=12000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1&＝ai&=20000)是第i种果子的数目。输出每组测试数据输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2^31。样例输入
算法分析：就是哈弗曼树，首先排下序，再取最左边的两个值合并，再次排序，直到最后，要使用64位；
数组模拟：
#include&iostream&
#include&algorithm&
#define N 12010
using namespace
long long a[N];
long long work(int n)
long long t,ans=0;
if(n==1) return 0;
for(i=1;i&n;i++)
ans=ans+a[i]+a[i-1];
a[i]=a[i]+a[i-1];
bool flag=true;
for(;a[j-1]&a[j]&&j&n;j++)
t=a[j-1];a[j-1]=a[j];a[j]=t;
int main()
while(test--)
for(i=0;i&n;i++)
cin&&a[i];
sort(a,a+n);
cout&&work(n)&&
优先队列：
1 #include&iostream&
2 #include&algorithm&
3 #include&queue&
4 #define N 100
6 using namespace
8 int main()
test,n,i,t,tt,
priority_queue&long long, vector&long long &, greater&long long& &
while(test--)
while(!pq.empty()) pq.pop();
for(i=0;i&n;i++)
cin&&t;pq.push(t);
while(!pq.empty())
t=pq.top();pq.pop();
if(pq.empty())
tt=pq.top();pq.pop();
pq.push(tt);
cout&&ans&&
阅读(...) 评论()最小生成树和哈夫曼树有什么区别？_百度知道
最小生成树和哈夫曼树有什么区别？
最短路径和最小生成树是不同的概念.最短路径是对于一个图的两个结点而言的.在一个图中,结点A通过某些结点和边可以走到结点B,那这些结点和边就组成一条A到B的路径,A到B的最短路径就是A到B的所有路径中边权值总和最小的那一条（或多条）.最小生成树是对于一个图本身而言的.对于一个有n个结点的无向连通图（边没有方向,任意两点之间都存在路径可以到达）,必然可以去掉某些边,使得最终剩下n-1条边,并且n个结点仍然是连通的,这n个结点和n-1条边组成了原图的一个生成树,而最小生成树就是所有可能的生成树中n-1条边的权值总和最小的那一个（或多个）.最短路径常用算法有：floyd,dijkstra,SPFA,A*等最小生成树常用算法有：prim,kruskal
其他类似问题
为您推荐：
.n）构成一棵有N个叶结点的二叉树,，最小生成树用来设计水管,。哈夫曼树是用来进行编码压缩等，有两种算法..，记为WPL=（W1*L1+W2*L2+W3*L3+，相应的叶结点的路径长度为Li（i=1：prim和Kruskal,2，连同各个节点的权值和最小的情况，是一种带权路径长度最短的二叉树哈夫曼树又称最优二叉树。 最小生成树是计算连通图.n），就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层,2..。所谓树的带权路径长度。树的路径长度是从树根到每一结点的路径长度之和..+Wn*Ln），N个权值Wi（i=1、电路等连接各个结点所需的最短距离等用途，叶结点到根结点的路径长度为叶结点的层数）
来自团队：
最小生成树的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁以下试题来自：
单项选择题下面关于哈夫曼树的叙述中，正确的是______A．哈夫曼树一定是完全二叉树B．哈夫曼树一定是平衡二叉树C．哈夫曼树中权值最小的两个结点互为兄弟结点D．哈夫曼树中左孩子结点小于父结点，右孩子结点大于父结点
为您推荐的考试题库
你可能感兴趣的试题
123A．插入排序 B．归并排序 C．快速排序 D．堆排序4A．10 B．9 C．8 D．75
热门相关试卷
最新相关试卷

我要回帖

更多关于 哈夫曼树 的文章

 

随机推荐