哈夫曼树，又称二叉树，是一类带权路径长度最短的树。所谓路径长度，就是节点到树根之间的路径长度与节点权值的乘积。

哈夫曼本人曾在MIT的信息论研究生班学习。Robert Fano教授让学生们自己决定是参加期未考试还是做一个大作业。而哈夫曼选择了后者，原因很简单，因为解决一大作业可能比期未考试更容易通过。Robert Fano教授也是信息论的先驱，学过信息论的都知道有Fano不等式，Shannon-Fano编码。当时这个大作业，Fano也解决不了，哈夫曼并不知道，于是自己尝试，最终产生了哈夫曼编码，其性能比Shannon-Fano编码更好。这个故事说明，大师级人物未能解决的问题，我们不一定解决不了，因为我们的思想比较开阔，能从不同的角度看问题。还有就是turbo码的产生也印证了这个道理。但是任何成功都离不开坚持不懈的努力。这段小故事就当你我共勉。

二叉树的遍历算法是许多二叉树运算的算法设计的基础，因此遍历算法的应用很广泛。下面以遍历算法求二叉树的叶子数和深度为例，来加深对于二叉树遍历算法的理解。

广度优先遍历：又称按层次遍历，也就是先遍历二叉树的第一层节点，然后遍历第二层节点……最后遍历最下层节点。而对每一层的遍历是按照从左至右的方式进行的。

二叉树的遍历可以分为深度优先遍历和广度优先遍历。本篇介绍深度优先遍历，下一篇介绍广度优先遍历。

基本概念：

​ 有序树与无序树：若将树中的每个节点的各个子树都看成是从左到右有次序的，则称该树为有序树，否则为无序数。

​ 从六月初开始看算法导论，陆陆续续看了有2个月了，但实际看的时间只有半个月左右。这期间都忙着找导师、期末考试，同时还回家修养了十来天。真正专心的看算法是在离家返校后，由于没有考试和作业的烦恼，天天都沉浸在算法中，感觉效率较高。这段时间学到的东西较多，下面来总结一下：

时间复杂度为：O(n)

基本思想：将要排列的序列分成n组，每组分别进行排序，然后在合并到一起，这里面有分而治之的思想。

​ 选择排序其实是冒泡法的一种改进，其基本思路也是：先确定最小元素，再找次最小元素，最后确定最大元素。

时间复杂度：O(n*n)

基本思想：从数组最后一个元素开始，依次与前一个元素比较，若比前一个元素小，则与之交换位置，然后再与当前前一个元素比较，直到遇到比它大的元素为止。例如：假设数组为：$a[5]={3,4,2,5,1}$;则运算过程为：首先$1$与$5$比较，由于$1<5$，从而交换位置，数组变为$a[5]={3,4,2,1,5}$;然后$1$与当前前一个元素$2$比较，一直重复上述操作，经过一次循环后，数组变为$a[5]={1,3,4,2,5}$;第二次循环从倒数第二个元素开始……，总共循环$n-1$次就可以得到正确结果。总的来说，首先将最小的元素放在数组前面，然后放次最小的元素，依此类推。

时间复杂度：$O(n)$.

基本思路：两个数比较大小，我们的直观感觉是先比较高位，若相同则比较低位。但是这样做需要记录额外的数据，浪费空间。而基数排序则是先比较低位，再比较高位。通过各个位的比较进行排序，如果数组元素最大有$N$位，则总共需要$N$次排序。注意：按位排序必须是稳定排序（两个相等的数其在序列的前后位置顺序，在排序前后不改变），所以在这我选择了计数排序。