二叉搜索树（C语言实现）

2024-01-12 12:13:22

数据结构

typedef struct TreeNode {
	int data;//数据 
	struct TreeNode* left;//左孩子 
	struct TreeNode* right;//右孩子 
}BST, *BinTree;

函数声明

void Insert(BinTree& BST, int x);//插入元素 
void Delete(BinTree& BST, int x);//删除元素 
BinTree FindMin(BinTree BST);//找寻最小值
BinTree FindMax(BinTree BST);//找寻最大值
BinTree FindElem(BinTree BST, int x);//按值查找
void MidOrder(BinTree BST);//中序遍历

void Insert_menu(BinTree& BST);
void Delete_menu(BinTree& BST);
void FindMin_menu(BinTree BST);
void FindMax_menu(BinTree BST);
void FindElem_menu(BinTree BST);
void MidOrder_menu(BinTree BST);

插入元素

//插入元素 
void Insert(BinTree& BST, int x) {
	if (BST == NULL) {
		BST = (BinTree)malloc(sizeof(struct TreeNode));//构建结点 
		BST->data = x;
		BST->left = NULL;
		BST->right = NULL;
		return;
	}
	else if (x > BST->data) {//去右边找 
		Insert(BST->right, x);
	}

	else if (x < BST->data) {//去左边找 
		Insert(BST->left, x);
	}
}

删除元素

void Delete(BinTree& BST, int x)
{
	if (BST == NULL) return;
	BinTree node_temp = BST;
	BinTree node_par = NULL;
	BinTree temp = NULL;
	
	while (node_temp->data != x)
	{
		if (x > node_temp->data) {
			node_par = node_temp;
			node_temp = node_temp->right;
		}

		else if (x < node_temp->data) {
			node_par = node_temp;
			node_temp = node_temp->left;
		}
			
	}
	
	//无此值 
	if (node_temp == NULL) return;
	
	//叶节点
	if (node_temp->left == NULL && node_temp->right == NULL) {
		if (node_temp == BST) {
			BST = NULL;
		}
		else if (node_par->left == node_temp) {
			node_par->left = NULL;
		}
		else {
			node_par->right = NULL;
		}
	} 
	
	//单支节点 
	else if (node_temp->left != NULL || node_temp->right != NULL) {
		if (node_temp == BST) {
			if (node_temp->left != NULL) {
				BST = node_temp->left;
			}
			else {
				BST = node_temp->right;
			}
		}
		//非根结点 
		else {
			if (node_par->left == node_temp && temp->left != NULL) {
				node_par->left = node_temp->left;
			}
			if (node_par->left == node_temp && temp->right != NULL) {
				node_par->left = node_temp->right;
			}
			if (node_par->right == node_temp && temp->left != NULL) {
				node_par->right = node_temp->left;
			}
			if (node_par->right == node_temp && temp->right != NULL) {
				node_par->right = node_temp->right;
			}
		}
	}
	//双支节点 
	else if (node_temp->left != NULL && node_temp->right != NULL) {
		BinTree temp = node_temp;
		node_temp = node_temp->right;
		//找寻右子树的最小值 
		while (node_temp->right) {
			node_par = node_temp;//记录找到最小结点的父节点 
			node_temp = node_temp->left;
		}
		temp->data = node_temp->data;//数据覆盖
		if (node_par == temp) { //右子树只有一个元素 
			node_par = node_temp->right;
		} 
		else {
			node_par->left = node_temp->right;
		}
	}
	
	free(node_temp);
}

返回最小元素的结点

BinTree FindMin(BinTree BST) {
	if (BST == NULL)
		return NULL;
	while (BST->left != NULL) {
		BST = BST->left;
	}
	return BST;
}

返回最大元素的结点

BinTree FindMax(BinTree BST) {
	if (BST == NULL)
		return NULL;
	while (BST->right != NULL) {
		BST = BST->right;
	}
	return BST;
}

按值查找

