跳转至

二叉树

概述

二叉树（Binary Tree）是一种重要的树形数据结构，每个节点最多有两个子节点，分别称为左子节点（Left Child）和右子节点（Right Child）。二叉树是许多高级数据结构（如BST、AVL树、红黑树、堆等）的基础。

二叉树的递归定义

二叉树要么为空集，要么由一个根节点和两个互不相交的、分别称为左子树和右子树的二叉树组成。这个递归定义是理解二叉树所有操作的关键。

二叉树的可视化结构

graph TB
    A((1)) --> B((2))
    A --> C((3))
    B --> D((4))
    B --> E((5))
    C --> F((6))
    C --> G((7))
    
    style A fill:#E3F2FD
    style B fill:#E8F5E9
    style C fill:#E8F5E9
    style D fill:#FFF3E0
    style E fill:#FFF3E0
    style F fill:#FFF3E0
    style G fill:#FFF3E0

树的层次结构

层次 节点 说明
第1层 1 ← 根节点 (Root)
第2层 2, 3 ← 第1层的子节点
第3层 4, 5, 6, 7 ← 叶子节点 (Leaf)

树的高度: 3 | 节点总数: 7

二叉树特点详解

1. 递归定义

二叉树的每个节点都可以看作是一棵子树的根，这使得递归成为处理二叉树最自然的方式。

2. 度数限制

每个节点的度数（子节点数量）最多为2，可以是0、1或2。

度数限制

graph TB
    subgraph "节点A（度=2）"
        A1[A] --> B1[○]
        A1 --> C1[○]
    end
    
    subgraph "节点B（度=1）"
        D[B] --> E[○]
    end
    
    subgraph "节点C（度=0，叶子）"
        F[C]
    end

3. 有序性

左右子树有严格的顺序区分，即使某个节点只有一个子节点，也必须区分是左子节点还是右子节点。

4. 层次结构

节点按层次组织，根节点在第1层，其子节点在第2层，以此类推。

基本概念详解

概念 定义 示例
节点（Node） 包含数据元素和指向子树的指针 上图中1-7都是节点
节点度数（Degree） 节点拥有的子树数量 节点1的度数为2
叶子节点（Leaf） 度数为0的节点 节点4,5,6,7
分支节点（Branch） 度数大于0的节点 节点1,2,3
父节点（Parent） 若有子节点，则为父节点 节点1是2,3的父节点
子节点（Child） 父节点的下层节点 节点2,3是1的子节点
兄弟节点（Sibling） 同一父节点的节点 节点2,3互为兄弟
节点层次（Level） 根为第1层，子节点层次=父节点层次+1 节点4在第3层
树的深度/高度（Depth/Height） 最大层次数 上图高度为3
路径（Path） 从一个节点到另一个节点的边序列 1→2→4
路径长度 路径上的边数 1到4的路径长度为2

二叉树重要性质

性质1：第i层节点数

第i层最多有 \(2^{i-1}\) 个节点。

验证

层级 公式 节点数
第1层 \(2^{1-1} = 1\) 1 ✓
第2层 \(2^{2-1} = 2\) 2 ✓
第3层 \(2^{3-1} = 4\) 4 ✓
第4层 \(2^{4-1} = 8\) 8 ✓

性质2：深度为k的节点总数

深度为 k 的二叉树最多有 \(2^k - 1\) 个节点。

验证

深度 k 公式 节点数
k=1 \(2^1 - 1 = 1\) 1
k=2 \(2^2 - 1 = 3\) 3
k=3 \(2^3 - 1 = 7\) 7

性质3：叶子节点与度数为2节点的关系

对任何非空二叉树，若 \(n_0\) 为叶子节点数，\(n_2\) 为度数为2的节点数，则：

\[n_0 = n_2 + 1\]

验证示例

graph TB
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))
    B --> E
end

style D fill:#E8F5E9
style E fill:#E8F5E9
style C fill:#E8F5E9
  • 叶子节点 \(n_0 = 3\) (D, E, C)
  • 度数为2节点 \(n_2 = 2\) (A, B)

