# 9. 二叉树

## 概念

**二叉树（Binary Tree）** 是每个结点**最多有两个子树**（左子树、右子树）的树结构，左右子树**有明确次序**，不能随意颠倒。二叉树不是树的特殊情况，而是另一种树形结构。

**二叉树的定义：** 二叉树是 n（n ≥ 0）个结点的有限集合，要么是空集（空二叉树），要么由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。该定义是**递归**的。

**二叉树的性质：**

1. 第 i 层最多有 **2^(i-1)** 个结点（i ≥ 1）。
2. 深度为 k 的二叉树最多有 **2^k − 1** 个结点（k ≥ 1）。
3. 对任意二叉树，**叶结点数 n0 = 度为 2 的结点数 n2 + 1**，即 `n0 = n2 + 1`。（证明：总分支数 = n0 + 2·n2 = 结点总数 − 1 = (n0+n1+n2) − 1，整理得 n0 = n2 + 1。）
4. 具有 n 个结点的完全二叉树深度为 **⌊log₂ n⌋ + 1**。

**特殊形态：**

- **满二叉树**：深度为 k 且有 2^k − 1 个结点，每一层都充满。
- **完全二叉树**：除最后一层外每一层都满，最后一层结点从左到右连续排列（可以不满）。满二叉树是完全二叉树的特例。完全二叉树适合用数组顺序存储。

**存储结构：**

1. **顺序存储**：用数组存放结点，下标反映结点在完全二叉树中的位置。若某结点下标为 i，则左孩子为 2i，右孩子为 2i+1，父结点为 ⌊i/2⌋。**适合完全二叉树**；对一般二叉树会浪费大量空间（需补空结点）。
2. **链式存储**：每个结点包含 `data`、`left`、`right` 三个字段。**适合任意二叉树**，是实际中最常用的方式。

**适用场景**：表达式树、二叉排序树、堆、哈夫曼树、搜索与排序（如平衡二叉树）、文件系统目录等。

## 核心操作

| 操作                  | 说明                                    |
| --------------------- | --------------------------------------- |
| `Create` 创建         | 按先序序列（含空结点标记）创建二叉树    |
| `PreOrder` 前序遍历   | 根 → 左 → 右                            |
| `InOrder` 中序遍历    | 左 → 根 → 右                            |
| `PostOrder` 后序遍历  | 左 → 右 → 根                            |
| `LevelOrder` 层序遍历 | 从上到下、从左到右（用队列）            |
| 求结点数 / 叶子数     | 统计结点或叶子数量                      |
| 求高度 / 深度         | 计算树的高度（根到最远叶子的边数/层数） |

> **非递归遍历思想**：用**栈**模拟递归过程。前/中序遍历用一个栈保存待访问的结点；后序遍历需额外标记或双栈；层序遍历用**队列**实现。所有递归算法都可转化为用栈实现的非递归版本，本质相同。

## 复杂度分析

| 操作                 | 时间复杂度 | 空间复杂度 | 说明                       |
| -------------------- | ---------- | ---------- | -------------------------- |
| 创建                 | O(n)       | O(h)       | 递归建树，访问每个结点一次 |
| 前/中/后序遍历       | O(n)       | O(h)       | 每个结点访问一次           |
| 层序遍历             | O(n)       | O(w)       | w 为最大宽度，最坏 O(n)    |
| 求高度/结点数/叶子数 | O(n)       | O(h)       | 递归遍历整棵树             |

其中 **h 为树的高度**（递归栈深度）。

**为什么：** 前/中/后序遍历每个结点恰好访问一次，共 n 个结点，故时间 O(n)。递归实现时系统递归栈的最大深度等于树的高度 h，故空间 O(h)；最坏情况（斜树）下 h = n，空间退化为 O(n)。层序遍历用队列，队中最多同时容纳一层结点，宽度最坏为 O(n)。

## 语言实现

以下四种语言均用**链式存储**实现二叉树，包含：递归创建、前序/中序/后序递归遍历、层序遍历（队列）、求高度/结点数/叶子数，并演示同一棵二叉树的结果。

演示的二叉树（先序含空标记创建）：

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

先序含空序列：`A B D # # E # # C # F # #`（# 表示空结点）

### C

