二叉树

从这章开始我们正式进入非线性数据结构的领域。

我们学过的两类线性结构、顺序表和链表。他们的优缺点基本正好互补。顺序表插入和删除元素有$O(n)$的复杂度，查找某个位置的元素则很快，在有序的前提下可以达到$O(logn)$的搜索复杂度。 而链表基本是他的反面，插入和删除元素的时间开销很小，可以达到$O(1)$，但搜索元素则需要$O(n)$的复杂度。 有没有什么数据结构能结合这两者的优点呢？这就是本章要讨论的树。当然树有很多种类型，本章不特别指明的话，都指最基础的二叉树。

树和链表在逻辑结构上有很大的不同。在线性数据结构中，除了头尾节点之外，每个节点都有且仅有1个前驱，有且仅有一个后继。从某个节点往前或往后，对应的节点都唯一。因此他们遍历的次序基本也是唯一的。不存在岔路，也不用选择。

但树有很大不同，如果我们将次序定义为上到下，那么每个节点都有唯一的前驱，但可以有多于一个的后继。这使我们向下选择的路径不唯一，遍历就有了更多的可能性。

从另一个角度看，选择某一条路径，就意味着我们放弃另一条路径。也就是所谓的“剪枝”，在很多场合，这是很有效的降低处理数据规模的方法。

此外我们还会发现，树的每个局部部分，都可以看成一颗新树。

如图，树A的左子树B和右子树C，都可以看成一颗二叉树。对于这种情况，我们可以认为树是一种递归定义的数据结构。很多性质，我们都可以通过递归的方式来定义：

搜索二叉树是这样一棵树：
1. 对于任意节点，左节点比根节点小。
2. 对于任意节点，右节点比根节点大。
3. 对于任意节点，他的子树也满足上述条件。

因此你会发现树天然适合用递归解决问题。

请大家带着这些概念，进入二叉树的学习。