二叉排序树的创建，插入及删除 - C语言

待我称王封你为后i 2022-12-20 02:26 129阅读 0赞

这里的二叉排序树的创建是根据课本上写的，其中掺杂了递归思想，之前的写的二叉树的创建是为非递归的方法[https://blog.csdn.net/qq\_43402544/article/details/109228383][https_blog.csdn.net_qq_43402544_article_details_109228383]。  
完整代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct//关键字结构体 
    { 
    	int key;//关键字项 
    	int otherinfo;//其他数据域 
    }ElemType;//每个节点的数据域的类型 
    typedef struct BSTNode//二叉树结构体 
    { 
    	ElemType data;//每个节点的数据域包括关键字项和其他数据项 
    	struct BSTNode *lchild,*rchild;//左右孩子指针 
    }BSTNode,*BSTree;
    
    void InitTree(BSTree &T)//初始化二叉排序树 
    { 
    	T = (BSTNode*)malloc(sizeof(BSTNode));//创建一个头结点 
    	T->data.key = NULL;
    	T->lchild = T->rchild = NULL;//头结点指针域和数据域都NULL 
    }
    
    void InsertTree(BSTree &T,int e)//二叉排序树的插入 
    { 
    	if(!T)//找到插入位置，递归结束 
    	{ 
    		BSTree S;
    		S = (BSTNode *)malloc(sizeof(BSTNode));//创建一个结点
    		S->data.key = e;//新结点的数据置为e 
    		S->lchild = S->rchild = NULL;//新结点设置为叶子结点 
    		T = S;//把新结点S接到已找到的插入位置 
    	}
    	else if(e<T->data.key)
    		InsertTree(T->lchild,e);//将S插入左子树 
    	else
    		InsertTree(T->rchild,e);//将S插入右子树 
    } 
    
    void CreateTree(BSTree &T)//创建二叉排序树 
    { 
    	int a;
    	printf("请输入：");
    	scanf("%d",&a);
    	T->data.key = a;//将数据填入二叉排序树的根结点 
    	while(1)//利用循环进行插入操作 
    	{ 
    		scanf("%d",&a);
    		InsertTree(T,a);//将数据导入到二叉排序树T中 
    		if(getchar()=='\n')//死循环结束条件 
    			break;
    	}
    }
    
    void InOrderTraverse(BSTree T)//遍历二叉树，中序遍历 
    { 
    	if(T)//递归终止条件是T为NULL 
    	{ 
    		InOrderTraverse(T->lchild);//中序遍历左子树 
    		printf("%d ",T->data);//输出打印根结点 
    		InOrderTraverse(T->rchild);//中序遍历右子树 
    	}
    }
    
    int SearchTree(BSTree T,int key)//二叉排序树的查找，这里的查找只能知道二叉树中有没有和key相等的值 
    { 
    	if(T == NULL)//查找结束，且没有和key相等的值 
    		return 0;
    	else if(T->data.key==key)//查找结束，二叉树中有和key相等的值 
    		return T->data.key;	
    	else if(key<T->data.key)
    		return SearchTree(T->lchild,key);//递归左子树 
    	else
    		return SearchTree(T->rchild,key);//递归右子树 
    }
    
    void DeleteTree(BSTree &T,int key)//从二叉排序树T中删除关键字等于key的结点 ,这里分三种情况进行讨论 
    { 
    	BSTree f,p;
    	p = T;
    	f = NULL;//初始化 
    	while(p)//利用循环找到关键字等于key的结点
    	{ 
    		if(p->data.key == key)//找到关键字等于key的结点，并跳出循环 
    			break;
    		f = p;//结点f一直为结点p的双亲结点 
    		if(p->data.key>key)
    			p = p->lchild;//在p的左子树中继续查找 
    		else
    			p = p->rchild;//在p的右子树中继续查找 
    	}
    	if(p == NULL)//找不到被删除的结点则返回 
    	{ 
    		printf("没有找到要删除的值！\n");
    		return ; 
    	}
    	/*第一种情况：被删除的结点（包含被删除的结点是根结点）的左右子树都存在，在其左子树上找中序最后一个结点填补*/ 
    	BSTree q,s;
    	if((p->lchild)&&(p->rchild))//被删结点p左右子树均不空 
    	{ 
    		q = p;
    		s = p->rchild;
    		while(s->rchild)//在结点p的左子树中继续查找其前驱结点,即最右下结点 
    		{ 
    			q = s;
    			s = s->rchild;//向右到尽头 
    		}
    		p->data = s->data;//结点s中的数据顶替被删结点p中的 
    		if(q != p)//重新连接结点q的右子树 
    			q->rchild = s->lchild;
    		else//重新连接结点q的左子树 
    			q->lchild = s->lchild;
    		free(s);//释放s 
    		return ;//结束该函数 
    	}
    	/*第二种情况：被删结点(包含根结点)缺右子树，且包含左右子树都缺（即叶子结点）；缺右子树用左孩子填补*/
    	else if(p->rchild == NULL)//被删结点缺右子树 
    	{ 
    		if(f)//判断被删结点是否为根结点，若是则f==NULL 
    		{ 
    			if(f->lchild == p)//判断被删结点的双亲结点的左孩子是否为p 
    			{ 
    				f->lchild = p->lchild;
    				p->lchild = NULL;
    			}
    			else//被删结点的双亲结点的右孩子为p 
    			{ 
    				f->rchild = p->lchild;
    				p->lchild = NULL;
    			}
    			free(p);//释放结点p 
    			return ;//结束该函数 
    		}
    		else//被删结点为根结点 
    		{ 
    			f = p;
    			p = p->lchild;
    			f->lchild = NULL;
    			free(f);//释放根结点 
    			T = p;//根结点移位 
    			return ;
    		}
    	}
    	/*第三种情况：被删结点(包含根结点)缺左子树，且包含左右子树都缺（即叶子结点）；缺左子树用右孩子填补*/
    	else	// else if(p->lchild == NULL)//被删结点缺左子树 
    	{ 
    		if(f)//判断被删结点是否为根结点，若是则f==NULL 
    		{ 
    			if(f->lchild == p)//判断被删结点的双亲结点的左孩子是否为p 
    			{ 
    				f->lchild = p->rchild;
    				p->rchild = NULL;
    			}
    			else//被删结点的双亲结点的右孩子为p 
    			{ 
    				f->rchild = p->rchild;
    				p->rchild = NULL;
    			}
    			free(p);//释放结点p
    			return ;//结束该函数 
    		}
    		else//被删结点为根结点 
    		{ 
    			f = p;
    			p = p->rchild;
    			f->lchild = NULL;
    			free(f);//释放根结点 
    			T = p;//根结点移位 
    			return ;//结束该函数 
    		}
    	}
    }
    
    int main()
    { 
    	BSTree T;
    	InitTree(T);//初始化二叉排序树 
    	CreateTree(T);//创建二叉排序树 
    	InOrderTraverse(T);//打印 
    	printf("\n");
    	if(SearchTree(T,16))//判断二叉排序树中是否存在关键字与key相等的结点 ，其中的16是测试值，可换变量 
    		printf("存在：%d\n",SearchTree(T,16));
    	else
    		printf("不存在！\n"); 
    	DeleteTree(T,16);//二叉排序树的删除，删除与key相等的结点，其中的数值为测试值 
    	printf("删除之后："); 
    	InOrderTraverse(T);//再次打印结果，验证删除是否成功 
    	free(T);
    	return 0;
    }

结果演示：  
![在这里插入图片描述][2020110922122285.png_pic_center]

[https_blog.csdn.net_qq_43402544_article_details_109228383]: https://blog.csdn.net/qq_43402544/article/details/109228383
[2020110922122285.png_pic_center]: /images/20221120/7f56c9b73a4c459683fdbf251cc77d40.png