```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef char ElemType;

// 二叉树结点（链式存储）
typedef struct BTNode {
    ElemType data;
    struct BTNode *left;
    struct BTNode *right;
} BTNode;

// 按先序序列创建二叉树，读到 # 表示空结点
BTNode *CreateTree(char **p) {
    char ch = **p;
    (*p)++;                 // 指针后移
    if (ch == '#') return NULL;
    BTNode *node = (BTNode *)malloc(sizeof(BTNode));
    node->data = ch;
    node->left = CreateTree(p);
    node->right = CreateTree(p);
    return node;
}

// 前序遍历：根左右
void PreOrder(BTNode *root) {
    if (root == NULL) return;
    printf("%c ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

// 中序遍历：左根右
void InOrder(BTNode *root) {
    if (root == NULL) return;
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}

// 后序遍历：左右根
void PostOrder(BTNode *root) {
    if (root == NULL) return;
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%c ", root->data);
}

// 层序遍历：用队列
void LevelOrder(BTNode *root) {
    if (root == NULL) return;
    BTNode *queue[100];     // 简单队列
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        BTNode *node = queue[front++];
        printf("%c ", node->data);
        if (node->left) queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;
    }
}

// 求高度
int Height(BTNode *root) {
    if (root == NULL) return 0;
    int l = Height(root->left);
    int r = Height(root->right);
    return (l > r ? l : r) + 1;
}

// 求结点数
int CountNodes(BTNode *root) {
    if (root == NULL) return 0;
    return CountNodes(root->left) + CountNodes(root->right) + 1;
}

// 求叶子数
int CountLeaves(BTNode *root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;
    return CountLeaves(root->left) + CountLeaves(root->right);
}

int main() {
    char seq[] = "ABD##E##C#F##";
    char *p = seq;
    BTNode *root = CreateTree(&p);

    printf("前序: "); PreOrder(root); printf("\n");   // A B D E C F
    printf("中序: "); InOrder(root); printf("\n");    // D B E A C F
    printf("后序: "); PostOrder(root); printf("\n");  // D E B F C A
    printf("层序: "); LevelOrder(root); printf("\n"); // A B C D E F
    printf("高度: %d\n", Height(root));               // 3
    printf("结点数: %d\n", CountNodes(root));         // 6
    printf("叶子数: %d\n", CountLeaves(root));        // 3
    return 0;
}
```

### C++

```C++
#include <iostream>
#include <queue>
using namespace std;

typedef char ElemType;

// 二叉树结点
struct BTNode {
    ElemType data;
    BTNode *left;
    BTNode *right;
    BTNode(ElemType d) : data(d), left(nullptr), right(nullptr) {}
};

// 按先序序列创建二叉树，# 表示空结点
BTNode *CreateTree(const char *&p) {
    if (*p == '\0') return nullptr;
    char ch = *p++;
    if (ch == '#') return nullptr;
    BTNode *node = new BTNode(ch);
    node->left = CreateTree(p);
    node->right = CreateTree(p);
    return node;
}

// 前序
void PreOrder(BTNode *root) {
    if (!root) return;
    cout << root->data << " ";
    PreOrder(root->left);
    PreOrder(root->right);
}

// 中序
void InOrder(BTNode *root) {
    if (!root) return;
    InOrder(root->left);
    cout << root->data << " ";
    InOrder(root->right);
}

// 后序
void PostOrder(BTNode *root) {
    if (!root) return;
    PostOrder(root->left);
    PostOrder(root->right);
    cout << root->data << " ";
}

// 层序：用 queue
void LevelOrder(BTNode *root) {
    if (!root) return;
    queue<BTNode *> q;
    q.push(root);
    while (!q.empty()) {
        BTNode *node = q.front();
        q.pop();
        cout << node->data << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

int Height(BTNode *root) {
    if (!root) return 0;
    return max(Height(root->left), Height(root->right)) + 1;
}

int CountNodes(BTNode *root) {
    if (!root) return 0;
    return CountNodes(root->left) + CountNodes(root->right) + 1;
}

int CountLeaves(BTNode *root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    return CountLeaves(root->left) + CountLeaves(root->right);
}

int main() {
    const char *seq = "ABD##E##C#F##";
    BTNode *root = CreateTree(seq);

    cout << "前序: "; PreOrder(root); cout << endl;   // A B D E C F
    cout << "中序: "; InOrder(root); cout << endl;    // D B E A C F
    cout << "后序: "; PostOrder(root); cout << endl;  // D E B F C A
    cout << "层序: "; LevelOrder(root); cout << endl; // A B C D E F
    cout << "高度: " << Height(root) << endl;          // 3
    cout << "结点数: " << CountNodes(root) << endl;    // 6
    cout << "叶子数: " << CountLeaves(root) << endl;   // 3
    return 0;
}
```

