〓数据结构C++

来源：百度知道 编辑：UC知道 时间：2024/05/21 16:28:49
有7个带权结点，其权值分别为3, 7, 8, 2, 6, 10, 14，试以它们为叶结点生成一棵霍夫曼树，求出该树的高度

思想是：
先从小到大排序，2，3，6，7，8，10，14
把最小的两个数，作为叶子节点（2，3），把他们和（5）作为根节点
参与新的排序，5，6，7，8，10，14
如次往复，直到把所有的节点都加入进来：
7，8，10，11，14
10，11，14，15
14，15，21
21，29
50
然后，展开，就是一棵霍夫曼树：
_________________(50)__________________
________________/____\_________________
_____________(21)____(29)______________
____________/__\______/__\_____________
_________(10)__(11)_(14)__(15)_________
_______________/__\_______/__\_________
_____________(5)__(6)___(7)__(8)_______
_____________/__\______________________
___________(2)__(3)____________________

所以，树高是5

一次找权值最小的节点生成二叉树，最后的高度是5

jiandan