第11章树基础与二叉树理论

本章导读

树是最重要的非线性数据结构，广泛应用于文件系统、编译器、数据库索引等领域。本章从图论角度深入分析树的数学基础，包括树的等价定义、二叉树ADT规范、遍历算法的正确性证明，以及二叉树性质的形式化推导。

学习目标

完成本章学习后，读者将能够：

掌握树的多种等价数学定义
理解二叉树ADT的形式化规范
掌握遍历算法的正确性证明与复杂度分析
理解二叉树性质定理的数学推导
掌握树构造算法的唯一性条件

11.1 树的数学基础

11.1.1 树的等价定义

定义 11.1（树-图论定义） 树是一个连通无环无向图 $T = (V, E)$。

定义 11.2（树-递归定义） 树递归定义为：

基础情况：单个节点是树
递归步骤：若 $T_1, \ldots, T_k$ 是树，则添加一个新根节点连接 $T_1, \ldots, T_k$ 的根，得到的新结构是树

定理 11.1（树的等价刻画） 对于 $n$ 个顶点、$m$ 条边的图 $G$，以下命题等价：

$G$ 是树
$G$ 连通且 $m = n - 1$
$G$ 无环且 $m = n - 1$
$G$ 连通，但删除任意边后不连通
$G$ 无环，但添加任意边后产生环
$G$ 中任意两点间存在唯一路径

证明：证明 $(1) \Rightarrow (2) \Rightarrow (3) \Rightarrow (1)$ 形成循环。

$(1) \Rightarrow (2)$：树连通且无环。对 $n$ 归纳证明 $m = n - 1$。

$n = 1$：$m = 0 = n - 1$，成立
设 $n = k$ 时成立。考虑 $n = k + 1$ 的树 $T$。$T$ 至少有一个叶子节点 $v$（否则所有节点度 $\geq 2$，存在环）。删除 $v$ 得到 $k$ 个节点的树，由归纳假设有 $k - 1$ 条边。原树有 $(k - 1) + 1 = k$ 条边。

$(2) \Rightarrow (3)$：设 $G$ 连通且 $m = n - 1$。若 $G$ 有环，删除环上一边仍连通，得到 $n$ 个顶点、$n - 2$ 条边的连通图。但 $n$ 个顶点的连通图至少需要 $n - 1$ 条边，矛盾。

$(3) \Rightarrow (1)$：设 $G$ 无环且 $m = n - 1$。需证明 $G$ 连通。若 $G$ 有 $k$ 个连通分量，每个分量是树（无环），则总边数为 $n - k$。但 $m = n - 1$，故 $k = 1$，$G$ 连通。

其他等价性类似可证。∎

11.1.2 有根树与层次结构

定义 11.3（有根树） 有根树是指定了根节点的树，所有边具有方向（从父节点指向子节点）。

定义 11.4（树术语） 对于有根树 $T$：

根（Root）：没有父节点的唯一节点
叶子（Leaf）：没有子节点的节点
内部节点：非叶子节点
深度（Depth）：节点 $v$ 的深度 $d(v)$ 是从根到 $v$ 的路径长度
高度（Height）：节点 $v$ 的高度 $h(v)$ 是从 $v$ 到叶子的最长路径长度
树的高度：$h(T) = h(root)$
祖先/后代：若 $u$ 在根到 $v$ 的路径上，则 $u$ 是 $v$ 的祖先，$v$ 是 $u$ 的后代

定理 11.2（深度与高度关系） 对于任意节点 $v$：

$$d(v) + h(v) \leq h(T)$$

等号成立当且仅当 $v$ 在最长路径上。

证明：设 $v$ 到叶子的最长路径为 $P_v$，根到 $v$ 的路径为 $P_r$。$P_r$ 和 $P_v$ 的并是一条从根到叶子的路径，长度为 $d(v) + h(v)$。由于树高是根到叶子的最长路径长度，故 $d(v) + h(v) \leq h(T)$。∎

11.1.3 树ADT规范

ADT 11.1（Tree）

