随机产生一组关键字，利用二叉排序树的插入算法建立二叉排序树，然后删除某一指定关键字元素。
目录
1、二叉排序树的结构
2、插入结点
3、查找结点
4、创建二叉树
5、删除结点
6、完整测试源码
1、二叉排序树的结构
就是一般二叉树的结构。
//二叉排序树
typedef struct BST {
int data; //值域
struct BST* left; //左孩子
struct BST* right; //右孩子
}*BST;
2、插入结点
递归方式，找到要插入值的位置，然后进行插入。
//插入结点
void InsertBSTree(BST* root, int k) {//root是一个二级指针，是二叉树根节点的地址，k是要插入的值
if (!(*root)) {//当节点为空值时，这就是要插入的位置
BST p = (BST)malloc(sizeof(struct BST));
p->data = k;
p->left = p->right = NULL;
*root = p;
}
else if ((*root)->data >= k)//当前结点值大于要插入的值，那就进入左子树
InsertBSTree(&(*root)->left, k);
else //当前结点值小于要插入的值，那就进入右子树
InsertBSTree(&(*root)->right, k);
}
3、查找结点
还是用递归，一直比较结点值与要查找的值。
//查找结点
bool FindBSTree(BST root, int k) {
//找到了返回真，没找到返回假
if (!root)
return false;//空树返回假
if (root->data == k)
return true;//找到了返回真
if (root->data >= k)
return FindBSTree(root->left, k);//去左子树里面找
if (root->data < k)
return FindBSTree(root->right, k);//去右子树里面找
}
4、创建二叉树
用随机数函数生成随机数，把生成的随机数当成关键字次次调用插入函数，完成树的创建。
因为rand函数每一次产生的随机数是相同的，所以要用srand函数设置一个随机数种子，保证每一次运行程序生成的随机数不是一样的，所以我们一般用系统时间作随机数种子，因为时间一直在改变；
因为srand取得是系统时间，并且是以秒为单位，但是for循环一次远远小于1秒，这样就会导致种子没有变化，产生的随机数也不会有变化，所以要让两次rand函数之间间隔1秒以上，所以用以恶搞sleep函数。
//创建二叉树
//循环调用插入函数来完成创建
void CreateBSTree(BST* root,int num) {
int a;//a是随机数作结点值
for (int i = 0; i < num; i++) {
srand((unsigned)time(0));//随机数种子
a = rand() % 100;//0到100范围内的随机数
Sleep(1000);//停留1s
if ((*root)&&FindBSTree(*root, a))
//不为空树并且树里面没有该值,如果树里有这个值就会执行continue语句从而重新生成一个数字
continue;
//因为srand((unsigned)time(NULL));取的是系统时间，也就是距离1970.1.1午夜有多少秒。而for循环一次远远小于1s，所以随机值种子不会变化，所以加一个sleep间隔一秒
//调用插入函数
InsertBSTree(root, a);
}
}
5、删除结点
删除结点有四种情况：
- 要删除的结点是叶子结点：直接删除该结点
- 要删除的结点只有左孩子：左孩子顶替该结点
- 要删除的结点只有右孩子：有孩子顶替该节点
- 要删除的结点有两个孩子：左子树最右的结点或右子树最左的结点顶替该节点，也就是在中序遍历下找该节点的直接前驱或者直接后继去顶替他。
中序遍历下的二叉排序树是有序的。
//删除结点
//先用函数判断要删除结点的位置
bool DeleteBSTree(BST* root, int k) {
if ((*root) == NULL)//空树或找不到目标值
return false;
if ((*root)->data == k)//找到目标值
return Delete(root);
if ((*root)->data > k)//当前结点值大于目标值，进入左子树找
return DeleteBSTree(&(*root)->left, k);
if ((*root)->data < k)//当前结点值小于目标值，进入右子树找
return DeleteBSTree(&(*root)->right, k);
}
//删除的核心 *** 作
bool Delete(BST* root) {
BST pre, s;//pre作目标节点的前一个,s作要删除的结点
//1、右子树为空或叶子节点
if ((*root)->right == NULL) {
pre = *root; //保存好要删除的结点
*root = (*root)->left; //用他的左儿子代替这个位置
free(pre); //再释放掉要删除的结点
}
//2、左子树为空
else if ((*root)->left == NULL) {
pre = *root; //保存好要删除的结点
*root = (*root)->right; //用他的右儿子代替这个位置
free(pre); //再释放掉要删除的结点
}
//3、左右子树均不为空
//用要删除的结点的前驱节点的值来代替要删除的结点的值，然后再把这个前驱节点删除掉就可以了
else {
pre = *root; //保存好要删除的结点
s = (*root)->left; //s是他左子树的根节点
while (s->right) { //循环找到他左子树的最右的结点，也就是找到要删除结点的前驱节点
pre = s; //两个指针依次向下
s = s->right; //
}
//退出循环，s是被删结点的前驱节点，pre是s的前驱节点
(*root)->data = s->data;//这里是赋值，用前驱的值代替被删除的结点的值
if (pre != (*root)) //这里不等于代表着经过了循环，
pre->right = s->left;//因为前面已经把值赋过去了，后面会有删除，又因为s是（*root）的直接前驱说明s没有右儿子，所以这里把s可能有的左儿子连接到pre上
else //这里代表着没有经过循环，也就是说，s直接是（*root）的直接前驱
pre->left = s->left;
free(s); //这里是删除，释放掉这个前驱结点，因为前驱结点的值和儿子都交代完了就可以不要了
}
return true;
}
6、完整测试源码
#define _CRT_SECURE_NO_WARNINGS 1 #include#include #include //二叉排序树 typedef struct BST { int data; struct BST* left; struct BST* right; }*BST; //插入结点 void InsertBSTree(BST* root, int k) { if (!(*root)) {//当节点为空值时 BST p = (BST)malloc(sizeof(struct BST)); p->data = k; p->left = p->right = NULL; *root = p; } else if ((*root)->data >= k)//当前结点值大于要插入的值，那就进入左子树 InsertBSTree(&(*root)->left, k); else //当前结点值小于要插入的值，那就进入右子树 InsertBSTree(&(*root)->right, k); } //查找结点 bool FindBSTree(BST root, int k) { //找到了返回真，没找到返回假 if (!root) return false;//空树返回假 if (root->data == k) return true;//找到了返回真 if (root->data >= k) return FindBSTree(root->left, k);//去左子树里面找 if (root->data < k) return FindBSTree(root->right, k);//去右子树里面找 } //中序遍历打印二叉树 void Inoder(BST root) { if (!root) return; Inoder(root->left); printf("%d ", root->data); Inoder(root->right); } //创建二叉树 //循环调用插入函数来完成创建，如果 void CreateBSTree(BST* root,int num) { int a;//a是随机数作结点值 for (int i = 0; i < num; i++) { srand((unsigned)time(0));//随机数种子 a = rand() % 100; Sleep(1000);//停留1s if ((*root)&&FindBSTree(*root, a))//不为空树并且树里面没有该值,如果树里有这个值就会执行continue语句从而重新生成一个数字 continue; //因为srand((unsigned)time(NULL));取的是系统时间，也就是距离1970.1.1午夜有多少秒。而for循环一次远远小于1s，所以随机值种子不会变化，所以加一个sleep间隔一秒 InsertBSTree(root, a); } } //删除结点 bool Delete(BST* root) { BST pre, s;//pre作目标节点的前一个,s作要删除的结点 //1、右子树为空或叶子节点 if ((*root)->right == NULL) { pre = *root; //保存好要删除的结点 *root = (*root)->left; //用他的左儿子代替这个位置 free(pre); //再释放掉要删除的结点 } //2、左子树为空 else if ((*root)->left == NULL) { pre = *root; //保存好要删除的结点 *root = (*root)->right; //用他的右儿子代替这个位置 free(pre); //再释放掉要删除的结点 } //3、左右子树均不为空 //用要删除的结点的前驱节点的值来代替要删除的结点的值，然后再把这个前驱节点删除掉就可以了 else { pre = *root; //保存好要删除的结点 s = (*root)->left; //s是他左子树的根节点 while (s->right) { //循环找到他左子树的最右的结点，也就是找到要删除结点的前驱节点 pre = s; //两个指针依次向下 s = s->right; // } //退出循环，s是被删结点的前驱节点，pre是s的前驱节点 (*root)->data = s->data;//这里是赋值，用前驱的值代替被删除的结点的值 if (pre != (*root)) //这里不等于代表着经过了循环， pre->right = s->left;//因为前面已经把值赋过去了，后面会有删除，又因为s是（*root）的直接前驱说明s没有右儿子，所以这里把s可能有的左儿子连接到pre上 else //这里代表着没有经过循环，也就是说，s直接是（*root）的直接前驱 pre->left = s->left; free(s); //这里是删除，释放掉这个前驱结点，因为前驱结点的值和儿子都交代完了就可以不要了 } return true; } bool DeleteBSTree(BST* root, int k) { if ((*root) == NULL)//空树或找不到目标值 return false; if ((*root)->data == k)//找到目标值 return Delete(root); if ((*root)->data > k)//当前结点值大于目标值，进入左子树找 return DeleteBSTree(&(*root)->left, k); if ((*root)->data < k)//当前结点值小于目标值，进入右子树找 return DeleteBSTree(&(*root)->right, k); } void menu() { printf("---------n1、插入n"); printf("2、删除n---------n"); } void main() { BST bstree=NULL; int chose; int num;//num作插入值 int num1;//num1作结点个数， printf("输入结点个数"); scanf("%d", &num1); printf("请稍等...n"); CreateBSTree(&bstree,num1); printf("二叉排序树："); Inoder(bstree);//先遍历输出一次 printf("n"); while (1) { menu(); scanf("%d", &chose); switch (chose) { case 1: printf("请输入要插入的值："); scanf("%d", &num); InsertBSTree(&bstree,num); printf("新树："); Inoder(bstree); printf("n"); break; case 2: printf("请输入要删除的值："); scanf("%d", &num); if (DeleteBSTree(&bstree, num)) { printf("新树："); Inoder(bstree); printf("n"); } else printf("没有这个值！n"); break; default:return 0; } } }
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）