树、森林——树与二叉树的应用（哈夫曼树的定义）

1. 基本概念带权路径长度 WPL树中所有叶子结点的权值 × 该结点到根的路径长度全部相加。哈夫曼树在n 个带权叶子结点构成的所有二叉树中带权路径长度 WPL 最小的二叉树→ 称为哈夫曼树最优二叉树2. 哈夫曼树重要特点只有叶子结点有权值分支结点无权值权值越大的叶子离根越近权值越小的叶子离根越远哈夫曼树没有度为 1 的结点n 个叶子结点 → 总结点数 2n - 1哈夫曼树不唯一但最小 WPL 唯一3. 总结哈夫曼树就是带权路径长度最短的二叉树权大离根近权小离根远。