ADT Tree[T]
  Types: Tree[T]
  
  Operations:
    empty: → Tree[T]
    isLeaf: Tree[T] → Boolean
    root: Tree[T] → T
    children: Tree[T] → List[Tree[T]]
    height: Tree[T] → ℕ
    size: Tree[T] → ℕ
  
  Axioms:
    ∀t: Tree[T]
    (A1) isLeaf(empty) = true
    (A2) isLeaf(t) = (children(t) = [])
    (A3) size(empty) = 0
    (A4) size(t) = 1 + Σ size(c) for c in children(t)
    (A5) height(empty) = -1
    (A6) height(t) = 1 + max(height(c) for c in children(t))

11.2 二叉树理论

11.2.1 二叉树的数学定义

定义 11.5（二叉树） 二叉树是节点的有限集合，满足：

空集是二叉树
或者由根节点和左右两棵不相交的二叉树组成

定义 11.6（二叉树节点） 二叉树节点定义为：

$$Node = {value: T, left: Option[Node], right: Option[Node]}$$

其中 $Option[Node] = Node \cup {None}$。

定理 11.3（二叉树节点数与边数） $n$ 个节点的二叉树有 $n - 1$ 条边。

证明：每条边连接一个节点与其父节点，除根外每个节点有且仅有一个父节点。因此边数 = 节点数 - 1。∎

11.2.2 特殊二叉树

定义 11.7（满二叉树） 满二叉树是每个节点要么是叶子，要么有两个子节点的二叉树。

定义 11.8（完全二叉树） 完全二叉树是除最后一层外每层节点数达到最大，且最后一层节点从左到右连续排列的二叉树。

定义 11.9（完美二叉树） 完美二叉树是所有叶子在同一层，且每层节点数达到最大的二叉树。

定理 11.4（完美二叉树性质） 高度为 $h$ 的完美二叉树：

节点数：$n = 2^{h+1} - 1$
叶子数：$n_0 = 2^h$
内部节点数：$n_i = 2^h - 1$

证明：归纳证明。高度为 $0$ 的完美二叉树有 $1 = 2^1 - 1$ 个节点。

设高度为 $h - 1$ 的完美二叉树有 $2^h - 1$ 个节点。高度为 $h$ 的完美二叉树由根和两棵高度为 $h - 1$ 的完美子树组成：

$$n = 1 + 2(2^h - 1) = 2^{h+1} - 1$$

叶子在第 $h$ 层，数量为 $2^h$。内部节点数 = 总节点数 - 叶子数 = $2^{h+1} - 1 - 2^h = 2^h - 1$。∎

定理 11.5（完全二叉树的数组表示） 完全二叉树可以用数组紧凑表示，节点 $i$ 的：

左子节点：$2i + 1$
右子节点：$2i + 2$
父节点：$\lfloor(i-1)/2\rfloor$

证明：按层序编号，第 $k$ 层的第一个节点编号为 $2^k - 1$。节点 $i$ 所在层 $k = \lfloor \log_2(i+1) \rfloor$。

节点 $i$ 在第 $k$ 层的位置为 $i - 2^k + 1$。其左子节点在第 $k+1$ 层的位置为 $2(i - 2^k + 1)$，编号为 $2^{k+1} - 1 + 2(i - 2^k + 1) = 2i + 1$。∎

11.2.3 二叉树性质定理

定理 11.6（叶子与内部节点关系） 对于满二叉树，叶子节点数 $n_0$ 与内部节点数 $n_i$ 满足：

$$n_0 = n_i + 1$$

证明：设总节点数为 $n$，边数为 $e$。由定理 11.3，$e = n - 1$。

另一方面，每个内部节点有 2 条出边，故 $e = 2n_i$。

因此 $2n_i = n - 1 = n_0 + n_i - 1$，解得 $n_0 = n_i + 1$。∎

定理 11.7（任意二叉树的叶子数） 对于任意二叉树，设度为 0、1、2 的节点数分别为 $n_0, n_1, n_2$，则：

$$n_0 = n_2 + 1$$

证明：总节点数 $n = n_0 + n_1 + n_2$。

边数 $e = n - 1$（定理 11.3）。

另一方面，$e = n_1 + 2n_2$（度为 1 的节点贡献 1 条边，度为 2 的节点贡献 2 条边）。

