树的基础

树由节点和父子边组成。根是唯一没有父节点的节点；其余节点各有一个父节点，结构中没有环，所以从根到任意节点恰好只有一条路径。根、父节点、子节点、叶子、深度、高度和子树，都来自这些关系。树形结构用于目录层级、HTML、数据库索引等场景。

图中根位于上方，分支向下展开，没有子节点的是叶子。要区分两种距离：节点的深度从根向下数到该节点；节点的高度从它向下数到最深叶子。整棵树的高度就是根的高度。

树的组成

本课节点保存值、左子节点与右子节点，是最多有两个子节点的二叉树。沿子链接向下不会绕回起点，非根节点也不会同时属于两个父节点。

• 根：唯一没有父节点的节点，是本课遍历入口。
• 叶子：没有子节点。
• 内部节点：至少有一个子节点。
• 子树：某节点及其全部后代。每个子节点又是子树的根，因此可以递归处理。

本课用 A、B、C 等字母标记节点。普通树没有大小排序规则，左子节点不必小于父节点。二叉搜索树另有排序不变量，不能混为一谈。

逐步演示

默认 Lopsided 树不对称：

        A
      /   \
     B     C
    / \   /
   D   E F
      /
     G

关系为 A → B, C、B → D, E、C → F、E → G。共有七个节点。D、F、G 是叶子，A、B、C、E 是内部节点。C 只有一个子节点，B 有两个，都是合法结构。

1. 显示根：先出现 A，唯一没有父节点。
2. 逐层展开：先 B、C，再 D、E、F，最后 G。每条父子连接是一条边，共七个节点且无环。
3. 标出叶子：D、F、G 没有子节点。
4. 读取深度：按边数计，A 为 0；B、C 为 1；D、E、F 为 2；G 为 3。
5. 读取高度：最长根到叶路径是 A → B → E → G，共三条边，因此树高为 3，等于最大深度。
6. 比较形状：同样七个节点，平衡形状高度 2，当前偏斜形状高度 3，单链形状高度 6。节点数相同，高度仍可不同。

深度是从根到某节点的距离，高度是从某节点到最深叶子的距离。最深叶子的深度等于整棵树的高度。

七个节点，高度可以是 2 或 6

Balanced 预设每层填满，是完美二叉树，高度 2，已达到七节点二叉树的最小可能高度。Degenerate 预设除末尾外每个节点只有一个子节点，形成高度 n − 1 = 6 的链。

沿单条路径的树操作通常取决于高度。完整遍历仍需访问全部节点，但搜索树中的定位会受退化影响。AVL、红黑树维护平衡规则，让高度保持在对数级，而普通树不提供这项保证。

三种遍历顺序

递归访问同一棵树，只改变访问节点值的时机，就能得到三种顺序：

def traverse(node):
    if node is None:
        return
    # preorder:  visit here  -> node before its subtrees
    traverse(node.left)
    # inorder:   visit here  -> between left and right
    traverse(node.right)
    # postorder: visit here  -> node after its subtrees

• 前序，节点→左→右：A B D E G C F。先看到各子树的根，再看到内容，适合复制树或输出层级提纲。
• 中序，左→节点→右：D B G E A F C。节点出现在两棵子树之间。
• 后序，左→右→节点：D G E B F C A。后代先完成，父节点再处理，适合释放整棵树或计算子树大小。

三者都恰好访问每个节点一次，只改变顺序。本课展示结果，树遍历课再用调用栈逐帧解释递归过程。

边界情况

• 单节点：根也是叶子，深度和树高都是 0。本课按边计高度，可把空树高度约定为 −1，使单节点递归结果为 1 + (−1) = 0。
• 只有一个子节点：合法。默认 C 只有左子节点；二叉表示最多两个，不是必须两个。
• 退化链：高度 n − 1，路径访问像链表。
• 叶子深度不同：D、F 深度 2，G 深度 3；叶子不要求处在同一层。

常见错误

1. 混淆深度与高度。 深度从根算，高度向叶子算。深处的叶子可有很大深度，但高度仍为 0。
2. 把普通树当搜索树。 本课没有左小右大的规则；那是 BST 额外维护的条件。
3. 只把最底层当叶子。 没有子节点就是叶子，与所在层无关。
4. 混淆遍历顺序。 区别是节点在子树之前、之间还是之后访问，会改变完整输出和适用问题。
5. 假设树天然平衡。 普通树可以退化。小高度需要 AVL、红黑树等规则维护。