植树节，种个二叉树吧
3月12日，是全国的重要节日——植树节。还记得小时候，曾跟着老师一起去植树。如今参加工作了，虽然没有再亲手植过树，但却学习了不少关于树的结构知识，比如二叉树、B+树、红黑树等。这些内容在每次面试中几乎都是必问的。正好赶上植树节，原本打算讲解B树，但后来发现只有先理解了二叉树，才能更好地讲解B树。所以
3月12日，是全国的重要节日——植树节。还记得小时候，曾跟着老师一起去植树。如今参加工作了，虽然没有再亲手植过树，但却学习了不少关于树的结构知识，比如二叉树、B+树、红黑树等。这些内容在每次面试中几乎都是必问的。正好赶上植树节，原本打算讲解B树，但后来发现只有先理解了二叉树，才能更好地讲解B树。所以，今天就先给大家讲讲二叉树到底是什么，关于B树的内容，会在后面的文章中更新。
大白话讲解二叉树
比如现在有个数组，存放了很多用户的名字，需要从这个数组中找到包含指定的用户名，最快的方式是什么？
我们会想到二分查找，虽然这种方式很快，但要达到最快还需要有个条件：数组有序。
如果我们能把插入用户名的时候直接给他排序，那最后的结构就是有序结构。
因此有人设计了一种数据结构：二叉查找树，也叫做二叉树。
如下图所示：这是一种二叉树结构。
二叉树 根据上文中的例子的，假定 Herry 在最上面，下面有 Alice，Mike，Ivy，Tom，从左到右，从上到下来看的话，最后的排序是：Alice->Herry->Ivy->Mike->Tom，确实是按照字母顺序排的。
名字排序说明 其中有四个术语需要说明：节点、左节点、右节点、根节点。
其中每个红色圆球都算一个节点，节点左下边相连接的节点叫做左节点，而右边相连的叫做右节点。比如 Alice 被称作 Herry 节点的左节点，Mike 被称作 Herry 的右节点。而根节点只会有一个，属于最上面的节点，上图中的 Herry 就是根节点。
对于其中每个节点，左子节点的值都比它小，而右子节点的值都比它大。比如 Alice < Herry < Mike。
假设现在我们想要查找 Ivy，首先检查根节点，发现比 Herry 大，所以往下继续找，找到了根节点的右节点 Mike，再继续找，比 Mike 小，所以找 Mike 的左节点，正好找到 Ivy。
在二叉查找树中查找节点时，平均运行时间为O(logn)，最坏情况所需时间为O(n)；而在有序数组中查找时，即使是最坏情况，二分查找最多也只需O(logn)。由此，你或许会觉得二分查找比二叉查找快很多。然而，实际上二叉查找树的插入和删除操作速度要快得多。接下来，我们就来做一个对比：
二叉树与二分查找算法对比 但是二叉树也有缺点：
- 不能随机访问。比如想要查找第 10 个元素，是不能返回第十个元素的，但是数组就可以通过下标索引找到。
- 二叉树存在不平衡的情况，比如以根节点为中间的界限，发现右边的节点数远超左边的节点数，那么左右不平衡，查找的效率就很低了。如下图所示：
右边节点数远大于左边节点数 那有没有平衡的二叉树呢？当然有，那就是红黑树，限于篇幅和侧重点，这个放到下篇再讲吧
二叉树中的含义
二叉树定义
大白话说二叉树就是每个节点只能有两颗子树，且有左右之分。
来看看专业定义：二叉树是 n(n>=0 ) 个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。
二叉树有 5 种形态
- 空二叉树。
- 只有一个根节点的二叉树。
- 只有左子树
- 只有右子树。
- 完全二叉树。
节点的度
定义：节点拥有的子树数目称为节点的度。
我们来看下图就一目了然了。
mark 比如节点 B 的度为 2，节点 E 的度 为 1.
而树的度就是所有节点的度的最大值，也就是 2。
节点层次
如下图所示：根节点为第一层，依次类推。
二叉树的特点
- 每个节点最多有颗子树，所以二叉树中不存在度大于 2 的节点。
- 左右子树是有顺序的，次序不能任意颠倒。
- 即使某个节点只有一颗子树，也是需要区分它是左子树还是右子树。
二叉树的遍历
二叉树的遍历：从二叉树的根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点都能被访问一次，且仅被访问一次。
二叉树的访问次序可以分为四种：
- 前序遍历。
- 中序遍历。
- 后续遍历。
- 层序遍历。
前序遍历：通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左再向右的方向访问。
中序遍历：就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左再向右的方向访问。
后序遍历：就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左再向右的方向访问。
层次遍历：就是按照树的层次自上而下的遍历二叉树。
mark 按照前序遍历的结果就是 BADCE。
按照中序遍历的结果就是 ABCDE。
按照后续遍历的结果就是 ACEDB。
按照层次遍历的结果就是 BADCE。
巨人的肩膀：
《算法图解》
https://www.jianshu.com/p/bf73c8d50dc2
本文分享自微信公众号 - 悟空聊架构（PassJa va666）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
Photoshop 2026 是 Adobe 推出的专业图像处理与视觉设计软件，支持 Windows、macOS 和 iPad 等平台，广泛应用于摄影修图、电商设计、平面海报、数字绘画及视觉合成等创作场景。
Blender 是一款免费开源、跨平台的专业 3D 创作软件，集建模、动画、渲染、视频编辑与视觉合成等功能于一体，广泛应用于影视动画、游戏设计和建筑可视化等领域。软件支持 Cycles 物理渲染器与 Eevee 实时渲染引擎，并提供多边形建模、骨骼绑定、物理模拟等专业工具。Blender 兼容 Windows、macOS 和 Linux 系统，安装包轻巧、运行流畅，依托活跃的全球开发者社区持续更新，是从初学者到专业创作者都值得选择的正版 3D 创作工具。
极度公式是一款跨平台专业LaTeX公式识别编辑软件，支持OCR公式识别和多平台编辑。和使用说明，避免使用，享受完整功能与稳定支持。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。
一款文字处理软件，一种订阅式的跨平台办公软件，基于云平台提供多种服务，通过将 Excel 和 Outlook 等应用与 OneDrive 和 Microsoft Teams 等强大的云服务相结合，Office 365 可让任何人使用任何设备随时随地创建和共享内容。
CodeExpander 是一款快捷短语输入增强工具，通过键入缩写自动展开为自定义文段，提升工作效率。任务管理和过程控制会更完整，持续下载、批量同步或需要稳定传输流程的场景会更适合它。
Mountain Duck 是一款能将多个网盘挂载到本地的工具，像本地磁盘一样使用网盘。清理链路的完整性会更好一些，做应用卸载、残留处理和空间整理时，通常能少走很多手动排查步骤。
Photoshop 2026 是 Adobe 推出的专业图像处理与视觉设计软件，支持 Windows、macOS 和 iPad 等平台，广泛应用于摄影修图、电商设计、平面海报、数字绘画及视觉合成等创作场景。
Blender 是一款免费开源、跨平台的专业 3D 创作软件，集建模、动画、渲染、视频编辑与视觉合成等功能于一体，广泛应用于影视动画、游戏设计和建筑可视化等领域。软件支持 Cycles 物理渲染器与 Eevee 实时渲染引擎，并提供多边形建模、骨骼绑定、物理模拟等专业工具。Blender 兼容 Windows、macOS 和 Linux 系统，安装包轻巧、运行流畅，依托活跃的全球开发者社区持续更新，是从初学者到专业创作者都值得选择的正版 3D 创作工具。
极度公式是一款跨平台专业LaTeX公式识别编辑软件，支持OCR公式识别和多平台编辑。和使用说明，避免使用，享受完整功能与稳定支持。做扫描整理、文字提取和表格转换时，它能把识别后的处理步骤接得更顺，资料录入这类场景会省下不少时间。
一款文字处理软件，一种订阅式的跨平台办公软件，基于云平台提供多种服务，通过将 Excel 和 Outlook 等应用与 OneDrive 和 Microsoft Teams 等强大的云服务相结合，Office 365 可让任何人使用任何设备随时随地创建和共享内容。
Wise Folder Hider Pro 是一款专业级文件和文件夹隐藏加密软件，为私密数据添加多重保护。高频操作更强调就近处理，浏览、整理和跨目录移动文件时，来回切换和重复点击都会少很多。
CodeExpander 是一款快捷短语输入增强工具，通过键入缩写自动展开为自定义文段，提升工作效率。任务管理和过程控制会更完整，持续下载、批量同步或需要稳定传输流程的场景会更适合它。