二叉树基础及常见类型
我认为二叉树是最重要的基本数据结构，没有之一。
如果你是初学者，现在这个阶段我很难给你彻底解释清楚得出这个结论的原因，你需要认真学习本站后面的内容才能逐渐理解。我暂且总结两个点：
1、二叉树本身是比较简单的基础数据结构，但是很多复杂的数据结构都是基于二叉树的，比如 红黑树（二叉搜索树）、多叉树、二叉堆、图、字典树、并查集、线段树 等等。你把二叉树玩明白了，这些数据结构都不是问题；如果你不把二叉树搞明白，这些高级数据结构你也很难驾驭。
2、二叉树不单纯是一种数据结构，更代表着递归的思维方式。一切递归算法，比如 回溯算法、BFS 算法、动态规划 本质上也是把具体问题抽象成树结构，你只要抽象出来了，这些问题最终都回归二叉树的问题。同样看一段算法代码，在别人眼里是一串文本，每个字都认识，但连起来就不认识了；而在你眼里的代码就是一棵树，想咋改就咋改，咋改都能改对，实在是太简单了。
后面的数据结构章节包含大量关于二叉树的讲解和习题，你按照本站的目录顺序学习，我会带你把二叉树彻底搞懂，到时候你就明白我为什么这么重视二叉树了。
二叉搜索树
二叉搜索树（Binary Search Tree，简称 BST）是一种很常见的二叉树，它的定义是：对于树中的每个节点，其左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。你可以简单记为「左小右大」。我把「子树的每个节点」加粗了，这是初学者常犯的错误，不要只看子节点，而要看整棵子树的所有节点。比方说，下面这棵树就是一棵 BST：
J