//按值查找 
BinTree FindElem(BinTree BST, int x) {
	if (BST == NULL) {
		return NULL;
	}
	else if (x > BST->data) {
		BST = FindElem(BST->right,x);
	}
	else if (x < BST->data) {
		BST = FindElem(BST->left, x);
	}
	return BST;
}

中序遍历

void MidOrder(BinTree BST) {
	if (BST != NULL) {
		MidOrder(BST->left);
		printf("%d", BST->data);
		MidOrder(BST->right);
	}
}

源代码

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef struct TreeNode {
	int data;//数据 
	struct TreeNode* left;//左孩子 
	struct TreeNode* right;//右孩子 
}BST, *BinTree;

void Insert(BinTree& BST, int x);//插入元素 
void Delete(BinTree& BST, int x);//删除元素 
BinTree FindMin(BinTree BST);
BinTree FindMax(BinTree BST);
BinTree FindElem(BinTree BST, int x);
void MidOrder(BinTree BST);

void Insert_menu(BinTree& BST);
void Delete_menu(BinTree& BST);
void FindMin_menu(BinTree BST);
void FindMax_menu(BinTree BST);
void FindElem_menu(BinTree BST);
void MidOrder_menu(BinTree BST);

void menu();

int main() {
	BinTree BST = NULL;//记得初始化为空指针，否则报错
	int max, min;
	int choice;
	while (true)
	{
		menu();
		scanf("%d", &choice);
		switch (choice)
		{
		case 0:
			exit(1);
			break;
		case 1:
			Insert_menu(BST);
			break;
		case 2:
			Delete_menu(BST); 
			break;
		case 3:
			MidOrder_menu(BST);
			printf("\n");
			break;
		case 4:
			FindElem_menu(BST);
			break;
		case 5:
			FindMax_menu(BST);
			break;
		case 6:
			FindMin_menu(BST);
			break;
		}
	}
	
	for (int i = 1; i <= 5; i++) {
		Insert(BST, i);
	}
	MidOrder(BST);
	cout << endl;
	BinTree temp;
	temp = FindMax(BST);
	cout << "Max = " << temp->data << endl;
	temp = FindMin(BST);
	cout << "Min = " << temp->data << endl;
	Delete(BST, 2);
	if (BST != NULL)
	MidOrder(BST);
	return 0;
}

void menu()
{
	printf("------------0.退出程序------------\n");
	printf("------------1.插入元素------------\n");
	printf("------------2.删除元素------------\n");
	printf("------------3.中序遍历------------\n");
	printf("------------4.查找元素------------\n");
	printf("------------5.最大元素------------\n");
	printf("------------6.最小元素------------\n");
}

//插入元素 
void Insert(BinTree& BST, int x) {
	if (BST == NULL) {
		BST = (BinTree)malloc(sizeof(struct TreeNode));//构建结点 
		BST->data = x;
		BST->left = NULL;
		BST->right = NULL;
		return;
	}
	else if (x > BST->data) {//去右边找 
		Insert(BST->right, x);
	}

	else if (x < BST->data) {//去左边找 
		Insert(BST->left, x);
	}
}

