《数据结构与算法》——赫夫曼树

luciferzf

赫夫曼树：
1）为了节约资源，根据节点的利用情况组建二叉树，从而使建立的二叉树在使用时，使用率的节点遍历次数较少。
2）提出了权的概念，使用率高的节点的权较大，所以在构建二叉树的时候使权较大是节点在树的上层，所以在组建二叉树的时候，我们先对每个节点的权进行一次排序，然后先取其中权最小的两个节点分别作为左右节点，并生成一个新的节点作为这两个节点的父节点，父节点的权为左右两个子节点的权的和，然后从剩下的节点中选出权最小的节点，若该节点比父节点大，则该节点作为右子节点，原父节点作为左子节点，生成一个新节点作为二者的父节点，一直重复至所有节点都被使用。赫夫曼树构建完毕。