Hello 算法二叉树篇完整笔记从节点结构、遍历策略到 AVL 树旋转的体系化回顾【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本文基于《Hello 算法》仓库的树章节小结 summary.md对二叉树的核心知识体系做一次系统回顾从节点结构与常用术语到层序遍历BFS与三种深度优先遍历DFS再到二叉搜索树的增删查与 AVL 树的四种旋转操作。读完后你可以对照仓库中多语言实现如 avl_tree.py、binary_search_tree.py逐行验证每一条结论建立起一套可自洽推导的树结构知识框架。一、二叉树的基本概念与节点结构二叉树binary tree是一种非线性数据结构体现“一分为二”的分治逻辑。与链表类似二叉树的基本单元是节点每个节点包含一个值以及两个指针引用分别指向其左子节点和右子节点。对二叉树中的某个节点其左右子节点及其以下形成的树被称为该节点的左右子树。以 Python 实现为例节点定义如下见 binary_tree.py 与文档 binary_tree.mdclass TreeNode: 二叉树节点类 def __init__(self, val: int): self.val: int val # 节点值 self.left: TreeNode | None None # 左子节点引用 self.right: TreeNode | None None # 右子节点引用二叉树的常用术语包括根节点root node位于顶层、没有父节点的节点叶节点leaf node没有子节点的节点两个指针均指向None边edge连接两个节点的线段即节点引用指针层level从顶至底递增根节点所在层为 1度degree节点的子节点数量在二叉树中取值为 0、1、2高度height从根节点到最远叶节点所经过的边的数量深度depth从根节点到某节点所经过的边的数量。请注意高度与深度通常定义为“经过的边的数量”但部分题目或教材会将其定义为“经过的节点的数量”。此时高度和深度都需要加 1详见下文 QA 第一条。初始化二叉树与链表类似先初始化节点再构建节点之间的引用指针# 初始化节点 n1 TreeNode(val1) n2 TreeNode(val2) n3 TreeNode(val3) n4 TreeNode(val4) n5 TreeNode(val5) # 构建节点之间的引用指针 n1.left n2 n1.right n3 n2.left n4 n2.right n5插入与删除节点同样通过修改指针实现。以在n1 - n2之间插入节点 P 为例# 插入与删除节点 p TreeNode(0) # 在 n1 - n2 中间插入节点 P n1.left p p.left n2 # 删除节点 P n1.left n2需要注意的是插入节点可能会改变二叉树的原有逻辑结构而删除节点通常意味着删除该节点及其所有子树。因此二叉树中的插入与删除通常由一套操作配合完成以实现有实际意义的操作——这一点在二叉搜索树与 AVL 树的删除实现中会得到具体印证。二、常见二叉树类型与二叉树的退化小结中列出四种常见类型完美二叉树、完全二叉树、完满二叉树和平衡二叉树。其中完美二叉树中文社区常称“满二叉树”所有层的节点都被完全填满叶节点度为 0、其余节点度均为 2若高度为 h 则节点总数为 $2^{h1} - 1$完全二叉树仅允许最底层不完全填满且从左至右连续填充完满二叉树除叶节点外每个节点都有两个子节点平衡二叉树则要求任意节点左右子树高度差的绝对值不超过 1。完美二叉树是最理想的状态链表是退化后的最差状态。下表对比了两类极端结构下的关键指标完美二叉树链表第 $i$ 层的节点数量$2^{i-1}$$1$高度为 $h$ 的树的叶节点数量$2^h$$1$高度为 $h$ 的树的节点总数$2^{h1} - 1$$h 1$节点总数为 $n$ 的树的高度$\log_2 (n1) - 1$$n - 1$这一退化问题贯穿整个树章节二叉搜索树在频繁增删后退化为链表时各项操作复杂度从 $O(\log n)$ 劣化至 $O(n)$这正是 AVL 树要解决的核心问题。三、二叉树的数组表示除了链表指针表示二叉树也可以用数组表示。方法是将节点值和空位按层序遍历顺序排列并借助父节点与子节点之间的索引映射关系来“实现指针”若某节点的索引为 i则其左子节点索引为 $2i 1$右子节点索引为 $2i 2$。对于非完美二叉树中间层存在许多空位仅凭层序序列无法唯一确定树结构因此需要在序列中显式写出空位None。示例# 二叉树的数组表示 # 使用 None 来表示空位 tree [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15]仓库中 array_binary_tree.py 给出了完整的数组表示实现其核心就是三个索引函数def left(self, i: int) - int | None: 获取索引为 i 节点的左子节点的索引 return 2 * i 1 def right(self, i: int) - int | None: 获取索引为 i 节点的右子节点的索引 return 2 * i 2 def parent(self, i: int) - int | None: 获取索引为 i 节点的父节点的索引 return (i - 1) // 2其中父节点索引 $(i-1) // 2$ 是层序映射的逆运算。该文件还实现了层序遍历直接顺序扫过数组、跳过空位以及前序、中序、后序遍历基于索引映射的递归完整覆盖了文档 array_representation_of_tree.md 所述的操作集合。完全二叉树非常适合数组表示空位只出现在序列末尾可以省略存储。数组表示的优点是内存连续、缓存友好、无需指针、支持随机访问局限性则是需要连续内存、增删节点需移动数组元素、空位过多时空间利用率低。四、层序遍历广度优先搜索BFS层序遍历从顶部到底部逐层访问二叉树每层按从左到右的顺序访问节点。它本质上属于广度优先遍历breadth-first search, BFS体现“一圈一圈向外扩展”的逐层遍历方式通常借助队列实现——队列“先进先出”的规则与 BFS“逐层推进”的思想是一致的。binary_tree_bfs.py 中的level_order()实现如下def level_order(root: TreeNode | None) - list[int]: 层序遍历 # 初始化队列加入根节点 queue: deque[TreeNode] deque() queue.append(root) # 初始化一个列表用于保存遍历序列 res [] while queue: node: TreeNode queue.popleft() # 队列出队 res.append(node.val) # 保存节点值 if node.left is not None: queue.append(node.left) # 左子节点入队 if node.right is not None: queue.append(node.right) # 右子节点入队 return res复杂度分析时间复杂度 $O(n)$所有节点被访问一次空间复杂度 $O(n)$在最差情况下满二叉树遍历到最底层之前队列中最多同时存在 $(n 1) / 2$ 个节点。关于队列规模有一个值得玩味的事实广度优先遍历到最底层之前队列中的节点数量恰为 $2^h$例如高度 $h 2$ 的满二叉树节点总数 $n 7$底层节点数量 $4 2^h (n1)/2$。五、前序、中序、后序遍历深度优先搜索DFS前序、中序、后序遍历皆属于深度优先遍历depth-first search, DFS体现“先走到尽头再回溯继续”的遍历方式通常使用递归来实现。深度优先遍历就像绕着整棵二叉树的外围“走”一圈每个节点都会被遇到三次分别对应前、中、后三种访问时机。binary_tree_dfs.py 中三种遍历只差一行res.append(root.val)的位置def pre_order(root: TreeNode | None): 前序遍历 if root is None: return # 访问优先级根节点 - 左子树 - 右子树 res.append(root.val) pre_order(rootroot.left) pre_order(rootroot.right) def in_order(root: TreeNode | None): 中序遍历 if root is None: return # 访问优先级左子树 - 根节点 - 右子树 in_order(rootroot.left) res.append(root.val) in_order(rootroot.right) def post_order(root: TreeNode | None): 后序遍历 if root is None: return # 访问优先级左子树 - 右子树 - 根节点 post_order(rootroot.left) post_order(rootroot.right) res.append(root.val)递归过程可分为“递”与“归”两个逆向阶段“递”表示开启新调用、访问下一个节点“归”表示函数返回、当前节点访问完毕。复杂度方面时间复杂度为 $O(n)$空间复杂度为 $O(n)$——在最差情况下树退化为链表递归深度达到 n系统占用 $O(n)$ 栈帧空间。深度优先遍历也可以基于迭代实现通常借助显式栈这里以递归为主。六、二叉搜索树查找、插入、删除与中序有序二叉搜索树binary search tree满足根节点的值介于左、右子树所有节点的值之间左 根 右且任意节点的左右子树也是二叉搜索树。其查找、插入、删除操作的时间复杂度均为 $O(\log n)$当树退化为链表时各项复杂度劣化至 $O(n)$。仓库中 binary_search_tree.py 的BinarySearchTree类封装了这三项操作是理解“一套操作配合完成”的最佳样本。6.1 查找节点查找与二分查找原理一致每轮排除一半情况循环次数最多为树高def search(self, num: int) - TreeNode | None: 查找节点 cur self._root # 循环查找越过叶节点后跳出 while cur is not None: # 目标节点在 cur 的右子树中 if cur.val num: cur cur.right # 目标节点在 cur 的左子树中 elif cur.val num: cur cur.left # 找到目标节点跳出循环 else: break return cur6.2 插入节点插入分两步循环查找插入位置、在该位置插入节点。实现上有两个关键细节树中不允许重复节点遇到重复值直接返回用辅助指针pre保存上一轮节点以便在遍历至None时拿到父节点完成挂接def insert(self, num: int): 插入节点 # 若树为空则初始化根节点 if self._root is None: self._root TreeNode(num) return # 循环查找越过叶节点后跳出 cur, pre self._root, None while cur is not None: # 找到重复节点直接返回 if cur.val num: return pre cur # 插入位置在 cur 的右子树中 if cur.val num: cur cur.right # 插入位置在 cur 的左子树中 else: cur cur.left # 插入节点 node TreeNode(num) if pre.val num: pre.right node else: pre.left node6.3 删除节点分三种情况删除操作要分待删除节点的子节点数量为 0、1、2 三种情况处理每种情况都需要多步节点操作这正是小结 QA 中“一套操作”的具体含义。其中度为 2 的情况最复杂无法直接删除需要用右子树的最小节点即中序遍历的下一个节点覆盖当前节点再递归删除那个后继节点# 子节点数量 0 or 1 if cur.left is None or cur.right is None: child cur.left or cur.right # 删除节点 cur if cur ! self._root: if pre.left cur: pre.left child else: pre.right child else: # 若删除节点为根节点则重新指定根节点 self._root child # 子节点数量 2 else: # 获取中序遍历中 cur 的下一个节点 tmp: TreeNode cur.right while tmp.left is not None: tmp tmp.left # 递归删除节点 tmp self.remove(tmp.val) # 用 tmp 覆盖 cur cur.val tmp.val删除总耗时 $O(\log n)$查找待删除节点 $O(\log n)$获取中序后继 $O(\log n)$。6.4 中序遍历有序与效率对比由于中序遍历遵循“左 → 根 → 右”的顺序而二叉搜索树满足“左 根 右”的大小关系所以二叉搜索树的中序遍历序列天然升序获取有序数据仅需 $O(n)$ 时间无需额外排序。这也是“为什么 DFS 有前中后三种顺序”的实战答案之一见 QA。与无序数组对比源自 binary_search_tree.md无序数组二叉搜索树查找元素$O(n)$$O(\log n)$插入元素$O(1)$$O(\log n)$删除元素$O(n)$$O(\log n)$只有在高频添加、低频查找删除数据的场景下数组才比二叉搜索树效率更高。常见应用包括系统多级索引、搜索算法的底层数据结构、以及保持数据流有序状态。七、AVL 树用旋转操作维持平衡7.1 为什么需要 AVL 树不断插入和删除节点可能使二叉搜索树退化为链表例如删除两个节点后树就变成链状各种操作的复杂度随之从 $O(\log n)$ 劣化为 $O(n)$。1962 年 G. M. Adelson-Velsky 和 E. M. Landis 在论文“An algorithm for the organization of information”中提出AVL 树通过一系列操作确保持续增删节点后树不会退化使各种操作稳定保持在 $O(\log n)$ 级别。7.2 节点高度与平衡因子AVL 树既是二叉搜索树也是平衡二叉树是平衡二叉搜索树balanced binary search tree。为此节点类增加了height变量并配套两个工具函数avl_tree.pydef height(self, node: TreeNode | None) - int: 获取节点高度 # 空节点高度为 -1 叶节点高度为 0 if node is not None: return node.height return -1 def update_height(self, node: TreeNode | None): 更新节点高度 # 节点高度等于最高子树高度 1 node.height max([self.height(node.left), self.height(node.right)]) 1 def balance_factor(self, node: TreeNode | None) - int: 获取平衡因子 # 空节点平衡因子为 0 if node is None: return 0 # 节点平衡因子 左子树高度 - 右子树高度 return self.height(node.left) - self.height(node.right)注意两个规定叶节点高度为 0空节点高度为 -1节点平衡因子定义为左子树高度减去右子树高度空节点平衡因子为 0。由此可得AVL 树中任意节点的平衡因子 f 满足 $-1 \le f \le 1$。这里还有一个 C 侧的设计细节值得注意height()是访问节点高度的公共接口类似vector.size()因此放在public区而updateHeight()只是插入、删除操作中的一步用户单独调用它没有意义因此放在private区见 QA。7.3 四种旋转操作AVL 树的核心在于“旋转”它能在不改变中序遍历序列的前提下使失衡节点平衡因子绝对值 1重新恢复平衡——既保持二叉搜索树性质又让树重新成为平衡二叉树。以右旋为例处理左偏失衡node为失衡节点、child为其左子节点、grand_child为child的右子节点def right_rotate(self, node: TreeNode | None) - TreeNode | None: 右旋操作 child node.left grand_child child.right # 以 child 为原点将 node 向右旋转 child.right node node.left grand_child # 更新节点高度 self.update_height(node) self.update_height(child) # 返回旋转后子树的根节点 return child左旋与右旋逻辑上镜像对称分别解决两种对称的失衡情况——只需把右旋代码中所有left换成right、所有right换成left即可得到left_rotate()源码中确实如此实现。四种失衡情况分别对应右旋、先左旋后右旋、先右旋后左旋、左旋。判断条件如下表通过失衡节点与较高一侧子节点的平衡因子符号确定失衡节点的平衡因子子节点的平衡因子应采用的旋转方法$ 1$ 左偏树$\geq 0$右旋$ 1$ 左偏树$ 0$先左旋后右旋$ -1$ 右偏树$\leq 0$左旋$ -1$ 右偏树$ 0$先右旋后左旋四种情况统一封装进rotate()函数def rotate(self, node: TreeNode | None) - TreeNode | None: 执行旋转操作使该子树重新恢复平衡 # 获取节点 node 的平衡因子 balance_factor self.balance_factor(node) # 左偏树 if balance_factor 1: if self.balance_factor(node.left) 0: # 右旋 return self.right_rotate(node) else: # 先左旋后右旋 node.left self.left_rotate(node.left) return self.right_rotate(node) # 右偏树 elif balance_factor -1: if self.balance_factor(node.right) 0: # 左旋 return self.left_rotate(node) else: # 先右旋后左旋 node.right self.right_rotate(node.right) return self.left_rotate(node) # 平衡树无须旋转直接返回 return node7.4 插入与删除自底向上执行旋转AVL 树的插入与二叉搜索树在主体上类似唯一区别是插入或删除后从该节点到根节点的路径上可能出现一系列失衡节点需要自底向上执行旋转使所有失衡节点恢复平衡。从源码结构看insert_helper()是一个“递归插入 返回阶段旋转”的结构def insert_helper(self, node: TreeNode | None, val: int) - TreeNode: 递归插入节点辅助方法 if node is None: return TreeNode(val) # 1. 查找插入位置并插入节点 if val node.val: node.left self.insert_helper(node.left, val) elif val node.val: node.right self.insert_helper(node.right, val) else: # 重复节点不插入直接返回 return node # 更新节点高度 self.update_height(node) # 2. 执行旋转操作使该子树重新恢复平衡 return self.rotate(node)关键在于返回值每层递归在子树返回后先update_height再调用rotate并把可能变化的子树根回传给上一层——旋转发生在“归”阶段因此天然自底向上。remove_helper()的删除逻辑同样是先完成二叉搜索树式的删除度为 0/1 直接替换、度为 2 用中序后继覆盖再执行update_height与rotate查找操作则与二叉搜索树完全一致。AVL 树的典型应用包括组织和存储大型数据适合高频查找、低频增删场景、构建数据库索引系统。作为对照红黑树也是一种常见的平衡二叉搜索树其平衡条件更宽松插入与删除所需的旋转更少节点增删的平均效率更高。八、Q A 全解以下问答完整继承自 summary.md并结合源码给出可验证的依据。Q1对于只有一个节点的二叉树树的高度和根节点的深度都是 0 吗是的因为高度和深度通常定义为“经过的边的数量”单节点树没有边。Q2二叉树中的插入与删除一般由“一套操作”配合完成这里的“一套操作”指什么可以理解为“资源释放 结构调整”的组合。以二叉搜索树为例删除节点分度为 0、1、2 三种情况每种情况都要经过查找、替换、递归删除等多个步骤见上文 binary_search_tree.py 的remove()。Q3为什么 DFS 遍历有前、中、后三种顺序分别有什么用与顺序/逆序遍历数组类似前序、中序、后序是三种二叉树遍历方法用于得到特定顺序的遍历结果。典型例子是二叉搜索树由于满足左子节点值 根节点值 右子节点值按“左 → 根 → 右”的优先级中序遍历就能得到有序节点序列。Q4右旋只处理node、child、grand_child之间的关系node与其父节点的连接不需要维护吗旋转后岂不是断掉了需要从递归的视角来看right_rotate(root)传入的是子树的根节点函数最终return child返回旋转后子树的新根。子树根与其父节点的连接是在该函数返回后由上层调用完成的如insert_helper中的node.left self.left_rotate(node.left)不属于旋转操作本身的维护范围。Q5C 中height()与updateHeight()为何分别放在public和private看方法的使用范围只在类内部使用的方法设计为private。用户单独调用updateHeight()没有意义它只是插入、删除操作中的一步而height()是访问节点高度类似vector.size()设置成public便于外部使用。Q6如何从一组输入数据构建二叉搜索树根节点的选择重要吗很重要。构建方法见 build_tree.py 所在仓库的build_tree()实现通常先将输入数据排序把中点元素作为根节点再递归构建左右子树以最大程度保证树的平衡性。Q7Java 中字符串对比一定要用equals()吗不一定。对基本类型比较值是否相等对引用类型比较两个变量是否指向同一个对象内存位置是否相同equals()比较两个对象的值是否相等。因此比较值应使用equals()。但注意String a hi; String b hi;中两个字符串都存储在字符串常量池、指向同一对象所以此处a b也成立。Q8广度优先遍历到最底层之前队列中的节点数量是 $2^h$ 吗是的。例如高度 $h 2$ 的满二叉树节点总数 $n 7$底层节点数量 $4 2^h (n 1) / 2$。九、知识脉络小结与延伸阅读把本小结的 11 条重点串起来就是一条清晰的认知链路节点结构一分为二→ 术语与类型完美/完全/完满/平衡→ 数组表示索引映射 2i1、2i2→ 遍历BFS 层序 DFS 前中后→ 二叉搜索树对数级增删查、中序有序、可退化为链表→ AVL 树高度、平衡因子、四种旋转、自底向上恢复平衡。仓库中可直接运行、验证的对应实现codes/python/chapter_tree/binary_tree.py节点定义、初始化、插入与删除codes/python/chapter_tree/array_binary_tree.py数组表示与四种遍历codes/python/chapter_tree/binary_tree_bfs.py层序遍历codes/python/chapter_tree/binary_tree_dfs.py前序、中序、后序遍历codes/python/chapter_tree/binary_search_tree.pyBST 查找、插入、删除三种情况codes/python/chapter_tree/avl_tree.pyAVL 树完整实现旋转 插入 删除其__main__部分按顺序演示了插入节点 1、2、3、4、5、8、7、9、10、6 以及删除度为 0、1、2 三类节点时树的平衡过程。对应的章节文档为 binary_tree.md、array_representation_of_tree.md、binary_tree_traversal.md、binary_search_tree.md 与 avl_tree.md各语言版本的实现可在 codes/ 目录下按chapter_tree/目录同名文件对照阅读。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法二叉树篇完整笔记：从节点结构、遍历策略到 AVL 树旋转的体系化回顾
Hello 算法二叉树篇完整笔记从节点结构、遍历策略到 AVL 树旋转的体系化回顾【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本文基于《Hello 算法》仓库的树章节小结 summary.md对二叉树的核心知识体系做一次系统回顾从节点结构与常用术语到层序遍历BFS与三种深度优先遍历DFS再到二叉搜索树的增删查与 AVL 树的四种旋转操作。读完后你可以对照仓库中多语言实现如 avl_tree.py、binary_search_tree.py逐行验证每一条结论建立起一套可自洽推导的树结构知识框架。一、二叉树的基本概念与节点结构二叉树binary tree是一种非线性数据结构体现“一分为二”的分治逻辑。与链表类似二叉树的基本单元是节点每个节点包含一个值以及两个指针引用分别指向其左子节点和右子节点。对二叉树中的某个节点其左右子节点及其以下形成的树被称为该节点的左右子树。以 Python 实现为例节点定义如下见 binary_tree.py 与文档 binary_tree.mdclass TreeNode: 二叉树节点类 def __init__(self, val: int): self.val: int val # 节点值 self.left: TreeNode | None None # 左子节点引用 self.right: TreeNode | None None # 右子节点引用二叉树的常用术语包括根节点root node位于顶层、没有父节点的节点叶节点leaf node没有子节点的节点两个指针均指向None边edge连接两个节点的线段即节点引用指针层level从顶至底递增根节点所在层为 1度degree节点的子节点数量在二叉树中取值为 0、1、2高度height从根节点到最远叶节点所经过的边的数量深度depth从根节点到某节点所经过的边的数量。请注意高度与深度通常定义为“经过的边的数量”但部分题目或教材会将其定义为“经过的节点的数量”。此时高度和深度都需要加 1详见下文 QA 第一条。初始化二叉树与链表类似先初始化节点再构建节点之间的引用指针# 初始化节点 n1 TreeNode(val1) n2 TreeNode(val2) n3 TreeNode(val3) n4 TreeNode(val4) n5 TreeNode(val5) # 构建节点之间的引用指针 n1.left n2 n1.right n3 n2.left n4 n2.right n5插入与删除节点同样通过修改指针实现。以在n1 - n2之间插入节点 P 为例# 插入与删除节点 p TreeNode(0) # 在 n1 - n2 中间插入节点 P n1.left p p.left n2 # 删除节点 P n1.left n2需要注意的是插入节点可能会改变二叉树的原有逻辑结构而删除节点通常意味着删除该节点及其所有子树。因此二叉树中的插入与删除通常由一套操作配合完成以实现有实际意义的操作——这一点在二叉搜索树与 AVL 树的删除实现中会得到具体印证。二、常见二叉树类型与二叉树的退化小结中列出四种常见类型完美二叉树、完全二叉树、完满二叉树和平衡二叉树。其中完美二叉树中文社区常称“满二叉树”所有层的节点都被完全填满叶节点度为 0、其余节点度均为 2若高度为 h 则节点总数为 $2^{h1} - 1$完全二叉树仅允许最底层不完全填满且从左至右连续填充完满二叉树除叶节点外每个节点都有两个子节点平衡二叉树则要求任意节点左右子树高度差的绝对值不超过 1。完美二叉树是最理想的状态链表是退化后的最差状态。下表对比了两类极端结构下的关键指标完美二叉树链表第 $i$ 层的节点数量$2^{i-1}$$1$高度为 $h$ 的树的叶节点数量$2^h$$1$高度为 $h$ 的树的节点总数$2^{h1} - 1$$h 1$节点总数为 $n$ 的树的高度$\log_2 (n1) - 1$$n - 1$这一退化问题贯穿整个树章节二叉搜索树在频繁增删后退化为链表时各项操作复杂度从 $O(\log n)$ 劣化至 $O(n)$这正是 AVL 树要解决的核心问题。三、二叉树的数组表示除了链表指针表示二叉树也可以用数组表示。方法是将节点值和空位按层序遍历顺序排列并借助父节点与子节点之间的索引映射关系来“实现指针”若某节点的索引为 i则其左子节点索引为 $2i 1$右子节点索引为 $2i 2$。对于非完美二叉树中间层存在许多空位仅凭层序序列无法唯一确定树结构因此需要在序列中显式写出空位None。示例# 二叉树的数组表示 # 使用 None 来表示空位 tree [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15]仓库中 array_binary_tree.py 给出了完整的数组表示实现其核心就是三个索引函数def left(self, i: int) - int | None: 获取索引为 i 节点的左子节点的索引 return 2 * i 1 def right(self, i: int) - int | None: 获取索引为 i 节点的右子节点的索引 return 2 * i 2 def parent(self, i: int) - int | None: 获取索引为 i 节点的父节点的索引 return (i - 1) // 2其中父节点索引 $(i-1) // 2$ 是层序映射的逆运算。该文件还实现了层序遍历直接顺序扫过数组、跳过空位以及前序、中序、后序遍历基于索引映射的递归完整覆盖了文档 array_representation_of_tree.md 所述的操作集合。完全二叉树非常适合数组表示空位只出现在序列末尾可以省略存储。数组表示的优点是内存连续、缓存友好、无需指针、支持随机访问局限性则是需要连续内存、增删节点需移动数组元素、空位过多时空间利用率低。四、层序遍历广度优先搜索BFS层序遍历从顶部到底部逐层访问二叉树每层按从左到右的顺序访问节点。它本质上属于广度优先遍历breadth-first search, BFS体现“一圈一圈向外扩展”的逐层遍历方式通常借助队列实现——队列“先进先出”的规则与 BFS“逐层推进”的思想是一致的。binary_tree_bfs.py 中的level_order()实现如下def level_order(root: TreeNode | None) - list[int]: 层序遍历 # 初始化队列加入根节点 queue: deque[TreeNode] deque() queue.append(root) # 初始化一个列表用于保存遍历序列 res [] while queue: node: TreeNode queue.popleft() # 队列出队 res.append(node.val) # 保存节点值 if node.left is not None: queue.append(node.left) # 左子节点入队 if node.right is not None: queue.append(node.right) # 右子节点入队 return res复杂度分析时间复杂度 $O(n)$所有节点被访问一次空间复杂度 $O(n)$在最差情况下满二叉树遍历到最底层之前队列中最多同时存在 $(n 1) / 2$ 个节点。关于队列规模有一个值得玩味的事实广度优先遍历到最底层之前队列中的节点数量恰为 $2^h$例如高度 $h 2$ 的满二叉树节点总数 $n 7$底层节点数量 $4 2^h (n1)/2$。五、前序、中序、后序遍历深度优先搜索DFS前序、中序、后序遍历皆属于深度优先遍历depth-first search, DFS体现“先走到尽头再回溯继续”的遍历方式通常使用递归来实现。深度优先遍历就像绕着整棵二叉树的外围“走”一圈每个节点都会被遇到三次分别对应前、中、后三种访问时机。binary_tree_dfs.py 中三种遍历只差一行res.append(root.val)的位置def pre_order(root: TreeNode | None): 前序遍历 if root is None: return # 访问优先级根节点 - 左子树 - 右子树 res.append(root.val) pre_order(rootroot.left) pre_order(rootroot.right) def in_order(root: TreeNode | None): 中序遍历 if root is None: return # 访问优先级左子树 - 根节点 - 右子树 in_order(rootroot.left) res.append(root.val) in_order(rootroot.right) def post_order(root: TreeNode | None): 后序遍历 if root is None: return # 访问优先级左子树 - 右子树 - 根节点 post_order(rootroot.left) post_order(rootroot.right) res.append(root.val)递归过程可分为“递”与“归”两个逆向阶段“递”表示开启新调用、访问下一个节点“归”表示函数返回、当前节点访问完毕。复杂度方面时间复杂度为 $O(n)$空间复杂度为 $O(n)$——在最差情况下树退化为链表递归深度达到 n系统占用 $O(n)$ 栈帧空间。深度优先遍历也可以基于迭代实现通常借助显式栈这里以递归为主。六、二叉搜索树查找、插入、删除与中序有序二叉搜索树binary search tree满足根节点的值介于左、右子树所有节点的值之间左 根 右且任意节点的左右子树也是二叉搜索树。其查找、插入、删除操作的时间复杂度均为 $O(\log n)$当树退化为链表时各项复杂度劣化至 $O(n)$。仓库中 binary_search_tree.py 的BinarySearchTree类封装了这三项操作是理解“一套操作配合完成”的最佳样本。6.1 查找节点查找与二分查找原理一致每轮排除一半情况循环次数最多为树高def search(self, num: int) - TreeNode | None: 查找节点 cur self._root # 循环查找越过叶节点后跳出 while cur is not None: # 目标节点在 cur 的右子树中 if cur.val num: cur cur.right # 目标节点在 cur 的左子树中 elif cur.val num: cur cur.left # 找到目标节点跳出循环 else: break return cur6.2 插入节点插入分两步循环查找插入位置、在该位置插入节点。实现上有两个关键细节树中不允许重复节点遇到重复值直接返回用辅助指针pre保存上一轮节点以便在遍历至None时拿到父节点完成挂接def insert(self, num: int): 插入节点 # 若树为空则初始化根节点 if self._root is None: self._root TreeNode(num) return # 循环查找越过叶节点后跳出 cur, pre self._root, None while cur is not None: # 找到重复节点直接返回 if cur.val num: return pre cur # 插入位置在 cur 的右子树中 if cur.val num: cur cur.right # 插入位置在 cur 的左子树中 else: cur cur.left # 插入节点 node TreeNode(num) if pre.val num: pre.right node else: pre.left node6.3 删除节点分三种情况删除操作要分待删除节点的子节点数量为 0、1、2 三种情况处理每种情况都需要多步节点操作这正是小结 QA 中“一套操作”的具体含义。其中度为 2 的情况最复杂无法直接删除需要用右子树的最小节点即中序遍历的下一个节点覆盖当前节点再递归删除那个后继节点# 子节点数量 0 or 1 if cur.left is None or cur.right is None: child cur.left or cur.right # 删除节点 cur if cur ! self._root: if pre.left cur: pre.left child else: pre.right child else: # 若删除节点为根节点则重新指定根节点 self._root child # 子节点数量 2 else: # 获取中序遍历中 cur 的下一个节点 tmp: TreeNode cur.right while tmp.left is not None: tmp tmp.left # 递归删除节点 tmp self.remove(tmp.val) # 用 tmp 覆盖 cur cur.val tmp.val删除总耗时 $O(\log n)$查找待删除节点 $O(\log n)$获取中序后继 $O(\log n)$。6.4 中序遍历有序与效率对比由于中序遍历遵循“左 → 根 → 右”的顺序而二叉搜索树满足“左 根 右”的大小关系所以二叉搜索树的中序遍历序列天然升序获取有序数据仅需 $O(n)$ 时间无需额外排序。这也是“为什么 DFS 有前中后三种顺序”的实战答案之一见 QA。与无序数组对比源自 binary_search_tree.md无序数组二叉搜索树查找元素$O(n)$$O(\log n)$插入元素$O(1)$$O(\log n)$删除元素$O(n)$$O(\log n)$只有在高频添加、低频查找删除数据的场景下数组才比二叉搜索树效率更高。常见应用包括系统多级索引、搜索算法的底层数据结构、以及保持数据流有序状态。七、AVL 树用旋转操作维持平衡7.1 为什么需要 AVL 树不断插入和删除节点可能使二叉搜索树退化为链表例如删除两个节点后树就变成链状各种操作的复杂度随之从 $O(\log n)$ 劣化为 $O(n)$。1962 年 G. M. Adelson-Velsky 和 E. M. Landis 在论文“An algorithm for the organization of information”中提出AVL 树通过一系列操作确保持续增删节点后树不会退化使各种操作稳定保持在 $O(\log n)$ 级别。7.2 节点高度与平衡因子AVL 树既是二叉搜索树也是平衡二叉树是平衡二叉搜索树balanced binary search tree。为此节点类增加了height变量并配套两个工具函数avl_tree.pydef height(self, node: TreeNode | None) - int: 获取节点高度 # 空节点高度为 -1 叶节点高度为 0 if node is not None: return node.height return -1 def update_height(self, node: TreeNode | None): 更新节点高度 # 节点高度等于最高子树高度 1 node.height max([self.height(node.left), self.height(node.right)]) 1 def balance_factor(self, node: TreeNode | None) - int: 获取平衡因子 # 空节点平衡因子为 0 if node is None: return 0 # 节点平衡因子 左子树高度 - 右子树高度 return self.height(node.left) - self.height(node.right)注意两个规定叶节点高度为 0空节点高度为 -1节点平衡因子定义为左子树高度减去右子树高度空节点平衡因子为 0。由此可得AVL 树中任意节点的平衡因子 f 满足 $-1 \le f \le 1$。这里还有一个 C 侧的设计细节值得注意height()是访问节点高度的公共接口类似vector.size()因此放在public区而updateHeight()只是插入、删除操作中的一步用户单独调用它没有意义因此放在private区见 QA。7.3 四种旋转操作AVL 树的核心在于“旋转”它能在不改变中序遍历序列的前提下使失衡节点平衡因子绝对值 1重新恢复平衡——既保持二叉搜索树性质又让树重新成为平衡二叉树。以右旋为例处理左偏失衡node为失衡节点、child为其左子节点、grand_child为child的右子节点def right_rotate(self, node: TreeNode | None) - TreeNode | None: 右旋操作 child node.left grand_child child.right # 以 child 为原点将 node 向右旋转 child.right node node.left grand_child # 更新节点高度 self.update_height(node) self.update_height(child) # 返回旋转后子树的根节点 return child左旋与右旋逻辑上镜像对称分别解决两种对称的失衡情况——只需把右旋代码中所有left换成right、所有right换成left即可得到left_rotate()源码中确实如此实现。四种失衡情况分别对应右旋、先左旋后右旋、先右旋后左旋、左旋。判断条件如下表通过失衡节点与较高一侧子节点的平衡因子符号确定失衡节点的平衡因子子节点的平衡因子应采用的旋转方法$ 1$ 左偏树$\geq 0$右旋$ 1$ 左偏树$ 0$先左旋后右旋$ -1$ 右偏树$\leq 0$左旋$ -1$ 右偏树$ 0$先右旋后左旋四种情况统一封装进rotate()函数def rotate(self, node: TreeNode | None) - TreeNode | None: 执行旋转操作使该子树重新恢复平衡 # 获取节点 node 的平衡因子 balance_factor self.balance_factor(node) # 左偏树 if balance_factor 1: if self.balance_factor(node.left) 0: # 右旋 return self.right_rotate(node) else: # 先左旋后右旋 node.left self.left_rotate(node.left) return self.right_rotate(node) # 右偏树 elif balance_factor -1: if self.balance_factor(node.right) 0: # 左旋 return self.left_rotate(node) else: # 先右旋后左旋 node.right self.right_rotate(node.right) return self.left_rotate(node) # 平衡树无须旋转直接返回 return node7.4 插入与删除自底向上执行旋转AVL 树的插入与二叉搜索树在主体上类似唯一区别是插入或删除后从该节点到根节点的路径上可能出现一系列失衡节点需要自底向上执行旋转使所有失衡节点恢复平衡。从源码结构看insert_helper()是一个“递归插入 返回阶段旋转”的结构def insert_helper(self, node: TreeNode | None, val: int) - TreeNode: 递归插入节点辅助方法 if node is None: return TreeNode(val) # 1. 查找插入位置并插入节点 if val node.val: node.left self.insert_helper(node.left, val) elif val node.val: node.right self.insert_helper(node.right, val) else: # 重复节点不插入直接返回 return node # 更新节点高度 self.update_height(node) # 2. 执行旋转操作使该子树重新恢复平衡 return self.rotate(node)关键在于返回值每层递归在子树返回后先update_height再调用rotate并把可能变化的子树根回传给上一层——旋转发生在“归”阶段因此天然自底向上。remove_helper()的删除逻辑同样是先完成二叉搜索树式的删除度为 0/1 直接替换、度为 2 用中序后继覆盖再执行update_height与rotate查找操作则与二叉搜索树完全一致。AVL 树的典型应用包括组织和存储大型数据适合高频查找、低频增删场景、构建数据库索引系统。作为对照红黑树也是一种常见的平衡二叉搜索树其平衡条件更宽松插入与删除所需的旋转更少节点增删的平均效率更高。八、Q A 全解以下问答完整继承自 summary.md并结合源码给出可验证的依据。Q1对于只有一个节点的二叉树树的高度和根节点的深度都是 0 吗是的因为高度和深度通常定义为“经过的边的数量”单节点树没有边。Q2二叉树中的插入与删除一般由“一套操作”配合完成这里的“一套操作”指什么可以理解为“资源释放 结构调整”的组合。以二叉搜索树为例删除节点分度为 0、1、2 三种情况每种情况都要经过查找、替换、递归删除等多个步骤见上文 binary_search_tree.py 的remove()。Q3为什么 DFS 遍历有前、中、后三种顺序分别有什么用与顺序/逆序遍历数组类似前序、中序、后序是三种二叉树遍历方法用于得到特定顺序的遍历结果。典型例子是二叉搜索树由于满足左子节点值 根节点值 右子节点值按“左 → 根 → 右”的优先级中序遍历就能得到有序节点序列。Q4右旋只处理node、child、grand_child之间的关系node与其父节点的连接不需要维护吗旋转后岂不是断掉了需要从递归的视角来看right_rotate(root)传入的是子树的根节点函数最终return child返回旋转后子树的新根。子树根与其父节点的连接是在该函数返回后由上层调用完成的如insert_helper中的node.left self.left_rotate(node.left)不属于旋转操作本身的维护范围。Q5C 中height()与updateHeight()为何分别放在public和private看方法的使用范围只在类内部使用的方法设计为private。用户单独调用updateHeight()没有意义它只是插入、删除操作中的一步而height()是访问节点高度类似vector.size()设置成public便于外部使用。Q6如何从一组输入数据构建二叉搜索树根节点的选择重要吗很重要。构建方法见 build_tree.py 所在仓库的build_tree()实现通常先将输入数据排序把中点元素作为根节点再递归构建左右子树以最大程度保证树的平衡性。Q7Java 中字符串对比一定要用equals()吗不一定。对基本类型比较值是否相等对引用类型比较两个变量是否指向同一个对象内存位置是否相同equals()比较两个对象的值是否相等。因此比较值应使用equals()。但注意String a hi; String b hi;中两个字符串都存储在字符串常量池、指向同一对象所以此处a b也成立。Q8广度优先遍历到最底层之前队列中的节点数量是 $2^h$ 吗是的。例如高度 $h 2$ 的满二叉树节点总数 $n 7$底层节点数量 $4 2^h (n 1) / 2$。九、知识脉络小结与延伸阅读把本小结的 11 条重点串起来就是一条清晰的认知链路节点结构一分为二→ 术语与类型完美/完全/完满/平衡→ 数组表示索引映射 2i1、2i2→ 遍历BFS 层序 DFS 前中后→ 二叉搜索树对数级增删查、中序有序、可退化为链表→ AVL 树高度、平衡因子、四种旋转、自底向上恢复平衡。仓库中可直接运行、验证的对应实现codes/python/chapter_tree/binary_tree.py节点定义、初始化、插入与删除codes/python/chapter_tree/array_binary_tree.py数组表示与四种遍历codes/python/chapter_tree/binary_tree_bfs.py层序遍历codes/python/chapter_tree/binary_tree_dfs.py前序、中序、后序遍历codes/python/chapter_tree/binary_search_tree.pyBST 查找、插入、删除三种情况codes/python/chapter_tree/avl_tree.pyAVL 树完整实现旋转 插入 删除其__main__部分按顺序演示了插入节点 1、2、3、4、5、8、7、9、10、6 以及删除度为 0、1、2 三类节点时树的平衡过程。对应的章节文档为 binary_tree.md、array_representation_of_tree.md、binary_tree_traversal.md、binary_search_tree.md 与 avl_tree.md各语言版本的实现可在 codes/ 目录下按chapter_tree/目录同名文件对照阅读。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考