画一颗权为3.4.5.6.7.8.9的最优2叉树

Question

画一颗权为3.4.5.6.7.8.9的最优2叉树

Answer 1

最优二叉树,也就是赫夫曼树
是把带权值最小的两个数,相加得到它的双亲结点.
35
13 22
10 12
5 7
3 4
1 2
1,2,3,4,5,6,7,8,9,10
1、先在序列里找权值两个最小的根结点.选1,2组成一棵二叉数.
然后,把1,2去掉.用根结点的权值3加入原序列.3,3,4,5,6,7,8,9,10
2、在新的序列中找权值两个最小的根结点.选3,3组成一棵二叉数.
然后,把3.3去掉.用根结点的权值6加入原序列,升序排列.
4,5,6,6,7,8,9,10
3、在新的序列中找权值两个最小的根结点.选4,5组成一棵二叉数.
然后,把4,5去掉.用根结点的权值9加入原序列.升序排列.6,6,7,8,9,9,10
4、在新的序列中找权值两个最小的根结点.选6,6组成一棵二叉数.
然后,把6,6去掉.用根结点的权值12加入原序列.升序排列.
7,8,9,9,10,12
5、在新的序列中找权值两个最小的根结点.选7,8组成一棵二叉数.
然后,把7,8去掉.用根结点的权值15加入原序列.升序排列.
9,9,10,12,15
6、在新的序列中找权值两个最小的根结点.选9,9组成一棵二叉数.
然后,把9,9去掉.用根结点的权值18加入原序列.升序排列.
10,12,15,18
7、在新的序列中找权值两个最小的根结点.选10,12组成一棵二叉数.
然后,把10,12去掉.用根结点的权值22加入原序列.升序排列.
15,18,22
8、在新的序列中找权值两个最小的根结点.选15,18组成一棵二叉数.
然后,把15,18去掉.用根结点的权值33加入原序列.升序排列.
22,33
9、在新的序列中找权值两个最小的根结点.选22,33组成一棵二叉数.
然后,把22,33去掉.用根结点的权值55加入原序列.55
尝试看看damaihu.