二叉搜索树(C语言实现)
2021/4/30 18:26:57
本文主要是介绍二叉搜索树(C语言实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数据结构
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"); }
这篇关于二叉搜索树(C语言实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享