因此 $n_1 + 2n_2 = n_0 + n_1 + n_2 - 1$，解得 $n_0 = n_2 + 1$。∎

定理 11.8（二叉树高度下界） $n$ 个节点的二叉树的最小高度为：

$$h_{min} = \lfloor \log_2 n \rfloor$$

证明：高度为 $h$ 的二叉树最多有 $2^{h+1} - 1$ 个节点（定理 11.4）。

因此 $n \leq 2^{h+1} - 1$，即 $h \geq \lfloor \log_2(n+1) \rfloor - 1 = \lfloor \log_2 n \rfloor$。∎

11.2.4 二叉树实现

python

from typing import TypeVar, Generic, Optional, List, Iterator, Callable, Tuple
from dataclasses import dataclass
from collections import deque

T = TypeVar('T')

@dataclass
class TreeNode(Generic[T]):
    """二叉树节点"""
    value: T
    left: Optional['TreeNode[T]'] = None
    right: Optional['TreeNode[T]'] = None
    
    def is_leaf(self) -> bool:
        return self.left is None and self.right is None
    
    def degree(self) -> int:
        return (1 if self.left else 0) + (1 if self.right else 0)


class BinaryTree(Generic[T]):
    """
    二叉树实现
    
    时间复杂度：
    - 遍历：O(n)
    - 高度计算：O(n)
    - 查找：O(n)
    
    空间复杂度：O(n)
    """
    
    def __init__(self, root: Optional[TreeNode[T]] = None):
        self.root = root
    
    def height(self) -> int:
        """计算树的高度 - O(n)"""
        def _height(node: Optional[TreeNode[T]]) -> int:
            if not node:
                return -1
            return 1 + max(_height(node.left), _height(node.right))
        return _height(self.root)
    
    def size(self) -> int:
        """计算节点数 - O(n)"""
        def _size(node: Optional[TreeNode[T]]) -> int:
            if not node:
                return 0
            return 1 + _size(node.left) + _size(node.right)
        return _size(self.root)
    
    def leaf_count(self) -> int:
        """计算叶子节点数 - O(n)"""
        def _count(node: Optional[TreeNode[T]]) -> int:
            if not node:
                return 0
            if node.is_leaf():
                return 1
            return _count(node.left) + _count(node.right)
        return _count(self.root)
    
    def node_count_by_degree(self) -> Tuple[int, int, int]:
        """统计各度数节点数 - O(n)"""
        n0, n1, n2 = 0, 0, 0
        
        def _count(node: Optional[TreeNode[T]]):
            nonlocal n0, n1, n2
            if not node:
                return
            deg = node.degree()
            if deg == 0:
                n0 += 1
            elif deg == 1:
                n1 += 1
            else:
                n2 += 1
            _count(node.left)
            _count(node.right)
        
        _count(self.root)
        return n0, n1, n2
    
    def is_balanced(self) -> bool:
        """判断是否为平衡二叉树 - O(n)"""
        def _check(node: Optional[TreeNode[T]]) -> int:
            if not node:
                return 0
            
            left_h = _check(node.left)
            if left_h == -1:
                return -1
            
            right_h = _check(node.right)
            if right_h == -1:
                return -1
            
            if abs(left_h - right_h) > 1:
                return -1
            
            return 1 + max(left_h, right_h)
        
        return _check(self.root) != -1
    
    def is_complete(self) -> bool:
        """判断是否为完全二叉树 - O(n)"""
        if not self.root:
            return True
        
        queue = deque([self.root])
        has_null = False
        
        while queue:
            node = queue.popleft()
            
            if not node:
                has_null = True
            else:
                if has_null:
                    return False
                queue.append(node.left)
                queue.append(node.right)
        
        return True
    
    def is_full(self) -> bool:
        """判断是否为满二叉树 - O(n)"""
        def _check(node: Optional[TreeNode[T]]) -> bool:
            if not node:
                return True
            if node.is_leaf():
                return True
            if not node.left or not node.right:
                return False
            return _check(node.left) and _check(node.right)
        
        return _check(self.root)
    
    def is_perfect(self) -> bool:
        """判断是否为完美二叉树 - O(n)"""
        h = self.height()
        n = self.size()
        return n == 2**(h + 1) - 1
    
    def __len__(self) -> int:
        return self.size()
    
    def __repr__(self) -> str:
        return f"BinaryTree(size={self.size()}, height={self.height()})"

