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"); }