二叉查找树要求，在树中的任意一个节点，其【左子树】中的每个节点的值，都要【小于】这个节点的值，而【右子树】节点的值都【大于】这个节点的值。

目录

1. 头文件

1.1 include

1.2  定义树是否为空

1.3 树的数据结构

1.4 节点结构体

1.5 树结构体

2. 创建空树

2.1 给树赋空间，malloc

2.2 判断树是否创建成功

2.3 给树的各个参数赋值

2.4 返回树

3. 查找

3.1 创建指针，用于搜索

3.2 判断树是否存在&树为空

3.3 循环，比较值得大小，直接找到节点

3.4 返回节点

4. 插入节点

4.1 判断树是否为空

4.2 创建空节点，判断是否创建成功，给参数赋值

4.3 插入节点

4.3.1 树为空

4.3.2 树不为空

4.4 树不为空，创建空指针来查找

4.5 进入循环，比较大小，判断节点进入左子节点，还是右子节点

5. 删除节点

5.1 三种情况

5.1.1 删除的节点没有子节点

5.1.2 删除的节点有一个子节点

5.1.3 删除的节点有两个子节点

5.2 创建四个指针

5.3 判断树是否存在 & 树是否为空

5.4 循环指针，直到找到待删除接节点

5.5 判断节点是否有两个子节点

5.6 判断待删除结点有一个子节点或者为NULL

5.7 判断node在pnode的左/右子节点

size--;">5.8 free(node) ; tree->size--;

6. 递归方式删除结点

7. 中序遍历打印树节点

8. compare 函数

9. 主函数

10. 总览代码 

 11. 代码结果

1. 头文件

        1.1 include

        1.2  定义树是否为空

        1.3 树的数据结构

        1.4 节点结构体

        1.5 树结构体

#include
#include
#include

#define bstree_is_empty(tree)(tree->size == 0)          

typedef int type;

typedef struct bstree_node {
	type data;
	struct bstree_node* lchild;
	struct bstree_node* rchild;
}stbstree_node;				

typedef struct bstree {
	int size;
	int (*compare)(type key1, type key2);
	int (*destory)(type data);
	stbstree_node* root;
}stbstree;


typedef int (*compare_fuc)(type key1, type key2);       //key1 > key2  返回1  否则  返回-1
typedef int (*destory_fuc)(type data);

2. 创建空树

        2.1 给树赋空间，malloc

        2.2 判断树是否创建成功

        2.3 给树的各个参数赋值

        2.4 返回树

stbstree* bstree_create(compare_fuc compare,destory_fuc destory) {
	stbstree* tree = NULL;
	tree = (stbstree*)malloc(sizeof(stbstree));
	if (tree == NULL) {
		return NULL;
	}
	tree->size = 0;
	tree->compare = compare;
	tree->destory = destory;
	tree->root = NULL;
	return tree;
}

3. 查找

        3.1 创建指针，用于搜索

        3.2 判断树是否存在&树为空

        3.3 循环，比较值得大小，直接找到节点

        3.4 返回节点

stbstree_node* bstree_search(stbstree* tree, type data) {
	stbstree_node* node = NULL;
	int res = 0;
	if (tree == NULL && bstree_is_empty(tree)) {
		return NULL;
	}
	node = tree->root;
	 
	while (node != NULL) {
		res = tree->compare(data, node->data);
		if (res == 0) {
			return node;
		}
		else if (res > 0) {
			node = node->rchild;
		}
		else {
			node = node->rchild;
		}
	}
	return NULL;
}

4. 插入节点

        4.1 判断树是否为空

        4.2 创建空节点，判断是否创建成功，给参数赋值

        4.3 插入节点

                4.3.1 树为空

                4.3.2 树不为空

        4.4 树不为空，创建空指针来查找

        4.5 进入循环，比较大小，判断节点进入左子节点，还是右子节点

int bstree_insert(stbstree* tree, type data) {
	stbstree_node* node = NULL;           //插入结点
	stbstree_node* tmp = NULL;            //代替树的头指针
	int res = 0;
	if (tree == NULL) {
		return -1;
	} 
	node = (stbstree_node*)malloc(sizeof(stbstree_node));
	if (node == NULL) {
		return - 2;
	}
	node->data = data;
	node->lchild = NULL;
	node->rchild = NULL;
	
	if (bstree_is_empty(tree)){
		tree->root = node;
		tree->size++;
		return 0;
	}
	tmp = tree->root;        
	while (tmp != NULL) {
		res = tree->compare(data,tmp->data);
		if (res > 0) {
			if (tmp->rchild == NULL) {
				tmp->rchild = node;
				tree->size++;
				return 0;
			}
			tmp = tmp->rchild;
		}
		else {
			if (tmp->lchild == NULL) {
				tmp->lchild == node;
				tree->size++;
				return 0;
			}
			tmp = tmp->lchild;
		}
	}
}