11.3 二叉树遍历理论

11.3.1 遍历的定义

定义 11.10（前序遍历） 前序遍历按根-左子树-右子树的顺序访问节点。

定义 11.11（中序遍历） 中序遍历按左子树-根-右子树的顺序访问节点。

定义 11.12（后序遍历） 后序遍历按左子树-右子树-根的顺序访问节点。

定义 11.13（层序遍历） 层序遍历按从上到下、从左到右的顺序访问节点。

定理 11.9（遍历时间复杂度） 所有遍历算法的时间复杂度为 $O(n)$，空间复杂度为 $O(h)$（递归栈）或 $O(w)$（队列宽度）。

证明：每个节点被访问一次，故时间复杂度为 $O(n)$。递归深度最大为树高 $h$，层序遍历队列最大宽度为 $w$。∎

11.3.2 遍历实现

python

class BinaryTree(Generic[T]):
    
    def preorder(self) -> List[T]:
        """前序遍历（递归）- O(n)"""
        result = []
        
        def _traverse(node: Optional[TreeNode[T]]):
            if node:
                result.append(node.value)
                _traverse(node.left)
                _traverse(node.right)
        
        _traverse(self.root)
        return result
    
    def inorder(self) -> List[T]:
        """中序遍历（递归）- O(n)"""
        result = []
        
        def _traverse(node: Optional[TreeNode[T]]):
            if node:
                _traverse(node.left)
                result.append(node.value)
                _traverse(node.right)
        
        _traverse(self.root)
        return result
    
    def postorder(self) -> List[T]:
        """后序遍历（递归）- O(n)"""
        result = []
        
        def _traverse(node: Optional[TreeNode[T]]):
            if node:
                _traverse(node.left)
                _traverse(node.right)
                result.append(node.value)
        
        _traverse(self.root)
        return result
    
    def preorder_iterative(self) -> List[T]:
        """前序遍历（迭代）- O(n)"""
        result = []
        stack = [self.root]
        
        while stack:
            node = stack.pop()
            if node:
                result.append(node.value)
                stack.append(node.right)
                stack.append(node.left)
        
        return result
    
    def inorder_iterative(self) -> List[T]:
        """中序遍历（迭代）- O(n)"""
        result = []
        stack = []
        current = self.root
        
        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            
            current = stack.pop()
            result.append(current.value)
            current = current.right
        
        return result
    
    def postorder_iterative(self) -> List[T]:
        """后序遍历（迭代）- O(n)"""
        result = []
        stack = [(self.root, False)]
        
        while stack:
            node, visited = stack.pop()
            if node:
                if visited:
                    result.append(node.value)
                else:
                    stack.append((node, True))
                    stack.append((node.right, False))
                    stack.append((node.left, False))
        
        return result
    
    def level_order(self) -> List[List[T]]:
        """层序遍历 - O(n)"""
        if not self.root:
            return []
        
        result = []
        queue = deque([self.root])
        
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.value)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        
        return result
    
    def morris_inorder(self) -> List[T]:
        """
        Morris中序遍历 - O(n)时间，O(1)空间
        
        使用线索二叉树思想，临时修改树结构
        """
        result = []
        current = self.root
        
        while current:
            if not current.left:
                result.append(current.value)
                current = current.right
            else:
                predecessor = current.left
                while predecessor.right and predecessor.right != current:
                    predecessor = predecessor.right
                
                if not predecessor.right:
                    predecessor.right = current
                    current = current.left
                else:
                    predecessor.right = None
                    result.append(current.value)
                    current = current.right
        
        return result

11.3.3 遍历序列与树的唯一性

定理 11.10（前序+中序唯一确定二叉树） 给定二叉树的前序遍历和中序遍历序列，可以唯一确定该二叉树。

证明：设前序序列为 $P = [p_1, p_2, \ldots, p_n]$，中序序列为 $I = [i_1, i_2, \ldots, i_n]$。

