二叉树

数据结构

二叉树

什么是二叉树？

树是一种非线性的数据结构，它由节点（Node）和边（Edge）组成，并且具有层级关系。每个节点可以有零个或多个子节点。

而二叉树（Binary Tree） 是一种特殊的树，它的每个节点最多只有两个子节点，分别称为左子节点（Left Child） 和 右子节点（Right Child）。

基本概念：

  • 根节点（Root Node）： 树的顶端节点，没有父节点。
  • 父节点（Parent Node）： 拥有子节点的节点。
  • 子节点（Child Node）： 依附于父节点的节点。
  • 兄弟节点（Sibling Node）： 拥有同一个父节点的节点。
  • 叶子节点（Leaf Node）： 没有子节点的节点。
  • 路径（Path）： 从一个节点到另一个节点所经过的节点序列。
  • 深度（Depth）： 从根节点到某个节点的路径上的边数。根节点的深度为 0。
  • 高度（Height）： 从某个节点到其最远叶子节点的路径上的边数。叶子节点的高度为 0。树的高度是根节点的高度。
  • 层（Level）： 节点的深度加 1。根节点在第 1 层。

2. C 语言中的二叉树节点定义

与链表类似，二叉树的节点也可以通过结构体来定义。

1
2
3
4
5
6
7
8
9
#include <stdio.h>
#include <stdlib.h> // 包含 malloc 和 free

// 定义二叉树节点结构体
typedef struct TreeNode {
    int data;               // 数据域
    struct TreeNode *left;  // 指向左子节点的指针
    struct TreeNode *right; // 指向右子节点的指针
} TreeNode;

3. 二叉树的类型

二叉树有很多种类型，理解它们有助于我们更好地应用：

  • 满二叉树（Full Binary Tree）： 除了叶子节点外，所有节点都有两个子节点。

  • 完全二叉树（Complete Binary Tree）： 除了最后一层，其他层都被完全填满，并且最后一层的所有节点都尽可能地靠左排列。

  • 平衡二叉树（Balanced Binary Tree）： 左右子树的高度差不超过 1，并且左右子树都是平衡二叉树。常见的有 AVL 树和红黑树。

  • 二叉搜索树（Binary Search Tree, BST）：

    对所有节点都满足以下条件：

    • 左子树中所有节点的值都小于当前节点的值。
    • 右子树中所有节点的值都大于当前节点的值。
    • 左右子树也都是二叉搜索树。

4. 二叉树的遍历方式

遍历二叉树是指按照某种顺序访问树中的所有节点。二叉树的遍历是面试常考点，也是理解树结构的关键。主要有四种基本遍历方式：

4.1 深度优先遍历（Depth-First Search, DFS）

深度优先遍历沿着树的深度方向进行，直到无法继续深入，然后回溯。主要有三种：

  • 前序遍历（Pre-order Traversal）： 访问顺序为：根节点 -> 左子树 -> 右子树。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 前序遍历
    void preOrderTraversal(TreeNode* root) {
        if (root == NULL) {
            return;
        }
        printf("%d ", root->data);      // 访问根节点
        preOrderTraversal(root->left);  // 递归遍历左子树
        preOrderTraversal(root->right); // 递归遍历右子树
    }

  • 中序遍历（In-order Traversal）： 访问顺序为：左子树 -> 根节点 -> 右子树。

    对于二叉搜索树，中序遍历会得到一个有序的序列。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 中序遍历
    void inOrderTraversal(TreeNode* root) {
        if (root == NULL) {
            return;
        }
        inOrderTraversal(root->left);  // 递归遍历左子树
        printf("%d ", root->data);      // 访问根节点
        inOrderTraversal(root->right); // 递归遍历右子树
    }

  • 后序遍历（Post-order Traversal）： 访问顺序为：左子树 -> 右子树 -> 根节点。

    通常用于在删除节点前先删除子节点，或计算表达式树。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 后序遍历
    void postOrderTraversal(TreeNode* root) {
        if (root == NULL) {
            return;
        }
        postOrderTraversal(root->left);  // 递归遍历左子树
        postOrderTraversal(root->right); // 递归遍历右子树
        printf("%d ", root->data);      // 访问根节点
    }

4.2 广度优先遍历（Breadth-First Search, BFS）/ 层序遍历（Level-order Traversal）

