Hello 算法二叉树篇完整笔记：从节点结构、遍历策略到 AVL 树旋转的体系化回顾

本文基于《Hello 算法》仓库的树章节小结 summary.md，对二叉树的核心知识体系做一次系统回顾：从节点结构与常用术语，到层序遍历（BFS）与三种深度优先遍历（DFS），再到二叉搜索树的增删查与 AVL 树的四种旋转操作。读完后，你可以对照仓库中多语言实现（如 avl_tree.py、binary_search_tree.py）逐行验证每一条结论，建立起一套可自洽推导的树结构知识框架。

一、二叉树的基本概念与节点结构

二叉树（binary tree）是一种非线性数据结构，体现“一分为二”的分治逻辑。 与链表类似，二叉树的基本单元是节点，每个节点包含一个值以及两个指针（引用），分别指向其左子节点和右子节点。对二叉树中的某个节点，其左（右）子节点及其以下形成的树被称为该节点的左（右）子树。

以 Python 实现为例，节点定义如下（见 binary_tree.py 与文档 binary_tree.md）：

class 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（详见下文 Q&A 第一条）。

初始化二叉树与链表类似：先初始化节点，再构建节点之间的引用（指针）：

# 初始化节点
n1 = TreeNode(val=1)
n2 = TreeNode(val=2)
n3 = TreeNode(val=3)
n4 = TreeNode(val=4)
n5 = TreeNode(val=5)
# 构建节点之间的引用（指针）
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^{h+1} - 1$；完全二叉树仅允许最底层不完全填满且从左至右连续填充；完满二叉树除叶节点外每个节点都有两个子节点；平衡二叉树则要求任意节点左右子树高度差的绝对值不超过 1。

完美二叉树是最理想的状态，链表是退化后的最差状态。 下表对比了两类极端结构下的关键指标：

	完美二叉树	链表
第 $i$ 层的节点数量	$2^{i-1}$	$1$
高度为 $h$ 的树的叶节点数量	$2^h$	$1$
高度为 $h$ 的树的节点总数	$2^{h+1} - 1$	$h + 1$
节点总数为 $n$ 的树的高度	$\log_2 (n+1) - 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)\mathrm{/}\mathrm{/}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 = (n+1)/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(root=root.left)
    pre_order(root=root.right)

def in_order(root: TreeNode | None):
    """中序遍历"""
    if root is None:
        return
    # 访问优先级：左子树 -> 根节点 -> 右子树
    in_order(root=root.left)
    res.append(root.val)
    in_order(root=root.right)

def post_order(root: TreeNode | None):
    """后序遍历"""
    if root is None:
        return
    # 访问优先级：左子树 -> 右子树 -> 根节点
    post_order(root=root.left)
    post_order(root=root.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 cur

6.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 = node

6.3 删除节点：分三种情况

删除操作要分待删除节点的子节点数量为 0、1、2 三种情况处理，每种情况都需要多步节点操作，这正是小结 Q&A 中“一套操作”的具体含义。其中度为 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 有前中后三种顺序”的实战答案之一（见 Q&A）。

与无序数组对比（源自 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.py）：

def 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 区（见 Q&A）。

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 node

7.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)），不属于旋转操作本身的维护范围。

Q5：C++ 中 height() 与 updateHeight() 为何分别放在 public 和 private？

看方法的使用范围：只在类内部使用的方法设计为 private。用户单独调用 updateHeight() 没有意义，它只是插入、删除操作中的一步；而 height() 是访问节点高度，类似 vector.size()，设置成 public 便于外部使用。

Q6：如何从一组输入数据构建二叉搜索树？根节点的选择重要吗？

很重要。构建方法见 build_tree.py 所在仓库的 build_tree() 实现：通常先将输入数据排序，把中点元素作为根节点，再递归构建左右子树，以最大程度保证树的平衡性。

Q7：Java 中字符串对比一定要用 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 条重点串起来，就是一条清晰的认知链路：节点结构（一分为二）→ 术语与类型（完美/完全/完满/平衡）→ 数组表示（索引映射 2i+1、2i+2）→ 遍历（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.py：BST 查找、插入、删除（三种情况）；
• codes/python/chapter_tree/avl_tree.py：AVL 树完整实现（旋转 + 插入 + 删除），其 __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/ 目录同名文件对照阅读。