$p_1$ 是根节点
在 $I$ 中找到 $p_1$ 的位置 $k$，则 $I[0..k-1]$ 是左子树的中序，$I[k+1..n-1]$ 是右子树的中序
左子树有 $k$ 个节点，因此 $P[1..k]$ 是左子树的前序，$P[k+1..n-1]$ 是右子树的前序
递归构造左右子树

每一步选择唯一，故树唯一。∎

定理 11.11（中序+后序唯一确定二叉树） 给定二叉树的中序遍历和后序遍历序列，可以唯一确定该二叉树。

证明：类似定理 11.10，后序序列的最后一个元素是根节点。∎

定理 11.12（前序+后序不能唯一确定一般二叉树） 对于一般二叉树，前序和后序遍历序列不能唯一确定树结构。

证明：反例。考虑两棵树：

树1:    A        树2:    A
        /                \
       B                  B

两棵树的前序都是 $[A, B]$，后序都是 $[B, A]$，但树结构不同。∎

python

def build_from_preorder_inorder(preorder: List[T], inorder: List[T]) -> Optional[TreeNode[T]]:
    """
    从前序和中序遍历构造二叉树
    
    时间复杂度：O(n²)（可优化到O(n)使用哈希表）
    空间复杂度：O(n)
    """
    if not preorder or not inorder:
        return None
    
    root_val = preorder[0]
    root = TreeNode(root_val)
    
    root_idx = inorder.index(root_val)
    
    root.left = build_from_preorder_inorder(
        preorder[1:root_idx + 1],
        inorder[:root_idx]
    )
    root.right = build_from_preorder_inorder(
        preorder[root_idx + 1:],
        inorder[root_idx + 1:]
    )
    
    return root


def build_from_preorder_inorder_optimized(preorder: List[T], inorder: List[T]) -> Optional[TreeNode[T]]:
    """
    优化版本 - O(n)时间
    
    使用哈希表加速查找
    """
    inorder_map = {val: i for i, val in enumerate(inorder)}
    pre_idx = 0
    
    def build(left: int, right: int) -> Optional[TreeNode[T]]:
        nonlocal pre_idx
        
        if left > right:
            return None
        
        val = preorder[pre_idx]
        pre_idx += 1
        node = TreeNode(val)
        
        idx = inorder_map[val]
        node.left = build(left, idx - 1)
        node.right = build(idx + 1, right)
        
        return node
    
    return build(0, len(inorder) - 1)

11.4 二叉树高级操作

11.4.1 最近公共祖先

定义 11.14（最近公共祖先） 节点 $p$ 和 $q$ 的最近公共祖先（LCA）是同时拥有 $p$ 和 $q$ 作为后代的深度最大的节点。

定理 11.13（LCA存在唯一性） 在二叉树中，任意两个节点的LCA存在且唯一。

证明：两个节点 $p, q$ 的祖先集合非空（至少包含根）。两个集合的交集非空（包含根）。交集的最深元素唯一（树中路径唯一）。∎

python

def lowest_common_ancestor(root: TreeNode[T], p: TreeNode[T], q: TreeNode[T]) -> Optional[TreeNode[T]]:
    """
    最近公共祖先 - O(n)
    
    时间复杂度：O(n)
    空间复杂度：O(h)
    """
    if not root or root == p or root == q:
        return root
    
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    
    if left and right:
        return root
    
    return left if left else right


def lca_with_parent(p: TreeNode[T], q: TreeNode[T]) -> Optional[TreeNode[T]]:
    """
    带父指针的LCA - O(h)
    
    类似链表找交点
    """
    def get_depth(node: TreeNode[T]) -> int:
        depth = 0
        while node.parent:
            depth += 1
            node = node.parent
        return depth
    
    depth_p = get_depth(p)
    depth_q = get_depth(q)
    
    if depth_p < depth_q:
        p, q = q, p
    
    diff = abs(depth_p - depth_q)
    for _ in range(diff):
        p = p.parent
    
    while p != q:
        p = p.parent
        q = q.parent
    
    return p

11.4.2 路径问题

python

