树结构详解（二叉树、AVL、B/B+树）

树就是一种类似现实生活中的树的数据结构（倒置的树）。任何一棵非空树只有一个根节点。 一棵树具有以下特点： 1. 一棵树中的任意两个结点有且仅有唯一的一条路径连通。 2. 一棵树如果有 n 个结点，那么它一定恰好有 n 1 条边。 3. 一棵树不包含回路。 下图就是一棵树，并且是一棵二叉树。 如上图所示，通过上面这张图说明一下树中的常用概念： 节点 ：树中的每个元素都可以统称为节点。 根节点 ：顶层节点或者说没有父节点的节点。上图中 A 节点就是根节点。 父节点 ：若一个节点含有子节点，则这个节点称为其子节点的父节点。上图中的 B 节点是 D 节点、E 节点的父节点。 子节点 ：一个节点含有的子树的根节点称为该节点的子节点。上图中 D 节点、E 节点是 B 节点的子节点。 兄弟节点 ：具有相同父节点的节点互称为兄弟节点。上图中 D 节点、E 节点的共同父节点是 B 节点，故 D 和 E 为兄弟节点。 叶子节点 ：没有子节点的节点。上图中的 D、F、H、I 都是叶子节点。 节点的高度 ：该节点到叶子节点的最长路径所包含的边数。 节点的深度 ：根节点到该节点的路径所包含的边数。 节点的层数 ：节点的深度+1。 树的高度 ：根节点的高度。 关于树的深度和高度的定义可以看 stackoverflow 上的这个问题：What is the difference between tree depth and height?。 二叉树的分类 二叉树 （Binary tree）是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。 二叉树 的分支通常被称作“ 左子树 ”或“ 右子树 ”。并且， 二叉树 的分支具有左右次序，不能随意颠倒。 二叉树 的第 i 层至多拥有 个节点，深度为 k 的二叉树至多总共有 个节点（满二叉树的情况），至少有 2^(k) 个节点（关于节点的深度的定义国内争议比较多，我个人比较认可维基百科对节点深度的定义 /%E6%9C%AF%E8%AF%AD)）。 满二叉树 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是 满二叉树 。也就是说，如果一个二叉树的层数为 K，且结点总数是 ，则它就是 满二叉树 。如下图所示： 完全二叉树 除最后一层外，若其余层都是满的，并且最后一层是满的或者是在右边缺少连续若干节点，则这个二叉树就是 完全二叉树 。 大家可以想象为一棵树从根结点开始扩展，扩展完左子节点才能开始扩展右子节点，每扩展完一层，才能继续扩展下一层。如下图所示： 完全二叉树有一个很好的性质： 父结点和子节点的序号有着对应关系。 细心的小伙伴可能发现了，当根节点的值为 1 的情况下，若父结点的序号是 i，那么左子节点的序号就是 2i，右子节点的序号就是 2i+1。这个性质使得完全二叉树利用数组存储时可以极大地节省空间，以及利用序号找到某个节点的父结点和子节点，后续二叉树的存储会详细介绍。 平衡二叉树 平衡二叉树 是一棵二叉排序树，且具有以下性质： 1. 可以是一棵空树。 2. 如果不是空树，它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。 平衡二叉树的常用实现方法有 红黑树 、 AVL 树 、 替罪羊树 、 加权平衡树 、 伸展树 等。 在给大家展示平衡二叉树之前，先给大家看一棵树： 你管这玩意儿叫树？？？ 没错，这玩意儿还真叫树，只不过这棵树已经退化为一个链表了，我们管它叫 斜树 。 如果这样，那我为啥不直接用链表呢？ 谁说不是呢？ 二叉树相比于链表，由于父子节点以及兄弟节点之间往往具有某种特殊的关系，这种关系使得我们在树中对数据进行 搜索 和 修改 时，相对于链表更加快捷便利。 但是，如果二叉树退化为一个链表了，那么树所具有的优秀性质就难以表现出来，效率也会大打折扣。为了避免这样的情况，我们希望每个做“家长”（父结点）的，都 一碗水端平 ，分给左儿子和分给右儿子的尽可能一样多，相差最多不超过一层，如下图所示： 二叉树的存储 二叉树的存储主要分为 链式存储 和 顺序存储 两种： 链式存储 和链表类似，二叉树的链式存储依靠指针将各个节点串联起来，不需要连续的存储空间。 每个节点包括三个属性： 数据 data。data 不一定是单一的数据，根据不同情况，可以是多个具有不同类型的数据。 左节点指针 left。 右节点指针 right。 可是 JAVA 没有指针啊！ 那就直接引用对象呗（别问我对象哪里找）。 顺序存储 顺序存储就是利用数组进行存储，数组中的每一个位置仅存储节点的 data，不存储左右子节点的指针，子节点的索引通过数组下标完成。根结点的序号为 1，对于每个节点 Node，假设它存储在数组中下标为 i 的位置，那么它的左子节点就存储在 2i 的位置，它的右子节点存储在下标为 2i+1 的位置。 一棵完全二叉树的数组顺序存储如下图所示： 大家可以试着填写一下存储如下二叉树的数组，比较一下和完全二叉树的顺序存储有何区别： 可以看到，如果我们要存储的二叉树不是完全二叉树，在数组中就会出现空隙，导致内存利用率降低。 二叉树的遍历 先序遍历 二叉树的先序遍历，就是先输出根结点，再遍历左子树，最后遍历右子树。遍历左子树和右子树的时候，同样遵循先序遍历的规则，也就是说，我们可以递归实现先序遍历。 代码如下： 中序遍历 二叉树的中序遍历，就是先递归中序遍历左子树，再输出根结点的值，再递归中序遍历右子树。大家可以想象成一巴掌把树压扁，父结点被拍到了左子节点和右子节点的中间，如下图所示： 代码如下： 后序遍历 二叉树的后序遍历，就是先递归后序遍历左子树，再递归后序遍历右子树，最后输出根结点的值。 代码如下： 面试复盘重点 树结构面试通常会从二叉树遍历开始，逐步追问二叉搜索树、平衡树、B 树和 B+ 树。 | 结构 | 特点 | 常见追问 | | | | | | 二叉树 | 每个节点最多两个子节点 | 前中后序遍历、层序遍历、树高 | | 二叉搜索树 | 左子树小于根，右子树大于根 | 中序遍历有序、退化成链表 | | AVL 树 | 高度平衡 | 查询快，插入删除旋转更频繁 | | 红黑树 | 近似平衡 | Java 、 树化 | | B 树 | 多路平衡搜索树 | 磁盘 IO 友好 | | B+ 树 | 数据通常在叶子节点，叶子节点有序链表相连 | MySQL 索引、范围查询 | 二叉树遍历模板要能手写： BST 高频回答： 中序遍历二叉搜索树可以得到递增序列。 如果插入数据本身有序，普通 BST 会退化成链表。 AVL 树比红黑树更严格平衡，查询更稳定；红黑树平衡要求宽一些，插入删除调整成本更低。 B+ 树适合数据库索引，一个节点能存更多 key，树高更低，叶子节点有序链表适合范围查询。 Java 代码模板 层序遍历是二叉树面试中最常见的非递归模板，很多“每层最大值”“锯齿形遍历”“最小深度”都可以从它变形。 验证 BST 时，不要只比较当前节点和左右孩子。正确做法是给每棵子树传上下界： 过程示意和边界样例 二叉树题可以先判断“当前节点要做什么”，再决定用前序、中序、后序还是层序。 几个边界样例建议手写前先过一遍： 空树：很多题应该返回空列表、 或 。 只有一个节点：递归出口和层序队列都要能处理。 退化链表：递归深度可能达到 ，复杂度不要误写成 。 BST 中存在 / ：上下界建议用 。 推荐练习题 144. 二叉树的前序遍历 102. 二叉树的层序遍历 98. 验证二叉搜索树 236. 二叉树的最近公共祖先 105. 从前序与中序遍历序列构造二叉树 写在最后 如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。 JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。 如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。