二叉排序树 C语言实现_二叉排序树的c语言实现

基础知识

• 二叉排序树，又称二叉搜索树(Binary search tree)，是一种拥有排序功能的二叉树结构。其特点有：

1. 结点k的所有左子树结点，都小于等于结点k
2. 结点k的所有右子树结点，都大于等于结点k
3. k的子树也都是二叉排序树（递归）

显然，BST的中序遍历输出即为有序递增序列
二叉树的搜索，插入等操作是基于二分法的，所以时间复杂度为logn

• 二叉树的节点定义

typedef struct BST{
	int key;
	struct BST *lchild;
	struct BST *rchild;
}BST;
1
2
3
4
5

构建BST

创建

利用插入操作进行创建，首个节点在insert中分配，并将它赋值给指针bst，因为在insert中，要改变的是
bst指向的内存的内容，而不改变指针的位置，即将指针传递给函数，并在函数中修改指针的值，所以这里用了二级指针。

//创建 
void create(BST **bst, int *key, int n){
	int i=0;
	for(i=0; i<n; i++){
		insert(bst, key[i]);	
	}//这里不需要返回值
}
1
2
3
4
5
6
7

插入

在插入元素x时，从根节点开始，让x与节点的key比较，如果x < key，则将x递归插入到key 的左子树中，否则将x递归插入到key的右子树中; 如果子树不存在(到了叶节点)，则分配内存，并将x放入。