def has_path_sum(root: Optional[TreeNode[T]], target: int) -> bool:
    """
    判断是否存在根到叶子的路径和等于目标值
    
    时间复杂度：O(n)
    空间复杂度：O(h)
    """
    if not root:
        return False
    
    if root.is_leaf():
        return root.value == target
    
    return (has_path_sum(root.left, target - root.value) or
            has_path_sum(root.right, target - root.value))


def path_sum_all(root: Optional[TreeNode[T]], target: int) -> List[List[T]]:
    """
    找出所有根到叶子的路径和等于目标值的路径
    
    时间复杂度：O(n)
    空间复杂度：O(h)
    """
    result = []
    
    def dfs(node: Optional[TreeNode[T]], path: List[T], remaining: int):
        if not node:
            return
        
        path.append(node.value)
        
        if node.is_leaf() and node.value == remaining:
            result.append(path[:])
        else:
            dfs(node.left, path, remaining - node.value)
            dfs(node.right, path, remaining - node.value)
        
        path.pop()
    
    dfs(root, [], target)
    return result


def max_path_sum(root: Optional[TreeNode[T]]) -> int:
    """
    二叉树最大路径和（任意节点到任意节点）
    
    时间复杂度：O(n)
    空间复杂度：O(h)
    """
    max_sum = float('-inf')
    
    def max_gain(node: Optional[TreeNode[T]]) -> int:
        nonlocal max_sum
        
        if not node:
            return 0
        
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)
        
        price_newpath = node.value + left_gain + right_gain
        max_sum = max(max_sum, price_newpath)
        
        return node.value + max(left_gain, right_gain)
    
    max_gain(root)
    return max_sum

11.4.3 树的变换

python

def invert_tree(root: Optional[TreeNode[T]]) -> Optional[TreeNode[T]]:
    """
    翻转二叉树
    
    时间复杂度：O(n)
    空间复杂度：O(h)
    """
    if not root:
        return None
    
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    
    return root


def flatten_to_linked_list(root: Optional[TreeNode[T]]) -> Optional[TreeNode[T]]:
    """
    将二叉树展开为链表（原地）
    
    时间复杂度：O(n)
    空间复杂度：O(1)（Morris风格）
    """
    current = root
    
    while current:
        if current.left:
            predecessor = current.left
            while predecessor.right:
                predecessor = predecessor.right
            
            predecessor.right = current.right
            current.right = current.left
            current.left = None
        
        current = current.right
    
    return root


def diameter(root: Optional[TreeNode[T]]) -> int:
    """
    二叉树直径（任意两节点间最长路径）
    
    时间复杂度：O(n)
    空间复杂度：O(h)
    """
    max_diameter = 0
    
    def depth(node: Optional[TreeNode[T]]) -> int:
        nonlocal max_diameter
        
        if not node:
            return 0
        
        left = depth(node.left)
        right = depth(node.right)
        
        max_diameter = max(max_diameter, left + right)
        
        return 1 + max(left, right)
    
    depth(root)
    return max_diameter

11.5 序列化与反序列化

11.5.1 序列化理论

定义 11.15（序列化） 序列化是将数据结构转换为可存储或传输格式的过程。

定义 11.16（反序列化） 反序列化是从序列化格式恢复数据结构的过程。

定理 11.14（序列化完整性） 序列化后的数据应能唯一恢复原始树结构。

python

def serialize(root: Optional[TreeNode[T]]) -> str:
    """
    序列化二叉树（前序）
    
    时间复杂度：O(n)
    空间复杂度：O(n)
    """
    if not root:
        return "null"
    
    return f"{root.value},{serialize(root.left)},{serialize(root.right)}"


def deserialize(data: str) -> Optional[TreeNode[T]]:
    """
    反序列化二叉树
    
    时间复杂度：O(n)
    空间复杂度：O(n)
    """
    values = iter(data.split(','))
    
    def build() -> Optional[TreeNode[T]]:
        val = next(values)
        if val == "null":
            return None
        node = TreeNode(int(val))
        node.left = build()
        node.right = build()
        return node
    
    return build()


