二叉树特性

程序设计语言常用的二叉树如下：

• 满二叉树：除叶子节点外，每个节点都有两个子节点
• 完全二叉树：除最后一层外，其他层全满，且最后一层的节点从左到右依次排列
• 二叉搜索树（BST）：左子树节点值≤当前节点值≤右子树节点值
• 平衡二叉树（如 AVL 树、红黑树）：左右子树高度差不超过 1

二叉树广泛应用于数据查找、排序、表达式解析等场景，其遍历方式（前序、中序、后序、层次遍历）是基础操作。

---

以下特性均基于 根节点为第1层、空树深度为0 的通用定义。

1. 第 i 层最多节点数

二叉树第 $i$ 层的节点数量存在上限，公式为：
$\text{第 }i\text{ 层最大节点数}=2^{i-1}(i\ge 1)$

• 示例：第1层（根节点）最多1个节点（$2^0=1$），第3层最多4个节点（$2^2=4$）。

普通二叉树（示例：根为 1，左子树有分支，右子树仅 1 个节点）

graph TD
    A[1（根节点）] --> B[2（左子节点）]
    A --> C[3（右子节点，叶子）]
    B --> D[4（左子节点，叶子）]
    B --> E[5（右子节点）]
    E --> F[6（左子节点，叶子）]
    style C fill:#f9f,stroke:#333,stroke-width:2px
    style D fill:#f9f,stroke:#333,stroke-width:2px
    style F fill:#f9f,stroke:#333,stroke-width:2px
    %% 粉色填充标注叶子节点

2. 深度为 k 的二叉树最多总节点数

深度为 $k$ 的二叉树（所有层均满节点时，即满二叉树），总节点数上限公式为：
$\text{深度为 }k\text{ 的最大总节点数}=2^k-1(k\ge 0)$

• 示例：深度为3的满二叉树，总节点数为 $2^3-1=7$。

满二叉树（深度为 3，所有非叶子节点均有 2 个子节点）

graph TD
    A[1（根）] --> B[2（左）]
    A --> C[3（右）]
    B --> D[4（左）]
    B --> E[5（右）]
    C --> F[6（左）]
    C --> G[7（右）]
    style D fill:#f9f,stroke:#333,stroke-width:2px
    style E fill:#f9f,stroke:#333,stroke-width:2px
    style F fill:#f9f,stroke:#333,stroke-width:2px
    style G fill:#f9f,stroke:#333,stroke-width:2px
    %% 所有叶子节点均在同一层

3. 非空二叉树的叶子节点与双子节点关系

设：

• $n_0$ = 叶子节点数（无子女的节点）
• $n_2$ = 双子女节点数（有左、右两个子节点的节点）

两者满足固定等式：
$n_0=n_2+1$

• 示例：若某二叉树有5个双子女节点（$n_2=5$），则叶子节点数必为6（$n_0=5+1=6$）。

非空二叉树（示例：根为 1，余下复制）

graph TD
    A[1（双子女节点）] --> B[2（双子女节点）]
    A --> C[3（双子女节点）]
    
    B --> D[4（双子女节点）]
    B --> E[5（叶子）]
    
    D --> F[6（叶子）]
    D --> G[7（叶子）]
    
    C --> H[8（双子女节点）]
    C --> I[9（叶子）]
    
    H --> J[10（叶子）]
    H --> K[11（叶子）]
    
    %% 标记叶子节点样式
    style E fill:#f9f,stroke:#333,stroke-width:2px
    style F fill:#f9f,stroke:#333,stroke-width:2px
    style G fill:#f9f,stroke:#333,stroke-width:2px
    style I fill:#f9f,stroke:#333,stroke-width:2px
    style J fill:#f9f,stroke:#333,stroke-width:2px
    style K fill:#f9f,stroke:#333,stroke-width:2px

4. 完全二叉树的节点编号特性

对含 $n$ 个节点的完全二叉树（节点按“层序遍历”从1开始编号），任意节点 $i$ 的亲属节点编号满足：

