判断树：用于描述分类过程的二叉树
基本概念：
①路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径
②结点的路径长度：两结点间路径的分支数
③树的路径长度：从树根到每一个结点的路径长度之和，记作TL
结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树
④权（weight）：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权
⑤结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积
⑥树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：
哈夫曼树：最优二叉树（带权路径长度WPL最短的二叉树）
注：“带权路径长度最短”是在“度相同”的树中比较而得到的结果，因此有最优二叉树，最优三叉树之称等等
哈夫曼算法（构造哈夫曼树的方法）：
①根据n个给定的权值{w1，w2，…，wn}构成n棵二叉树的森林F={T1，T2，…，Tn}，其中Ti只有一个带权为wi的根结点（构造森林全是根）
②在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根结点的权值之和（选用两小造新树）
③在F中删除这两棵树，同时将新得到的二叉树加入森林中（删除两小添新人）
④重复（2）和（3），直到森林中只有一棵树为止，这棵树即为哈夫曼树（重复2，3剩单根）
总结：
①在哈夫曼算法中，初始时有n棵二叉树，要经过n-1次合并最终形成哈夫曼树
②经过n-1次合并产生n-1个新结点，且这n-1个新结点都是具有两个孩子的分支结点
可见：哈夫曼树中共有2n-1个结点，且其所有的分支结点的度均不为1
若有收获，就点个赞吧
0 人点赞