def serialize_level_order(root: Optional[TreeNode[T]]) -> str:
    """
    层序序列化
    
    时间复杂度：O(n)
    """
    if not root:
        return "null"
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        
        if node:
            result.append(str(node.value))
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append("null")
    
    while result and result[-1] == "null":
        result.pop()
    
    return ",".join(result)

11.6 本章小结

11.6.1 核心定理总结

定理	内容	应用
定理 11.1	树的等价刻画	树的判定
定理 11.4	完美二叉树性质	节点数计算
定理 11.7	叶子数与内部节点数关系	树分析
定理 11.8	二叉树高度下界	空间优化
定理 11.10	前序+中序唯一确定树	树构造

11.6.2 遍历复杂度对比

遍历方式	时间	空间（递归）	空间（迭代）	空间（Morris）
前序	$O(n)$	$O(h)$	$O(h)$	$O(1)$
中序	$O(n)$	$O(h)$	$O(h)$	$O(1)$
后序	$O(n)$	$O(h)$	$O(h)$	$O(1)$
层序	$O(n)$	-	$O(w)$	-

11.6.3 选择指南

场景	推荐遍历	原因
复制树	前序	先处理根节点
表达式求值	后序	先处理子树
BST排序	中序	有序输出
最短路径	层序	BFS
空间受限	Morris	$O(1)$ 空间

11.7 习题

理论题

证明：树的六种等价定义。
证明：对于任意二叉树，$n_0 = n_2 + 1$。
证明：前序+后序不能唯一确定一般二叉树。
证明：Morris遍历的时间复杂度为 $O(n)$。

设计题

设计一个支持 $O(1)$ 时间获取父节点的二叉树节点结构。
实现一个支持持久化的二叉树（修改不破坏原树）。

实现题

实现二叉树的序列化与反序列化（支持任意类型）。
实现多叉树与二叉树的相互转换。

11.8 参考文献

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press. Chapter 10: Elementary Data Structures.
Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley. Section 2.3: Trees.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley. Section 3.2: Binary Search Trees.
Morris, J. M. (1979). Traversing binary trees simply and cheaply. Information Processing Letters, 9(5), 197-200.
Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1983). Data Structures and Algorithms. Addison-Wesley. Chapter 3: Trees.

下一章：第12章二叉搜索树理论

第11章 树基础与二叉树理论 ​

本章导读 ​

学习目标 ​

11.1 树的数学基础 ​

11.1.1 树的等价定义 ​

11.1.2 有根树与层次结构 ​

11.1.3 树ADT规范 ​

11.2 二叉树理论 ​

11.2.1 二叉树的数学定义 ​

11.2.2 特殊二叉树 ​

11.2.3 二叉树性质定理 ​

11.2.4 二叉树实现 ​

11.3 二叉树遍历理论 ​

11.3.1 遍历的定义 ​

11.3.2 遍历实现 ​

11.3.3 遍历序列与树的唯一性 ​

11.4 二叉树高级操作 ​

11.4.1 最近公共祖先 ​

11.4.2 路径问题 ​

11.4.3 树的变换 ​

11.5 序列化与反序列化 ​

11.5.1 序列化理论 ​

11.6 本章小结 ​

11.6.1 核心定理总结 ​

11.6.2 遍历复杂度对比 ​

11.6.3 选择指南 ​

11.7 习题 ​

理论题 ​

设计题 ​

实现题 ​

11.8 参考文献 ​

第11章树基础与二叉树理论

本章导读

学习目标

11.1 树的数学基础

11.1.1 树的等价定义

11.1.2 有根树与层次结构

11.1.3 树ADT规范

11.2 二叉树理论

11.2.1 二叉树的数学定义

11.2.2 特殊二叉树

11.2.3 二叉树性质定理

11.2.4 二叉树实现

11.3 二叉树遍历理论

11.3.1 遍历的定义

11.3.2 遍历实现

11.3.3 遍历序列与树的唯一性

11.4 二叉树高级操作

11.4.1 最近公共祖先

11.4.2 路径问题

11.4.3 树的变换

11.5 序列化与反序列化

11.5.1 序列化理论

11.6 本章小结

11.6.1 核心定理总结

11.6.2 遍历复杂度对比

11.6.3 选择指南

11.7 习题

理论题

设计题

实现题

11.8 参考文献