哈夫曼树：某文件中有A、B、C、D、E、F和G共7种不同的字符，且每种字符出现的频率如下表所示，函数发f()恰好对应斐波那契数列的第2~8个数值：算法思路、伪代码、以及算法正确性

算法思路：
1. 将每个字符及其频率作为一个节点，构成一个森林。
2. 从森林中选取两个根节点的权值最小的树合并成一棵新树，权值为两个节点权值之和。
3. 将新树重新插入到森林中。
4. 重复步骤2和步骤3，直到森林中只剩下一棵树，即哈夫曼树。
5. 对哈夫曼树进行编码，规定左子树为0，右子树为1，从根节点开始遍历，直到叶子节点，得到每个字符的编码。

伪代码：

哈夫曼树(tree)
    while tree中节点数量 > 1
        选取tree中权值最小的两个节点node1, node2
        将node1和node2合并成一个节点new_node，权值为node1和node2的权值之和
        将new_node插入到tree中
    end while
    return tree

编码(tree, code)
    如果tree为叶子节点
        输出该节点对应的字符和编码code
    否则
        左子树递归调用编码函数，code加上0
        右子树递归调用编码函数，code加上1
    end if

算法正确性：
哈夫曼树是一种最优前缀编码，即每个字符的编码都不是另一个字符编码的前缀。证明如下：
假设存在两个字符x和y，它们的编码分别为a和b，且a是b的前缀，即a=bp（p为一个非空字符串）。
根据哈夫曼树的构造方式，权值较小的节点总是在深度较大的位置，因此x和y在哈夫曼树上的深度一定不同。
不妨设x在y的左侧，即在哈夫曼树上，x的深度小于y的深度。则a的最后一个字符必然是x对应的叶子节点，而b的最后一个字符是y对应的叶子节点。
由于a是b的前缀，故b必然包含a，即a=bp（p为一个非空字符串）。又因为x和y在哈夫曼树上深度不同，故x对应的叶子节点不可能是y对应叶子节点的祖先节点。
因此，a的最后一个字符不可能是y对应的叶子节点，与前面的假设矛盾。
因此，哈夫曼树是一种最优前缀编码。