第六节、二叉树
什么是二叉树？
二叉树是一种树状结构，它由节点和边组成。每个节点最多有两个子节点，分别称为左子节点和右子节点。一个节点没有子节点的情况称为叶节点。
二叉树的基本操作
在C语言中，我们可以使用结构体来定义二叉树节点：
1
2
3
4
5
| struct Node {
int data;
struct Node* left;
struct Node* right;
};
|
这个结构体定义了一个二叉树节点，它有一个整数数据域和两个指针域，分别指向左子节点和右子节点。
插入节点
二叉树的插入操作通常用递归实现。我们从根节点开始，如果当前节点为空，就把新节点插入到当前位置，否则就比较新节点和当前节点的大小，如果新节点小于当前节点，就递归插入到当前节点的左子树，否则递归插入到当前节点的右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| struct Node* insert(struct Node* root, int data) {
if (root == NULL) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
if (data < root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}
|
遍历二叉树
二叉树的遍历有三种方式：前序遍历、中序遍历和后序遍历。前序遍历是先访问当前节点，然后递归遍历左子树和右子树；中序遍历是先递归遍历左子树，然后访问当前节点，最后递归遍历右子树；后序遍历是先递归遍历左子树和右子树，最后访问当前节点。
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_traversal(struct Node* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
preorder_traversal(root->left);
preorder_traversal(root->right);
}
void inorder_traversal(struct Node* root) {
if (root == NULL) {
return;
}
inorder_traversal(root->left);
printf("%d ", root->data);
inorder_traversal(root->right);
}
void postorder_traversal(struct Node* root) {
if (root == NULL) {
return;
}
postorder_traversal(root->left);
postorder_traversal(root->right);
printf("%d ", root->data);
}
|
查找节点
二叉树的查找操作也通常用递归实现。我们从根节点开始，如果当前节点为空，就说明要查找的节点不存在；如果要查找的节点等于当前节点，就返回当前节点；否则就比较要查找的节点和当前节点的大小，如果要查找的节点小于当前节点，就递归查找左子树；如果要查找的节点大于当前节点，就递归查找右子树。
1
2
3
4
5
6
7
8
9
10
| struct Node* search(struct Node* root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return search(root->left, data);
} else {
return search(root->right, data);
}
}
|
删除节点
二叉树的删除操作需要考虑多种情况。如果要删除的节点是叶节点，直接删除即可；如果要删除的节点有一个子节点，就用子节点代替当前节点；如果要删除的节点有两个子节点，就找到当前节点的中序遍历的后继节点（即大于当前节点值的最小节点），用后继节点代替当前节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| struct Node* delete(struct Node* root, int data) {
if (root == NULL) {
return root;
}
if (data < root->data) {
root->left = delete(root->left, data);
} else if (data > root->data) {
root->right = delete(root->right, data);
} else {
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}
struct Node* temp = min_value_node(root->right);
root->data = temp->data;
root->right = delete(root->right, temp->data);
}
return root;
}
|
完整代码
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
| #include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* new_node(int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
struct Node* insert(struct Node* root, int data) {
if (root == NULL) {
return new_node(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
}
else {
root->right = insert(root->right, data);
}
return root;
}
void preorder_traversal(struct Node* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
preorder_traversal(root->left);
preorder_traversal(root->right);
}
void inorder_traversal(struct Node* root) {
if (root == NULL) {
return;
}
inorder_traversal(root->left);
printf("%d ", root->data);
inorder_traversal(root->right);
}
void postorder_traversal(struct Node* root) {
if (root == NULL) {
return;
}
postorder_traversal(root->left);
postorder_traversal(root->right);
printf("%d ", root->data);
}
struct Node* search(struct Node* root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return search(root->left, data);
}
else {
return search(root->right, data);
}
}
struct Node* min_value_node(struct Node* node) {
struct Node* current = node;
while (current->left != NULL) {
current = current->left;
}
return current;
}
struct Node* Delete(struct Node* root, int data) {
if (root == NULL) {
return root;
}
if (data < root->data) {
root->left = Delete(root->left, data);
}
else if (data > root->data) {
root->right = Delete(root->right, data);
}
else {
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}
struct Node* temp = min_value_node(root->right);
root->data = temp->data;
root->right = Delete(root->right, temp->data);
}
return root;
}
int main() {
struct Node* root = NULL;
root = insert(root, 5);
root = insert(root, 3);
root = insert(root, 7);
root = insert(root, 1);
root = insert(root, 9);
root = insert(root, 4);
root = insert(root, 6);
printf("Preorder traversal: ");
preorder_traversal(root);
printf("\n");
printf("Inorder traversal: ");
inorder_traversal(root);
printf("\n");
printf("Postorder traversal: ");
postorder_traversal(root);
printf("\n");
struct Node* search_result = search(root, 7);
if (search_result != NULL) {
printf("Found: %d\n", search_result->data);
}
else {
printf("Not found\n");
}
root = Delete(root, 5);
printf("Inorder traversal after deleting 5: ");
inorder_traversal(root);
printf("\n");
return 0;
}
|
