专题进阶 · 树与范围查询推荐总顺序 · 第 44 / 148 课

用空树作为递归基例,明确节点数、深度、高度与子树之间的关系。

先学会这些,再进入本课 递归与调用栈
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 树与范围查询

二叉树Binary Tree

每个节点最多两个孩子,递归地处理左、右子树。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用空树作为递归基例,明确节点数、深度、高度与子树之间的关系。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

一棵树的根为 4,左孩子 2,右孩子 7,节点 2 又有孩子 1 和 3。怎样计算节点总数与高度?

02一步步得到方法

树是递归定义的数据结构

二叉树要么为空,要么由一个根节点和两棵二叉子树组成。每个节点最多两个孩子,但不要求左右子树大小相同,也不要求节点值有序。二叉搜索树、完全二叉树是额外约束,不能混用。

本课用节点数定义高度:空树高度 0,叶子高度 1。另一些资料按边数计高度,空树可能为 −1、叶子为 0;两套约定都能用,公式必须前后一致。

先问孩子,再合成父亲

节点数 count(t)=1+count(left)+count(right)。高度 height(t)=1+max(height(left),height(right))。两个量看起来都递归,但合并操作不同:计数相加,高度取最长路径。

树保证每个非根节点只有一个父节点且没有环,因此递归不会绕回。若数据结构可能共享节点或含环,它已经是图,需要 visited 或重新定义计数语义。

结构性质与存储约定分开

二叉树只限制每个节点最多两个孩子,不自动规定键值大小关系。二叉搜索树、完全二叉树和满二叉树各有额外条件,不能仅凭画成二叉分支就使用它们的性质。

用数组按 2i+1、2i+2 存孩子适合结构稠密的完全树。链式节点更灵活地表示稀疏树;如果为倾斜树强行保留所有空位置,数组索引会快速增长。

03把一个小例子完全算清楚

树 4(2(1,3),7),括号表示左右子树。

步骤计算与状态为什么这样做
叶子 1、3、7各返回 (节点数1,高度1)空孩子贡献 (0,0)
节点 2(1+1+1,1+max(1,1))=(3,2)合并左右结果
根 4(1+3+1,1+max(2,1))=(5,3)整树结果

窄屏可左右滑动表格,阅读完整计算与理由。

整树 5 个节点,高度 3;根到节点 1 的路径有 3 个节点、2 条边。

04为什么这个方法成立

  1. 空树返回正确的零规模。
  2. 若左右子树结果正确,节点集合互不重叠,加上根就得到正确计数。
  3. 最长根到叶路径必经过左或右子树之一,因此取较大高度再加根。

05把推导翻译成代码

Python · 可独立运行的教学实现

class Node:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def measure(node):
    if node is None:
        return 0, 0
    ln, lh = measure(node.left)
    rn, rh = measure(node.right)
    return 1 + ln + rn, 1 + max(lh, rh)

逐个理解关键决定

return 0, 0
空树为递归提供终止条件和合并单位。
measure(node.left)
子问题只依赖子树,不需要携带整棵树的数组下标。

06时间、空间与实现范围

每个节点访问一次,时间 O(n),递归栈 O(h)。平衡树 h=O(log n),单链形状 h=O(n)。

本函数同时求两个量,避免每个节点再单独扫描整棵子树求高而导致重复工作。

07改变条件,检查哪里会出错

二叉树高度总是 log n

退化链可以高达 n;只有平衡等额外条件才能保证对数高度。

把二叉树都当作高度 log n

极度倾斜的树高度可达 n−1,递归栈和搜索成本都会随之增加。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

一棵只有根的树返回什么?

需要一点提示

两个孩子都是空。

查看解析与答案

(1,1)。

练习 2 · 边界与辨析

同一节点被左右孩子同时指向,会怎样?

需要一点提示

输入是否还是树?

查看解析与答案

递归会重复计数,该结构不满足普通树的唯一父节点约定,应改按图处理或修复输入。

练习 3 · 变式与迁移

怎样同时计算叶子数?

需要一点提示

叶子没有两个孩子。

查看解析与答案

空树 0;叶子 1;其他节点返回两棵子树叶子数之和,仍可在一次后序遍历中完成。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 查找结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。