5. 删除节点

        5.1 三种情况

                5.1.1 删除的节点没有子节点

                5.1.2 删除的节点有一个子节点

                5.1.3 删除的节点有两个子节点

        5.2 创建四个指针

                        分别是删除节点、待删除结点的父节点、最小节点、最小节点的父节点

        5.3 判断树是否存在 & 树是否为空

        5.4 循环指针，直到找到待删除接节点

        5.5 判断节点是否有两个子节点

                        如果有，找到删除节点右子树的最小节点，替换节点值，将node、pnode指向minnode、pminnode，这样待删除节点只有一个右节点或者没有（因为是最小节点，不会有左子节点，不然，就不是最小节点）

        5.6 判断待删除结点有一个子节点或者为NULL

                        将minnode指针指向它

        5.7 判断node在pnode的左/右子节点

                        将minnode赋给pnode的左/右子节点

        5.8 free(node) ; tree->size--;

int bstree_delete(stbstree* tree, type data) {
	stbstree_node* node = NULL;             //待删除结点
	stbstree_node* pnode = NULL;            //待删除结点的父节点
	stbstree_node* minnode = NULL;          //最小结点
	stbstree_node* pminnode = NULL;         //最小结点的父节点
	type tmp = 0;
	int res = 0;
	if (tree == NULL || bstree_is_empty(tree)) {
		return -1;
	}
	node = tree->root;
	while (node != NULL && (res = tree->compare(data, node->data)) != 0) {     //node为NULL 和 找到删除结点
		pnode = node;
		if (res > 0) {
			node = node->rchild;
		}
		else {
			node = node->lchild;
		}
	}
	if (node == NULL) {
		return -2;
	}                                                               //已找到删除结点，判断删除结点有几个子节点
	if (node->lchild != NULL && node->rchild != NULL) {
		minnode = node->rchild;                                     //需要找到右子树的最小结点，替换到删除结点，删除最小结点，因为最小节点肯定没有左子结点
		pminnode = node;
		while (minnode->lchild != NULL) {
			pminnode = minnode;
			minnode = minnode->lchild;
		}															//找到最小结点

		tmp = node->data;                                           //替换结点值
		node->data = minnode->data;
		minnode->data = tmp;

		node = minnode;                                             //将node、pnode指针指向minnode、pminnode
		pnode = pminnode;											//node只有一个子节点或没有子节点
	}
	
	//判断有哪个子节点
	if (node->lchild != NULL) {
		minnode = node->lchild;
	}
	else if (node->rchild != NULL) {
		minnode = node->rchild;
	}
	else {
		minnode = NULL;
	}
	//删除node结点，将pnode指针指向minnode
	if (pnode == NULL) {
		tree->root = minnode;
	}
	else if(pnode->lchild == node){
		pnode->lchild = minnode;
	}
	else {
		pnode->rchild = minnode;
	}
	tree->size--;
	free(node);
	return 0;
}

6. 递归方式删除结点

void bstree_destory_node(stbstree* tree,stbstree_node* root){
	if (root == NULL) {
		return;
	}
	bstree_destory_node(tree, root->lchild);
	bstree_destory_node(tree, root->rchild);
	free(root);
}

7. 中序遍历打印树节点

void bstree_inorder(stbstree_node* root) {
	
	if (root == NULL) {
		return;
	}
	bstree_inorder(root->lchild);
	printf(" %d ", root->data);
	bstree_inorder(root->rchild);
	return;
}

8. compare 函数

int bstree_compare(type key1, type key2) {
	if (key1 == key2) {
		return 0;
	}
	else if (key1 > key2) {
		return 1;
	}
	else {
		return -1;
	}
}

9. 主函数

int main() {
	stbstree* tree = NULL;
	stbstree_node* node = NULL;
	type data = 0;
	int res = 0;

	tree = bstree_create(bstree_compare, NULL);
	while (1) {
		printf("插入一个数字，输入100时退出：n");
		scanf_s("%d", &data);
		if (data == 100)break;
		res = bstree_insert(tree, data);
		printf("%d 插入%s成功n", data, (res != 0) ? ("不") : (""));
	}
	bstree_inorder(tree->root);
}

10. 总览代码 

 11. 代码结果

 发现问题了吗，代码自能打印出左子树，55，插入，打印都没有问题，就是打印不出来，容我慢慢改...