//插入 
int insert(BST **bt, int key){
	if(*bt == NULL){
		*bt = (BST*)malloc(sizeof(BST));
		if(*bt == NULL){
			printf("分配内存失败\n");
			return 0;
		}
		(*bt)->key = key;
		(*bt)->lchild = (*bt)->rchild = NULL;
		return 1;
	}
	if(key == (*bt)->key){//如果已存在，则插入失败 
		printf("%d已存在！\n", key);
		return 0;
	}
	else if(key < (*bt)->key)
		insert(&(*bt)->lchild, key);
	else
		insert(&(*bt)->rchild, key);	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

查找

查找元素x，方式为二分查找，从根节点开始，让x与节点的key比较，如果x < key，则在key 的左子树中查找，否则在key的右子树中查找。若找到，返回x对应的指针，否则查找失败

//查找, 返回值是BST指针 
BST *search(BST *bt, int key){
	if(bt == NULL){
		printf("查找失败！\n");
		return bt;
	}
	else{
		if(bt->key == key){
			return bt;
		}//递归查找
		else if(key < bt->key)
			return search(bt->lchild, key);	
		else
			return search(bt->rchild, key);
	}	 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

删除节点

删除节点比较复杂，大体分4种情况

1. 左右子树都为空
   直接清空指针内容即可，*p = NULL;
   
2. 左子树为空，右子树不为空
   
3. 右子树为空，左子树不为空
   
4. 左右子树都不为空
   若将节点p删除，代替它的应该是中序遍历中p的直接前驱s，只需要找到s，将其值赋给p，然后将s删除掉即可，而且对于s，一定符合上面两种情况，删除较容易。
   根据中序遍历规则，s的位置一定是下面两种情况
   
   
   为了便于操作，我们另p为s的父节点。
   (a). q != p
   (b). q == p
   
   代码如下：

//删除节点 
int delnode(BST **p){
	//删除节点有4种情况
	BST *s, *q;	
	if((*p)->lchild == NULL && (*p)->rchild == NULL){ //左右子树都为空!
		*p = NULL;  //二级指针下，可以直接令*p = NULL 
		return 1; 	
	}
	else if(!(*p)->lchild){//左子树为空 
		q = *p;  //让q指向p的右子树，然后把p的右子树挪到p的位置 
		*p = (*p)->rchild;  
		free(q);  
		return 1;
	}
	else if(!(*p)->rchild){//右子树为空 
		q = *p;
		*p = (*p)->lchild;
		free(q);
		return 1;	
	}
	else{   //左右子树都不为空 
		s = (*p)->lchild;
		q = *p;
		while(s->rchild){ //找到中序遍历中p的直接前驱s 
			q = s;
			s = s->rchild;
		}
		(*p)->key = s->key;  //把前驱的值赋值给p
	
		if(q != (*p))//如果q = *p，则while没执行，即p->lchild = s 
			q->rchild = s->lchild; //叶子节点置空，必须使其父节点指向空，不能直接对叶子结点操作 
		else //如果q = s 
			q->lchild = s->lchild;//q不存在，p->lchild即为s 	
		free(s);			
	} 
	return 1;
} 
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

删除

递归删除

//删除
int del(BST **bt, int key){
	if(*bt == NULL){
		printf("未找到%d\n", key);
		return 0;
	}	
	if((*bt)->key == key){
		if(delnode(&(*bt)))
			printf("已删除%d\n", key);
		return 1;
	}
	else if((*bt)->key > key)
		return del(&(*bt)->lchild, key);//因为bt中的值要改变，所以这里必须传入实值，定义为二级指针 
	else
		return del(&(*bt)->rchild, key);
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

摧毁

//摧毁树
int destroy(BST *bst){
	if(bst == NULL){
		printf("树为空！\n");
		return 0;
	}
	while(bst){
		del(&bst, bst->key);	
	}
	free(bst);
	printf("树已摧毁！\n");
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

测试

int main(void){
	int *key;

	int n, i=0;
	int num, search_key, del_key;
	printf("输入n：\n");
	scanf("%d", &n);
	key = (int *)malloc(sizeof(int)*n);
	printf("输入数字:\n");
	for(i=0; i<n; i++){
		scanf("%d", &key[i]);
	}
	//创建 
	BST *bst = NULL;
	create(&bst, key, n);//这个数组传入指针即可
	//中序遍历 
	printf("中序遍历：\n");
	inorder(bst);
	//插入元素 
	printf("输入插入元素:\n");
	scanf("%d", &num);
	insert(&bst, num);
	printf("中序遍历：\n");
	inorder(bst);
	//查找元素 
	printf("输入查找元素：\n");
	scanf("%d", &search_key);
	BST *result = NULL;
	result = search(bst, search_key); //返回值是bt指针 
	if(result)
		printf("查找元素的指针是：result->key = %d\n", result->key); //这里的result即为BST指针 
	//删除元素
	printf("输入要删除的元素：\n");
	scanf("%d", &del_key); 
	del(&bst, del_key);
	printf("中序遍历：\n");
	inorder(bst);
	//摧毁,摧毁后要想使用必须重建bst 
	printf("摧毁树\n");
	destroy(bst);
	//printf("*bst = %d\n", *bst);
	
	return 0;
}
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

完整可运行代码

#include <stdio.h>
#include <stdlib.h>

typedef struct BST{
	int key;
	struct BST *lchild;
	struct BST *rchild;
}BST;

void create(BST **bst, int *key, int n);
int insert(BST **bt, int key);
void inorder(BST *bt);
BST *search(BST *bt, int key);  
int delnode(BST **p);
int del(BST **bt, int key);
int destroy(BST *bst); 

int main(void){
	int *key;
	
	int n, i=0;
	int num, search_key, del_key;
	printf("输入n：\n");
	scanf("%d", &n);
	key = (int *)malloc(sizeof(int)*n);
	printf("输入数字:\n");
	for(i=0; i<n; i++){
		scanf("%d", &key[i]);
	}
	//创建 
	BST *bst = NULL;
	create(&bst, key, n);//这个数组传入指针即可
	//中序遍历 
	printf("中序遍历：\n");
	inorder(bst);
	//插入元素 
	printf("输入插入元素:\n");
	scanf("%d", &num);
	insert(&bst, num);
	printf("中序遍历：\n");
	inorder(bst);
	//查找元素 
	printf("输入查找元素：\n");
	scanf("%d", &search_key);
	BST *result = NULL;
	result = search(bst, search_key); //返回值是bt指针 
	if(result)
		printf("查找元素的指针是：result->key = %d\n", result->key); //这里的result即为BST指针 
	//删除元素
	printf("输入要删除的元素：\n");
	scanf("%d", &del_key); 
	del(&bst, del_key);
	printf("中序遍历：\n");
	inorder(bst);
	//摧毁,摧毁后要想使用必须重建bst 
	printf("摧毁树\n");
	destroy(bst);
	//printf("*bst = %d\n", *bst);
	
	return 0;
}
//创建 
void create(BST **bst, int *key, int n){
	int i=0;
	for(i=0; i<n; i++){
		insert(bst, key[i]);	
	}
}
//插入 
int insert(BST **bt, int key){
	if(*bt == NULL){
		*bt = (BST*)malloc(sizeof(BST));
		if(*bt == NULL){
			printf("分配内存失败\n");
			return 0;
		}
		(*bt)->key = key;
		(*bt)->lchild = (*bt)->rchild = NULL;
		//printf("(*bt)->key=%d\n",(*bt)->key);
		return 1;
	}
	if(key == (*bt)->key){//如果已存在，则插入失败 
		printf("%d已存在！\n", key);
		return 0;
	}
	else if(key < (*bt)->key)
		insert(&(*bt)->lchild, key);
	else
		insert(&(*bt)->rchild, key);	
	return 0;
}
//查找  返回值是BST指针 
BST *search(BST *bt, int key){
	if(bt == NULL){
		printf("查找失败！\n");
		return bt;
	}
	else{
		if(bt->key == key){
			return bt;
		}
		else if(key < bt->key)
			return search(bt->lchild, key);	
		else
			return search(bt->rchild, key);
	}	 
}
//删除节点 
int delnode(BST **p){
	//删除节点有4种情况
	BST *s, *q;
		
	if((*p)->lchild == NULL && (*p)->rchild == NULL){ //左右子树都为空!
		*p = NULL;  //二级指针下，可以直接令*p = NULL 
		return 1; 	
	}
	else if(!(*p)->lchild){//左子树为空 
		q = *p;  //让q指向p的右子树，然后把p的右子树挪到p的位置 
		*p = (*p)->rchild; 
		free(q); 
		return 1;
	}
	else if(!(*p)->rchild){//右子树为空 
		q = *p;
		*p = (*p)->lchild;
		free(q);
		return 1;	
	}
	else{   //左右子树都不为空 
		s = (*p)->lchild;
		q = *p;
		while(s->rchild){ //找到中序遍历中p的直接前驱 
			q = s;
			s = s->rchild;
		}
		(*p)->key = s->key;  //把前驱的值赋值给p
	
		if(q != (*p))//如果q = *p，则while没执行，即p->lchild = s 
			q->rchild = s->lchild; //叶子节点置空，必须使其父节点指向空，不能直接对叶子结点操作 
		else //如果q = s 
			q->lchild = s->lchild;//q不存在，p->lchild即为s 
			
		free(s);			
	} 
	return 1;
} 
//删除
int del(BST **bt, int key){
	if(*bt == NULL){
		printf("未找到%d\n", key);
		return 0;
	}	
	if((*bt)->key == key){
		if(delnode(&(*bt)))
			printf("已删除%d\n", key);
		return 1;
	}
	else if((*bt)->key > key)
		return del(&(*bt)->lchild, key);//因为bt中的值要改变，所以这里必须传入实值，定义为二级指针 
	else
		return del(&(*bt)->rchild, key);
} 
//摧毁树
int destroy(BST *bst){
	if(bst == NULL){
		printf("树为空！\n");
		return 0;
	}
	while(bst){
		del(&bst, bst->key);	
	}
	free(bst);
	printf("树已摧毁！\n");
	return 1;
}
//中序遍历
void inorder(BST *bt){
	if(bt!=NULL){
		inorder(bt->lchild);
		printf("%d\n",bt->key);
		inorder(bt->rchild);
	}
}
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