广度优先遍历逐层访问树的节点，从上到下，从左到右。通常需要借助队列（Queue）来实现。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 队列结构（用于层序遍历）
typedef struct QueueNode {
    TreeNode* treeNode;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

void enqueue(Queue* q, TreeNode* treeNode) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->treeNode = treeNode;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

TreeNode* dequeue(Queue* q) {
    if (q->front == NULL) {
        return NULL;
    }
    QueueNode* temp = q->front;
    TreeNode* treeNode = temp->treeNode;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return treeNode;
}

int isQueueEmpty(Queue* q) {
    return q->front == NULL;
}

// 层序遍历 (需要队列辅助)
void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    Queue* q = createQueue();
    enqueue(q, root);

    printf("层序遍历：");
    while (!isQueueEmpty(q)) {
        TreeNode* current = dequeue(q);
        printf("%d ", current->data);

        if (current->left != NULL) {
            enqueue(q, current->left);
        }
        if (current->right != NULL) {
            enqueue(q, current->right);
        }
    }
    printf("\n");
    // 释放队列内存（这里省略了详细的队列内存释放，实际应用中需要确保释放）
    free(q);
}

5. 二叉搜索树（BST）的实现

BST 是一种非常实用的二叉树，它能高效地进行查找、插入和删除操作。

5.1 插入节点

插入新节点时，从根节点开始比较，如果新节点的值小于当前节点，则进入左子树；如果大于当前节点，则进入右子树。直到找到一个空位置插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 插入节点到二叉搜索树
TreeNode* insertNode(TreeNode* root, int value) {
    if (root == NULL) {
        TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
        if (newNode == NULL) {
            printf("内存分配失败！\n");
            exit(1);
        }
        newNode->data = value;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }

    if (value < root->data) {
        root->left = insertNode(root->left, value);
    } else if (value > root->data) {
        root->right = insertNode(root->right, value);
    }
    // 如果值相等，通常不插入重复值，或者根据需求决定
    return root;
}

5.2 查找节点

查找节点与插入类似，通过比较值来决定向左还是向右查找。

1
2
3
4
5
6
7
8
9
10
11
// 在二叉搜索树中查找节点
TreeNode* searchNode(TreeNode* root, int value) {
    if (root == NULL || root->data == value) {
        return root;
    }
    if (value < root->data) {
        return searchNode(root->left, value);
    } else {
        return searchNode(root->right, value);
    }
}

5.3 删除节点

删除节点是 BST 操作中最复杂的一个，需要处理以下几种情况：

  1. 待删除节点是叶子节点： 直接删除，并将其父节点对应的指针置为 NULL。
  2. 待删除节点只有一个子节点： 用其子节点替换待删除节点。
  3. 待删除节点有两个子节点： 找到其右子树中的最小节点（或左子树中的最大节点）来替换它，然后删除那个最小（或最大）节点。
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
// 查找二叉搜索树中最小值的节点 (用于删除操作)
TreeNode* findMinNode(TreeNode* node) {
    TreeNode* current = node;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

// 从二叉搜索树中删除节点
TreeNode* deleteNode(TreeNode* root, int value) {
    if (root == NULL) {
        return root;
    }

    if (value < root->data) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);
    } else { // 找到了要删除的节点
        // 情况1: 没有子节点或只有一个子节点
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }

        // 情况2: 有两个子节点
        TreeNode* temp = findMinNode(root->right); // 找到右子树中最小的节点
        root->data = temp->data; // 将最小节点的数据复制到当前节点
        root->right = deleteNode(root->right, temp->data); // 在右子树中删除那个最小节点
    }
    return root;
}

5.4 释放二叉树内存

递归地释放所有节点。

1
2
3
4
5
6
7
8
9
// 释放二叉树所有节点的内存
void freeTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

6. 完整示例代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构体
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 队列结构（用于层序遍历）
typedef struct QueueNode {
    TreeNode* treeNode;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// Queue辅助函数
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

void enqueue(Queue* q, TreeNode* treeNode) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->treeNode = treeNode;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

TreeNode* dequeue(Queue* q) {
    if (q->front == NULL) {
        return NULL;
    }
    QueueNode* temp = q->front;
    TreeNode* treeNode = temp->treeNode;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return treeNode;
}

int isQueueEmpty(Queue* q) {
    return q->front == NULL;
}

void freeQueue(Queue* q) {
    while (!isQueueEmpty(q)) {
        dequeue(q); // 只是为了清空节点，TreeNode*已经被返回并处理了
    }
    free(q);
}

// 创建一个新节点（辅助函数）
TreeNode* createNewNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// ---- 二叉树遍历 ----
void preOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

void inOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inOrderTraversal(root->left);
    printf("%d ", root->data);
    inOrderTraversal(root->right);
}

void postOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    printf("%d ", root->data);
}

void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    Queue* q = createQueue();
    enqueue(q, root);
    printf("层序遍历：");
    while (!isQueueEmpty(q)) {
        TreeNode* current = dequeue(q);
        printf("%d ", current->data);
        if (current->left != NULL) enqueue(q, current->left);
        if (current->right != NULL) enqueue(q, current->right);
    }
    printf("\n");
    free(q); // 释放队列本身
}

// ---- 二叉搜索树操作 ----
TreeNode* insertNode(TreeNode* root, int value) {
    if (root == NULL) {
        return createNewNode(value);
    }
    if (value < root->data) {
        root->left = insertNode(root->left, value);
    } else if (value > root->data) {
        root->right = insertNode(root->right, value);
    }
    return root;
}

TreeNode* searchNode(TreeNode* root, int value) {
    if (root == NULL || root->data == value) {
        return root;
    }
    if (value < root->data) {
        return searchNode(root->left, value);
    } else {
        return searchNode(root->right, value);
    }
}

TreeNode* findMinNode(TreeNode* node) {
    TreeNode* current = node;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

TreeNode* deleteNode(TreeNode* root, int value) {
    if (root == NULL) {
        return root;
    }

    if (value < root->data) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);
    } else { // 找到了要删除的节点
        if (root->left == NULL) { // 没有左子或没有子节点
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) { // 只有左子
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        // 有两个子节点
        TreeNode* temp = findMinNode(root->right); // 找到右子树中最小的节点
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// 释放二叉树所有节点的内存
void freeTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    TreeNode* root = NULL; // 初始化空二叉搜索树

    printf("------ 插入节点 ------\n");
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 70);
    root = insertNode(root, 20);
    root = insertNode(root, 40);
    root = insertNode(root, 60);
    root = insertNode(root, 80);

    printf("\n------ 遍历操作 ------\n");
    printf("前序遍历：");
    preOrderTraversal(root);
    printf("\n");

    printf("中序遍历：");
    inOrderTraversal(root); // 对于BST，中序遍历是升序
    printf("\n");

    printf("后序遍历：");
    postOrderTraversal(root);
    printf("\n");

    levelOrderTraversal(root);

    printf("\n------ 查找操作 ------\n");
    if (searchNode(root, 40) != NULL) {
        printf("找到了值为 40 的节点。\n");
    } else {
        printf("未找到值为 40 的节点。\n");
    }

    if (searchNode(root, 90) != NULL) {
        printf("找到了值为 90 的节点。\n");
    } else {
        printf("未找到值为 90 的节点。\n");
    }

    printf("\n------ 删除操作 ------\n");
    printf("删除节点 20 (叶子节点):\n");
    root = deleteNode(root, 20);
    levelOrderTraversal(root);

    printf("删除节点 70 (有一个子节点):\n");
    root = deleteNode(root, 70); // 80会上移
    levelOrderTraversal(root);

    printf("删除节点 50 (有两个子节点):\n");
    root = deleteNode(root, 50); // 60会上移
    levelOrderTraversal(root);

    printf("\n------ 内存释放 ------\n");
    freeTree(root);
    printf("二叉树内存已释放。\n");

    return 0;
}

Title:二叉树

Author:

Created:2025-05-30, 20:05:21

Updated:2025-05-30, 20:47:21

Full URL:http://example.com/2025/05/30/%E4%BA%8C%E5%8F%89%E6%A0%91/

License: "CC BY-NC-SA 4.0" Keep Link & Author if Distribute.

Contents
  1. 1. 二叉树
    1. 1.1. 什么是二叉树？
    2. 1.2. 2. C 语言中的二叉树节点定义
    3. 1.3. 3. 二叉树的类型
    4. 1.4. 4. 二叉树的遍历方式
      1. 1.4.1. 4.1 深度优先遍历（Depth-First Search, DFS）
      2. 1.4.2. 4.2 广度优先遍历（Breadth-First Search, BFS）/ 层序遍历（Level-order Traversal）
    5. 1.5. 5. 二叉搜索树（BST）的实现
      1. 1.5.1. 5.1 插入节点
      2. 1.5.2. 5.2 查找节点
      3. 1.5.3. 5.3 删除节点
      4. 1.5.4. 5.4 释放二叉树内存
    6. 1.6. 6. 完整示例代码
|