引言
在计算机科学中,相对的大小要比绝对的数量更重要，计算机只看重相对的输赢。在计算机中，由于经常要做的事情是判断真假、比较大小、排序、挑选最大值这类的操作。在计算机的世界里为这些事情专门设计一种数据结构，称为二叉树。
I 二叉树
二叉树在生活中的对应：
- 锦标赛的比大小
- 文件目录
- 组织架构
- 网站的链接层次（N个分叉）
1.1 二叉树的发明
工具是根据所遇到的问题而发明的
在计算机科学中，数据的相对大小比绝对的数值重要，出于很多数据比大小的需求以及其他一些需求，就产生了一个抽象的数据结构——二叉树。
- 在数学上要计算数字，人类就发明了算盘。
- 在物理学上，要测量绝对的数值，人类就发明了各种度量长度的尺子、计时的钟、称重量的天平和秤等等。
- 在化学上，要测量化学反应的当量，人类就发明了各种有刻度的量器。
在计算机中，由于经常要做的事情是判断真假、比较大小、排序、挑选最大值这类的操作，而它们在计算机的世界里又如此重要，当然也就值得为这些事情专门设计一种数据结构，这种数据结构被称为二叉树。
1.2 二叉树的用处
二叉树浓缩了自然界很多事物的共性：分叉、层层递进和有序。针对这些共性，科学家们又总结出一些具有普遍性的算法，能够回过头来，应用到各种实际问题中。
- 排序(从左到右是从小到大)：把一堆数字按照一定的规则放到二叉树中，再拿出来，它们就有序。
- 快速查找到某一个数值
- 针对二叉树的各种算法，稍加改变，就可以用于互联网。比如，下载一个网站里面所有的网页，就会用到二叉树中的一种遍历算法。
在数学上，两个分支和N个分支是等价的，N个分支的情况可以通过两个分支来实现。
1.3 二叉树排序规则
思路：左右两个分叉可以和比较大小后的两种结果自然对应起来，从左到右是从小到大排好序的。
- 先来的占据根部，以及靠近顶部层级比较高的位置，后来的放在相对靠下的位置。
- 每当一个分支的根部被占据之后，接下来的数字，是和根部的数字进行比较，小的放到左边分叉中，大的放到右边分叉中。
时间复杂度：和快速排序是同一个量级。
1.4 二叉树的变种：哈夫曼树和红黑树
哈夫曼树和红黑树目的不同:
- 哈夫曼树对应于哈夫曼编码，即信息论里的最短编码。可以保证平均的访问时间最短。哈夫曼编码的条件是必须事先知道每个码出现的频率。
- 红黑树是为了防止二叉树一个枝子太长，另一个太短, 导致效率不高。
1.5 二叉搜索树和平衡二叉树的时间复杂度
与树的高度h相关，所以需要尽可能的降低树的高度。
【二叉搜索树 Binary search tree、平衡二叉树Balanced binary tree】