• 左子节点编号：$2i$（仅当 $2i\le n$ 时存在）
• 右子节点编号：$2i+1$（仅当 $2i+1\le n$ 时存在）
• 父节点编号：$\lfloor \frac{i}{2}\rfloor$（仅当 $i>1$ 时存在，$\lfloor x\rfloor$ 表示向下取整）
• 示例：节点3的左子节点为6（$2\times 3=6$），右子节点为7（$2\times 3+1=7$）；节点6的父节点为3（$\lfloor 6/2\rfloor =3$）。

完全二叉树（深度为 3，最后一层节点从左到右连续排列，无空缺）

graph TD
    A[1（根）] --> B[2（左）]
    A --> C[3（右）]
    B --> D[4（左）]
    B --> E[5（右）]
    C --> F[6（左，叶子）]
    %% 最后一层仅缺失最右侧的7号节点，且节点从左到右连续
    style D fill:#f9f,stroke:#333,stroke-width:2px
    style E fill:#f9f,stroke:#333,stroke-width:2px
    style F fill:#f9f,stroke:#333,stroke-width:2px

附加：二叉搜索树（BST，满足 “左子树值≤父节点值≤右子树值”）

graph TD
    A[5（根）] --> B[3（左，≤5）]
    A --> C[7（右，≥5）]
    B --> D[2（左，≤3）]
    B --> E[4（右，≥3）]
    C --> F[6（左，≤7）]
    C --> G[8（右，≥7）]
    style D fill:#f9f,stroke:#333,stroke-width:2px
    style E fill:#f9f,stroke:#333,stroke-width:2px
    style F fill:#f9f,stroke:#333,stroke-width:2px
    style G fill:#f9f,stroke:#333,stroke-width:2px
    %% 每个节点的左子树值均小于自身，右子树值均大于自身

Python 实现常见操作

class TreeNode:
    """二叉树节点类"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val    # 节点值
        self.left = left  # 左子节点
        self.right = right # 右子节点

    def preorder_traversal(root):
        """前序遍历：根 -> 左 -> 右"""
        result = []
        def traverse(node):
            if node:
                result.append(node.val)  # 先访问根节点
                traverse(node.left)      # 再访问左子树
                traverse(node.right)     # 最后访问右子树
        traverse(root)
        return result

    def inorder_traversal(root):
        """中序遍历：左 -> 根 -> 右"""
        result = []
        def traverse(node):
            if node:
                traverse(node.left)      # 先访问左子树
                result.append(node.val)  # 再访问根节点
                traverse(node.right)     # 最后访问右子树
        traverse(root)
        return result

    def postorder_traversal(root):
        """后序遍历：左 -> 右 -> 根"""
        result = []
        def traverse(node):
            if node:
                traverse(node.left)      # 先访问左子树
                traverse(node.right)     # 再访问右子树
                result.append(node.val)  # 最后访问根节点
        traverse(root)
        return result

    def levelorder_traversal(root):
        """层次遍历：按层从左到右访问"""
        if not root:
            return []
        result = []
        queue = [root]  # 使用队列存储当前层节点
        while queue:
            level_size = len(queue)
            current_level = []
            for _ in range(level_size):
                node = queue.pop(0)  # 取出队首节点
                current_level.append(node.val)
                if node.left:
                    queue.append(node.left)  # 左子节点入队
                if node.right:
                    queue.append(node.right) # 右子节点入队
            result.append(current_level)
        return result

if __name__ == '__main__':
    # 构建示例二叉树
    #       1
    #      / \
    #     2   3
    #    / \   \
    #   4   5   6
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(6)

    # 测试遍历结果
    print("前序遍历:", preorder_traversal(root))   # [1, 2, 4, 5, 3, 6]
    print("中序遍历:", inorder_traversal(root))    # [4, 2, 5, 1, 3, 6]
    print("后序遍历:", postorder_traversal(root))  # [4, 5, 2, 6, 3, 1]
    print("层次遍历:", levelorder_traversal(root)) # [[1], [2, 3], [4, 5, 6]]