//删除元素 
void Delete(BinTree& BST, int x)
{
	if (BST == NULL) return;
	BinTree node_temp = BST;
	BinTree node_par = NULL;
	BinTree temp = NULL;
	
	while (node_temp->data != x)
	{
		if (x > node_temp->data) {
			node_par = node_temp;
			node_temp = node_temp->right;
		}

		else if (x < node_temp->data) {
			node_par = node_temp;
			node_temp = node_temp->left;
		}
			
	}
	
	//无此值 
	if (node_temp == NULL) return;
	
	//叶节点
	if (node_temp->left == NULL && node_temp->right == NULL) {
		if (node_temp == BST) {
			BST = NULL;
		}
		else if (node_par->left == node_temp) {
			node_par->left = NULL;
		}
		else {
			node_par->right = NULL;
		}
	} 
	
	//单支节点 
	else if (node_temp->left != NULL || node_temp->right != NULL) {
		if (node_temp == BST) {
			if (node_temp->left != NULL) {
				BST = node_temp->left;
			}
			else {
				BST = node_temp->right;
			}
		}
		//非根结点 
		else {
			if (node_par->left == node_temp && temp->left != NULL) {
				node_par->left = node_temp->left;
			}
			if (node_par->left == node_temp && temp->right != NULL) {
				node_par->left = node_temp->right;
			}
			if (node_par->right == node_temp && temp->left != NULL) {
				node_par->right = node_temp->left;
			}
			if (node_par->right == node_temp && temp->right != NULL) {
				node_par->right = node_temp->right;
			}
		}
	}
	//双支节点 
	else if (node_temp->left != NULL && node_temp->right != NULL) {
		BinTree temp = node_temp;
		node_temp = node_temp->right;
		//找寻右子树的最小值 
		while (node_temp->right) {
			node_par = node_temp;//记录找到最小结点的父节点 
			node_temp = node_temp->left;
		}
		temp->data = node_temp->data;//数据覆盖
		if (node_par == temp) { //右子树只有一个元素 
			node_par = node_temp->right;
		} 
		else {
			node_par->left = node_temp->right;
		}
	}
	
	free(node_temp);
}

//最小元素 
BinTree FindMin(BinTree BST) {
	if (BST == NULL)
		return NULL;
	while (BST->left != NULL) {
		BST = BST->left;
	}
	return BST;
}

//最大元素 
BinTree FindMax(BinTree BST) {
	if (BST == NULL)
		return NULL;
	while (BST->right != NULL) {
		BST = BST->right;
	}
	return BST;
}

//按值查找 
BinTree FindElem(BinTree BST, int x) {
	if (BST == NULL) {
		return NULL;
	}
	else if (x > BST->data) {
		BST = FindElem(BST->right,x);
	}
	else if (x < BST->data) {
		BST = FindElem(BST->left, x);
	}
	return BST;
}

//中序遍历 
void MidOrder(BinTree BST) {
	if (BST != NULL) {
		MidOrder(BST->left);
		printf("%d", BST->data);
		MidOrder(BST->right);
	}
}

//---------------------------------------
void Insert_menu(BinTree& BST)
{
	int n, x;
	printf("请输入您想要插入的元素个数\n");
	scanf("%d", &n);
	printf("请输入元素\n");
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &x);
		Insert(BST, x);
	}
	printf("插入成功\n");
	system("pause");
	system("cls");
} 

void Delete_menu(BinTree& BST)
{
	printf("请输入您想删除的元素\n");
	int x; 
	scanf("%d", &x);
	Delete(BST,x);
	printf("删除成功\n");
	system("pause");
	system("cls");
}

void FindMin_menu(BinTree BST)
{
	BinTree temp = FindMin(BST);
	if (temp == NULL) 
	printf("树为空\n");
	else {
		printf("最小值为：%d", temp->data);
	}	
	system("pause");
	system("cls");
}

void FindMax_menu(BinTree BST)
{
	BinTree temp = FindMax(BST);
	if (temp == NULL) 
	printf("树为空\n");
	else {
		printf("最大值为：%d", temp->data);
	}
	system("pause");
	system("cls");
}

void FindElem_menu(BinTree BST)
{
	int x;
	printf("请输入您想要查询的值\n");
	scanf("%d", &x);
	BinTree temp = FindElem(BST,x);
	if (temp == NULL) 
	printf("无此值存在\n");
	else {
		printf("该值存在\n"); 
	}
	system("pause");
	system("cls");
}

void MidOrder_menu(BinTree BST) {
	MidOrder(BST);
	system("pause");
	system("cls");
}

码农公寓

数据结构

函数声明

插入元素

删除元素

返回最小元素的结点

返回最大元素的结点

按值查找

中序遍历

源代码

相关文章