\(n_0 = n_2 + 1 \Rightarrow 3 = 2 + 1\) ✓

性质4：完全二叉树的深度

n 个节点的完全二叉树深度为 \(\lfloor \log_2 n \rfloor + 1\)

验证

节点数 n 公式 深度
n=1 \(\lfloor \log_2 1 \rfloor + 1 = 0 + 1\) 1 ✓
n=3 \(\lfloor \log_2 3 \rfloor + 1 = 1 + 1\) 2 ✓
n=7 \(\lfloor \log_2 7 \rfloor + 1 = 2 + 1\) 3 ✓

性质5：完全二叉树的节点编号

对完全二叉树按层序编号，对任一编号为 i 的节点：

  • 父节点编号：\(\lfloor i/2 \rfloor\)
  • 左子节点编号：\(2i\)
  • 右子节点编号：\(2i + 1\)

编号关系验证

graph TB
    1((1)) --> 2((2))
    1 --> 3((3))
    2 --> 4((4))
    2 --> 5((5))
    3 --> 6((6))
    3 --> 7((7))
  • 父节点(1)的子节点: 左 \(= 2 \times 1 = 2\), 右 \(= 2 \times 1 + 1 = 3\)
  • 节点(2)的父节点: \(\lfloor 2/2 \rfloor = 1\)
  • 节点(5)的父节点: \(\lfloor 5/2 \rfloor = 2\)

特殊二叉树详解

1. 满二叉树（Full Binary Tree）

所有叶子节点在同一层，且所有分支节点都有两个子节点。

满二叉树（深度为3）

graph TB
    1((1)) --> 2((2))
    1 --> 3((3))
    2 --> 4((4))
    2 --> 5((5))
    3 --> 6((6))
    3 --> 7((7))

特点: - ✓ 所有叶子在同一层 - ✓ 每个分支节点都有2个子节点 - • 叶子节点数 = 2^(k-1)，k为深度 - • 总节点数 = 2^k - 1

2. 完全二叉树（Complete Binary Tree）

除最后一层外，每层节点数达到最大，且最后一层节点从左到右连续排列。

完全二叉树

graph TB
    1((1)) --> 2((2))
    1 --> 3((3))
    2 --> 4((4))
    2 --> 5((5))
    3 --> 6((6))

叶子节点4,5,6在最后一层连续排列

非完全二叉树

graph TB
    1((1)) --> 2((2))
    1 --> 3((3))
    2 --> 4((4))
    2 --> 5((5))
    5 --> 7((7))
  • ✗ 节点5的位置"空缺"，不连续
  • ✗ 应该先有左子节点

完全二叉树的重要性

完全二叉树是堆的基础，其编号性质使得可以用数组高效存储，无需指针。

3. 二叉搜索树（Binary Search Tree, BST）

左子树所有节点值小于根节点，右子树所有节点值大于根节点。

graph TB
    A((5)) --> B((3))
    A --> C((7))
    B --> D((2))
    B --> E((4))
    C --> F((6))
    C --> G((8))
    
    style A fill:#E3F2FD

BST特性

  • 左子树所有值 < 根节点值
  • 右子树所有值 > 根节点值
  • 中序遍历得到有序序列: 2 3 4 5 6 7 8
  • 查找、插入、删除平均 \(O(\log n)\)

4. 平衡二叉树（Balanced Binary Tree）

左右子树高度差不超过1。

平衡 vs 不平衡

graph TB
    subgraph "平衡二叉树"
        B1((4)) --> B2((2))
        B1 --> B3((6))
        B2 --> B4((1))
        B2 --> B5((3))
        B3 --> B6((5))
        B3 --> B7((7))
    end
    
    subgraph "不平衡二叉树"
        U1((1)) --> U2((2))
        U2 --> U3((3))
    end
  • 平衡树: |左高-右高| = 0 ≤ 1 ✓
  • 不平衡树: |左高-右高| = 2 > 1 ✗

5. 斜树（Skewed Tree）

所有节点都只有左子节点或只有右子节点，退化为链表。

斜树

