数学小课堂： 二叉树的来源（计算机思维）

引言

在计算机科学中,相对的大小要比绝对的数量更重要，计算机只看重相对的输赢。在计算机中，由于经常要做的事情是判断真假、比较大小、排序、挑选最大值这类的操作。在计算机的世界里为这些事情专门设计一种数据结构，称为二叉树。

I 二叉树

二叉树在生活中的对应：

• 锦标赛的比大小
• 文件目录
• 组织架构
• 网站的链接层次（N个分叉）

1.1 二叉树的发明

工具是根据所遇到的问题而发明的

在计算机科学中，数据的相对大小比绝对的数值重要，出于很多数据比大小的需求以及其他一些需求，就产生了一个抽象的数据结构——二叉树。

1. 在数学上要计算数字，人类就发明了算盘。
2. 在物理学上，要测量绝对的数值，人类就发明了各种度量长度的尺子、计时的钟、称重量的天平和秤等等。
3. 在化学上，要测量化学反应的当量，人类就发明了各种有刻度的量器。
4. 在计算机中，由于经常要做的事情是判断真假、比较大小、排序、挑选最大值这类的操作，而它们在计算机的世界里又如此重要，当然也就值得为这些事情专门设计一种数据结构，这种数据结构被称为二叉树。

1.2 二叉树的用处

二叉树浓缩了自然界很多事物的共性：分叉、层层递进和有序。针对这些共性，科学家们又总结出一些具有普遍性的算法，能够回过头来，应用到各种实际问题中。

1. 排序(从左到右是从小到大)：把一堆数字按照一定的规则放到二叉树中，再拿出来，它们就有序。
2. 快速查找到某一个数值
3. 针对二叉树的各种算法，稍加改变，就可以用于互联网。比如，下载一个网站里面所有的网页，就会用到二叉树中的一种遍历算法。

在数学上，两个分支和N个分支是等价的，N个分支的情况可以通过两个分支来实现。

1.3 二叉树排序规则

思路：左右两个分叉可以和比较大小后的两种结果自然对应起来，从左到右是从小到大排好序的。

1. 先来的占据根部，以及靠近顶部层级比较高的位置，后来的放在相对靠下的位置。
2. 每当一个分支的根部被占据之后，接下来的数字，是和根部的数字进行比较，小的放到左边分叉中，大的放到右边分叉中。

时间复杂度：和快速排序是同一个量级。

1.4 二叉树的变种：哈夫曼树和红黑树

哈夫曼树和红黑树目的不同:

1. 哈夫曼树对应于哈夫曼编码，即信息论里的最短编码。可以保证平均的访问时间最短。哈夫曼编码的条件是必须事先知道每个码出现的频率。
2. 红黑树是为了防止二叉树一个枝子太长，另一个太短, 导致效率不高。

1.5 二叉搜索树和平衡二叉树的时间复杂度

与树的高度h相关，所以需要尽可能的降低树的高度。

【二叉搜索树 Binary search tree、平衡二叉树Balanced binary tree】