### Java

```java
import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    // 结点类
    static class BTNode {
        char data;
        BTNode left;
        BTNode right;
        BTNode(char d) { data = d; }
    }

    private static int idx = 0;   // 全局索引，用于创建

    // 按先序序列创建，# 表示空结点
    public static BTNode createTree(String seq) {
        if (idx >= seq.length()) return null;
        char ch = seq.charAt(idx++);
        if (ch == '#') return null;
        BTNode node = new BTNode(ch);
        node.left = createTree(seq);
        node.right = createTree(seq);
        return node;
    }

    public static void preOrder(BTNode root) {
        if (root == null) return;
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void inOrder(BTNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.data + " ");
        inOrder(root.right);
    }

    public static void postOrder(BTNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.data + " ");
    }

    // 层序：用队列
    public static void levelOrder(BTNode root) {
        if (root == null) return;
        Queue<BTNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            BTNode node = q.poll();
            System.out.print(node.data + " ");
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }

    public static int height(BTNode root) {
        if (root == null) return 0;
        return Math.max(height(root.left), height(root.right)) + 1;
    }

    public static int countNodes(BTNode root) {
        if (root == null) return 0;
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

    public static int countLeaves(BTNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return countLeaves(root.left) + countLeaves(root.right);
    }

    public static void main(String[] args) {
        idx = 0;   // 重置索引
        BTNode root = createTree("ABD##E##C#F##");

        System.out.print("前序: "); preOrder(root); System.out.println();   // A B D E C F
        System.out.print("中序: "); inOrder(root); System.out.println();    // D B E A C F
        System.out.print("后序: "); postOrder(root); System.out.println();  // D E B F C A
        System.out.print("层序: "); levelOrder(root); System.out.println(); // A B C D E F
        System.out.println("高度: " + height(root));                        // 3
        System.out.println("结点数: " + countNodes(root));                  // 6
        System.out.println("叶子数: " + countLeaves(root));                 // 3
    }
}
```

### Python

```python
from collections import deque


class BTNode:
    """二叉树结点（链式存储）"""

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def create_tree(seq_iter):
    """按先序序列创建二叉树，# 表示空结点（seq_iter 为迭代器）"""
    try:
        ch = next(seq_iter)
    except StopIteration:
        return None
    if ch == '#':
        return None
    node = BTNode(ch)
    node.left = create_tree(seq_iter)
    node.right = create_tree(seq_iter)
    return node


def pre_order(root):
    """前序：根左右"""
    if root is None:
        return []
    return [root.data] + pre_order(root.left) + pre_order(root.right)


def in_order(root):
    """中序：左根右"""
    if root is None:
        return []
    return in_order(root.left) + [root.data] + in_order(root.right)


def post_order(root):
    """后序：左右根"""
    if root is None:
        return []
    return post_order(root.left) + post_order(root.right) + [root.data]


def level_order(root):
    """层序：用队列"""
    if root is None:
        return []
    result = []
    q = deque([root])
    while q:
        node = q.popleft()
        result.append(node.data)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return result


def height(root):
    """求高度"""
    if root is None:
        return 0
    return max(height(root.left), height(root.right)) + 1


def count_nodes(root):
    """求结点数"""
    if root is None:
        return 0
    return count_nodes(root.left) + count_nodes(root.right) + 1


def count_leaves(root):
    """求叶子数"""
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return 1
    return count_leaves(root.left) + count_leaves(root.right)


if __name__ == "__main__":
    seq = "ABD##E##C#F##"
    root = create_tree(iter(seq))

    print("前序:", pre_order(root))       # ['A', 'B', 'D', 'E', 'C', 'F']
    print("中序:", in_order(root))        # ['D', 'B', 'E', 'A', 'C', 'F']
    print("后序:", post_order(root))      # ['D', 'E', 'B', 'F', 'C', 'A']
    print("层序:", level_order(root))     # ['A', 'B', 'C', 'D', 'E', 'F']
    print("高度:", height(root))          # 3
    print("结点数:", count_nodes(root))   # 6
    print("叶子数:", count_leaves(root))  # 3
```