graph TB
    subgraph "左斜树"
        L1((4)) --> L2((3))
        L2 --> L3((2))
        L3 --> L4((1))
    end
    
    subgraph "右斜树"
        R1((1)) --> R2((2))
        R2 --> R3((3))
        R3 --> R4((4))
    end

查找效率退化为 \(O(n)\)

二叉树的存储方式

1. 链式存储

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
typedef struct TreeNode {
    int data;                   // 数据域
    struct TreeNode *left;      // 左子节点指针
    struct TreeNode *right;     // 右子节点指针
} TreeNode;

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

链式存储结构

graph LR
    N1[("Node 1: data=1, left→, right→]
    N2[("Node 2: data=2, left→, right→]
    N3[("Node 4: data=4, left=NULL, right=NULL")]
    
    N1 --> N2
    N2 --> N3

每个节点包含数据域和两个指针域

2. 顺序存储（数组）

适用于完全二叉树：

完全二叉树的数组存储

graph TB
    1((1, idx=0)) --> 2((2, idx=1))
    1 --> 3((3, idx=2))
    2 --> 4((4, idx=3))
    2 --> 5((5, idx=4))
    3 --> 6((6, idx=5))

数组: [1, 2, 3, 4, 5, 6] 索引: 0 1 2 3 4 5

索引关系: - 父节点: ⌊(i-1)/2⌋ - 左子节点: 2i+1 - 右子节点: 2i+2

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 完全二叉树的数组表示
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int size;
} ArrayBinaryTree;

// 获取左子节点索引
int leftChild(int i) {
    return 2 * i + 1;
}

// 获取右子节点索引
int rightChild(int i) {
    return 2 * i + 2;
}

// 获取父节点索引
int parent(int i) {
    return (i - 1) / 2;
}

二叉树遍历详解

遍历是二叉树最基本也是最重要的操作，指按某种顺序访问所有节点且每个节点仅访问一次。

四种遍历方式对比

graph TB
    subgraph "遍历顺序示意"
        A((A)) --> B((B))
        A --> C((C))
    end
    
    style A fill:#E3F2FD
    style B fill:#E8F5E9
    style C fill:#FFF3E0
遍历方式 访问顺序 上图结果 应用场景
前序遍历 根→左→右 A B C 复制树、前缀表达式
中序遍历 左→根→右 B A C BST有序输出、中缀表达式
后序遍历 左→右→根 B C A 计算树高度、后缀表达式、释放树
层序遍历 按层次 A B C 按层处理、序列化

1. 前序遍历（Preorder）

graph TB
    subgraph "前序遍历: 根→左→右"
        A((1)) --> B((2))
        A --> C((3))
        B --> D((4))
        B --> E((5))
    end
    
    style A fill:#E3F2FD
    style B fill:#E8F5E9
    style D fill:#FFF3E0
    style E fill:#FFF3E0
    style C fill:#F3E5F5

前序遍历

遍历顺序: 1 → 2 → 4 → 5 → 3

执行过程: 1. 访问根节点1 2. 递归遍历左子树(以2为根) → 访问2, 4, 5 3. 递归遍历右子树(以3为根) → 访问3

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 递归实现
void preorder(TreeNode *root) {
    if (root == NULL) return;
    
    printf("%d ", root->data);   // 1. 访问根
    preorder(root->left);         // 2. 遍历左子树
    preorder(root->right);        // 3. 遍历右子树
}

// 非递归实现（使用栈）
void preorderIterative(TreeNode *root) {
    if (root == NULL) return;
    
    TreeNode *stack[100];
    int top = -1;
    stack[++top] = root;
    
    while (top >= 0) {
        TreeNode *node = stack[top--];
        printf("%d ", node->data);
        
        // 先压右子节点，后压左子节点（栈是LIFO）
        if (node->right) stack[++top] = node->right;
        if (node->left) stack[++top] = node->left;
    }
}

2. 中序遍历（Inorder）

graph TB
    subgraph "中序遍历: 左→根→右"
        A((1)) --> B((2))
        A --> C((3))
        B --> D((4))
        B --> E((5))
    end
    
    style D fill:#E3F2FD
    style B fill:#E8F5E9
    style E fill:#FFF3E0
    style A fill:#F3E5F5
    style C fill:#FCE4EC

中序遍历

遍历顺序: 4 → 2 → 5 → 1 → 3

对于BST，中序遍历得到有序序列！

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 递归实现
void inorder(TreeNode *root) {
    if (root == NULL) return;
    
    inorder(root->left);          // 1. 遍历左子树
    printf("%d ", root->data);    // 2. 访问根
    inorder(root->right);         // 3. 遍历右子树
}

// 非递归实现（使用栈）
void inorderIterative(TreeNode *root) {
    TreeNode *stack[100];
    int top = -1;
    TreeNode *curr = root;
    
    while (curr != NULL || top >= 0) {
        // 一直向左走，将路径上的节点入栈
        while (curr != NULL) {
            stack[++top] = curr;
            curr = curr->left;
        }
        
        // 弹出栈顶并访问
        curr = stack[top--];
        printf("%d ", curr->data);
        
        // 转向右子树
        curr = curr->right;
    }
}

3. 后序遍历（Postorder）

graph TB
    subgraph "后序遍历: 左→右→根"
        A((1)) --> B((2))
        A --> C((3))
        B --> D((4))
        B --> E((5))
    end
    
    style D fill:#E3F2FD
    style E fill:#E8F5E9
    style B fill:#FFF3E0
    style C fill:#F3E5F5
    style A fill:#FCE4EC

后序遍历

遍历顺序: 4 → 5 → 2 → 3 → 1

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 递归实现
void postorder(TreeNode *root) {
    if (root == NULL) return;
    
    postorder(root->left);        // 1. 遍历左子树
    postorder(root->right);       // 2. 遍历右子树
    printf("%d ", root->data);    // 3. 访问根
}

// 非递归实现（双栈法）
void postorderIterative(TreeNode *root) {
    if (root == NULL) return;
    
    TreeNode *stack1[100], *stack2[100];
    int top1 = -1, top2 = -1;
    stack1[++top1] = root;
    
    while (top1 >= 0) {
        TreeNode *node = stack1[top1--];
        stack2[++top2] = node;
        
        if (node->left) stack1[++top1] = node->left;
        if (node->right) stack1[++top1] = node->right;
    }
    
    while (top2 >= 0) {
        printf("%d ", stack2[top2--]->data);
    }
}

4. 层序遍历（Level Order）

graph TB
    subgraph "层序遍历: 按层次从上到下，从左到右"
        A((1)) --> B((2))
        A --> C((3))
        B --> D((4))
        B --> E((5))
    end
    
    style A fill:#E3F2FD
    style B fill:#E8F5E9
    style C fill:#E8F5E9
    style D fill:#FFF3E0
    style E fill:#FFF3E0

层序遍历

遍历顺序: 1 → 2 → 3 → 4 → 5

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 使用队列实现
void levelOrder(TreeNode *root) {
    if (root == NULL) return;
    
    TreeNode *queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    while (front < rear) {
        TreeNode *node = queue[front++];
        printf("%d ", node->data);
        
        if (node->left) queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;
    }
}

// 带层级信息的层序遍历
void levelOrderWithLevel(TreeNode *root) {
    if (root == NULL) return;
    
    TreeNode *queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    int level = 0;
    while (front < rear) {
        int levelSize = rear - front;  // 当前层节点数
        printf("第%d层: ", ++level);
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode *node = queue[front++];
            printf("%d ", node->data);
            
            if (node->left) queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
        printf("\n");
    }
}

常用操作实现

计算节点数

C
1
2
3
4
int countNodes(TreeNode *root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

计算树高度

C
1
2
3
4
5
6
int height(TreeNode *root) {
    if (root == NULL) return 0;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

查找节点

C
1
2
3
4
5
6
7
8
9
TreeNode* findNode(TreeNode *root, int target) {
    if (root == NULL) return NULL;
    if (root->data == target) return root;
    
    TreeNode *left = findNode(root->left, target);
    if (left != NULL) return left;
    
    return findNode(root->right, target);
}

销毁树

C
1
2
3
4
5
6
void destroyTree(TreeNode *root) {
    if (root == NULL) return;
    destroyTree(root->left);   // 先释放左子树
    destroyTree(root->right);  // 再释放右子树
    free(root);                // 最后释放根节点
}

二叉树构建

从前序和中序序列构建

从前序和中序序列构建

原理: - 前序序列第一个元素是根节点 - 在中序序列中找到根节点，左边是左子树，右边是右子树 - 递归构建左右子树

示例: - 前序: [1, 2, 4, 5, 3] - 中序: [4, 2, 5, 1, 3]

  1. 前序第一个元素1是根
  2. 在中序中找1: [4,2,5] 1 [3]
  3. 根据长度分割前序: [1] [2,4,5] [3]
  4. 递归构建...
C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
TreeNode* buildTree(int preorder[], int inorder[], 
                   int preStart, int preEnd, 
                   int inStart, int inEnd) {
    if (preStart > preEnd) return NULL;
    
    // 前序序列第一个元素是根节点
    TreeNode *root = createNode(preorder[preStart]);
    
    // 在中序序列中找到根节点位置
    int rootIndex;
    for (rootIndex = inStart; rootIndex <= inEnd; rootIndex++) {
        if (inorder[rootIndex] == preorder[preStart]) break;
    }
    
    int leftSize = rootIndex - inStart;
    
    // 递归构建左右子树
    root->left = buildTree(preorder, inorder, 
                          preStart + 1, preStart + leftSize, 
                          inStart, rootIndex - 1);
    root->right = buildTree(preorder, inorder, 
                           preStart + leftSize + 1, preEnd, 
                           rootIndex + 1, inEnd);
    
    return root;
}

从数组构建完全二叉树

C
1
2
3
4
5
6
7
8
9
TreeNode* buildCompleteTree(int arr[], int n, int index) {
    if (index >= n) return NULL;
    
    TreeNode *root = createNode(arr[index]);
    root->left = buildCompleteTree(arr, n, 2 * index + 1);
    root->right = buildCompleteTree(arr, n, 2 * index + 2);
    
    return root;
}

C++ 实现

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
template<typename T>
class BinaryTree {
private:
    struct TreeNode {
        T data;
        TreeNode *left, *right;
        
        TreeNode(T val) : data(val), left(nullptr), right(nullptr) {}
    };
    
    TreeNode *root;
    
public:
    BinaryTree() : root(nullptr) {}
    
    // 前序遍历
    void preorder() {
        preorderHelper(root);
    }
    
    void preorderHelper(TreeNode *node) {
        if (!node) return;
        std::cout << node->data << " ";
        preorderHelper(node->left);
        preorderHelper(node->right);
    }
    
    // 中序遍历
    void inorder() {
        inorderHelper(root);
    }
    
    void inorderHelper(TreeNode *node) {
        if (!node) return;
        inorderHelper(node->left);
        std::cout << node->data << " ";
        inorderHelper(node->right);
    }
    
    // 层序遍历
    void levelOrder() {
        if (!root) return;
        
        std::queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop();
            std::cout << node->data << " ";
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
};

时间复杂度分析

操作 平均时间 最坏时间 说明
遍历 \(O(n)\) \(O(n)\) 访问所有节点
查找节点 \(O(n)\) \(O(n)\) 可能需要遍历整棵树
插入节点 \(O(n)\) \(O(n)\) 需要找到插入位置
删除节点 \(O(n)\) \(O(n)\) 需要找到删除节点
计算高度 \(O(n)\) \(O(n)\) 需要遍历所有节点

空间复杂度

情况 空间复杂度 说明
递归遍历 \(O(h)\) h为树高度，递归栈深度
层序遍历 \(O(w)\) w为树最大宽度
平衡树 \(O(\log n)\) 高度最小
斜树（最坏） \(O(n)\) 退化为链表

应用场景

  1. 表达式树：计算表达式求值
  2. Huffman编码：数据压缩
  3. 决策树：机器学习分类
  4. 文件系统：目录结构表示
  5. 语法树：编译器设计
  6. 数据库索引：B+树的基础
  7. 优先队列：堆的实现

参考资料