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为什么这个方法成立
- 空树返回正确的零规模。
- 若左右子树结果正确,节点集合互不重叠,加上根就得到正确计数。
- 最长根到叶路径必经过左或右子树之一,因此取较大高度再加根。
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)。
同一节点被左右孩子同时指向,会怎样?
需要一点提示
输入是否还是树?
查看解析与答案
递归会重复计数,该结构不满足普通树的唯一父节点约定,应改按图处理或修复输入。
怎样同时计算叶子数?
需要一点提示
叶子没有两个孩子。
查看解析与答案
空树 0;叶子 1;其他节点返回两棵子树叶子数之和,仍可在一次后序遍历中完成。