树

树是一种层次化的非线性结构：节点通过边连接，有且仅有一个根，除根外每个节点只有一个父节点，且不存在环。树是文件系统、DOM、表达式解析以及堆、BST 等许多数据结构的基础。

树基础（Trees）

树由节点和边组成：从根到任意节点有唯一路径。在二叉树中，每个节点最多有左、右两个孩子。访问所有节点常用 BFS（广度优先 / 层序） 或 DFS（深度优先：先序、中序、后序）；二者也是图遍历与大量面试题的基础模板，遍历一棵含 $n$ 个节点的树时间复杂度为 $O(n)$。

• 菜鸟教程 - 树形结构 (2026-06-04)
• OI Wiki - 树基础 (2026-06-05)
• 树的介绍（视频）
• 树遍历（视频）
• BFS（广度优先搜索）和 DFS（深度优先搜索）（视频）
• [复习]4 分钟内的广度优先搜索（视频）
• [复习] 4 分钟内的深度优先搜索（视频）
• [复习]11 分钟内的树遍历（播放列表）（视频）

二叉查找树（Binary search trees）

二叉搜索树（BST） 在二叉树基础上满足 BST 性质：左子树所有键值小于当前节点，右子树大于当前节点，中序遍历得到升序序列。树较平衡时，查找、插入、删除的平均时间均为 $O(\log n)$；若按有序顺序插入会退化为链表，最坏为 $O(n)$。语言里的 std::map / TreeMap 等有序容器都建立在这一思想上，工程实现通常配合 AVL、红黑树等平衡树维持高度。

• OI Wiki - 二叉搜索树 & 平衡树 (2026-06-05)
• 二叉搜索树复习（视频）
• 介绍（视频）
• MIT（视频）
• C/C++:
  • 二叉查找树 —— 在 C/C++ 中实现（视频）
  • BST 的实现 —— 在堆栈和堆中的内存分配（视频）
  • 在二叉查找树中找到最小和最大的元素（视频）
  • 寻找二叉树的高度（视频）
  • 二叉树的遍历 —— 广度优先和深度优先策略（视频）
  • 二叉树：层序遍历（视频）
  • 二叉树的遍历：先序、中序、后序（视频）
  • 判断一棵二叉树是否为二叉查找树（视频）
  • 从二叉查找树中删除一个节点（视频）
  • 二叉查找树中序遍历的后继者（视频）

• 实现二叉搜索树 (2026-06-05)
• 实现平衡二叉搜索树 (2026-06-08)

堆（Heap） / 优先级队列（Priority Queue） / 二叉堆（Binary Heap）

堆是一棵满足堆性质的完全二叉树：大顶堆中父节点不小于子节点，小顶堆反之。用数组存储时，父子下标有固定换算关系，插入与删除极值可在 $O(\log n)$ 内完成；优先级队列的底层通常就是堆。堆排序、Top-K、Dijkstra 等场景都依赖这一结构。

• 百度百科 - 完全二叉树 (2026-06-08)
• OI Wiki - 堆简介 (2026-06-08)
• OI Wiki - 二叉堆 (2026-06-08)
• Hello Algo - 堆 (2026-06-08)
• Hello Algo - 构建堆 (2026-06-09)
• 菜鸟教程 - 堆排序 (2026-06-09)
• 堆（Heap）
• 堆简介（视频）
• 二叉树（视频）
• 树高度备注（视频）
• 基本操作（视频）
• 完全二叉树（视频）
• 伪代码（视频）
• 堆排序 - 跳转到开始部分（视频）
• 堆排序（视频）
• 构建堆（视频）
• MIT：堆和堆排序（视频）
• CS 61B Lecture 24：优先队列（视频）
• 线性时间构建堆（大顶堆）
• [复习] 13 分钟了解堆（视频）

• 实现大顶堆 (2026-06-08)
• 实现堆排序 (2026-06-09)
• 线性时间构建堆 (2026-06-09)