数据结构（二叉树查找）——二叉排序树的构造和查找、插入、删除

待我称王封你为后i 2022-12-24 11:51 171阅读 0赞

设计一个读入一串整数，然后构造二叉排序树，进行查找、插入、删除。

#include <stdio.h>
    #include <stdlib.h>
    #define TRUE 1
    #define FALSE 0
    #define ENDKEY 0
    
    typedef int KeyType;
    
    typedef struct  node
    {
        
    	KeyType  key ; /*关键字的值*/
    	struct node  *lchild,*rchild;/*左右指针*/
    }BSTNode, *BSTree;
    
    int InsertBST(BSTree *bst, KeyType key)
    /*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/
    {
         
    	BSTree s;
    	if(*bst==NULL)
    	{
        
    		s=(BSTree)malloc(sizeof(BSTNode));
    		s->key=key;
    		s->lchild=NULL;
    		s->rchild=NULL;
    		*bst=s;
    	}
    	else if(key<(*bst)->key)
           InsertBST(&((*bst)->lchild),key);
    	else if(key>(*bst)->key)
    		InsertBST(&((*bst)->rchild),key);
    	return 0;
    		//请完成本函数的功能
    }
    
    void  CreateBST(BSTree  *bst)
    /*从键盘输入元素的值，创建相应的二叉排序树*/
    {
         
    	KeyType key;
    	*bst=NULL;
        scanf("%d",&key);
    	while(key!=ENDKEY)
    	{
        
    		InsertBST(bst,key);
    		scanf("%d",&key);
    	}
    	//请完成本函数的功能
    }
    
    void  InOrder(BSTree bst)  
    /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/
    {
        
    	if (bst!=NULL)
    	{
        
    		InOrder(bst ->lchild);   /*中序遍历左子树*/
    		printf("%d->",bst->key);        /*访问根结点*/
    		InOrder(bst ->rchild);   /*中序遍历右子树*/
    	}
    }
    
    BSTree  SearchBST(BSTree bst, KeyType key)
    /*在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回指向该元素结点指针，否则返回空指针*/
    {
         
    	if(!bst)
    	return NULL;
    	else if(bst->key==key) 
    		return bst;
    	else if(bst->key>key)
    		return SearchBST(bst->lchild,key);
    	else
    		return SearchBST(bst->rchild,key);
    	//请完成本函数的功能
    }
    int DelBST(BSTree t, KeyType  k) /*在二叉排序树t中删去关键字为k的结点*/
    {
        
    	BSTNode  *p, *f,*s ,*q;
    	p=t; 
    	f=NULL;
    	while(p)  /*查找关键字为k的待删结点p*/
    	{
         
    		if(p->key==k )  break;  /*找到则跳出循环*/
    		f=p;   /*f指向p结点的双亲结点*/
    		if(p->key>k)  
    			p=p->lchild;
    		else 
    			p=p->rchild;
    	} 
    	if(p==NULL)  return 0;  /*若找不到，返回原来的二叉排序树*/
    	if(p->lchild==NULL)  /*p无左子树*/
    	{
         
    		if(f==NULL) 
    			t=p->rchild;  /*p是原二叉排序树的根*/
    		else 
    			if(f->lchild==p)  /*p是f的左孩子*/
    				f->lchild=p->rchild ;  /*将p的右子树链到f的左链上*/
    			else  /*p是f的右孩子*/
    				f->rchild=p->rchild ;  /*将p的右子树链到f的右链上*/
    			free(p);  /*释放被删除的结点p*/
    	}
    	else  /*p有左子树*/
    	{
         
    		q=p; 
    		s=p->lchild;
    		while(s->rchild)  /*在p的左子树中查找最右下结点*/
    		{
        
    			q=s; 
    			s=s->rchild;
    		}
    		if(q==p) 
    			q->lchild=s->lchild ;  /*将s的左子树链到q上*/
    		else 
    			q->rchild=s->lchild;
    		p->key=s->key;  /*将s的值赋给p*/
    		free(s);
    	}
    	return 1;
    }  /*DelBST*/
    
    void main()
    {
        
    	BSTree T,p;
    	int keyword,temp;
    	char ch,j='y';
    	T=NULL;
    	while(j!='n')
        {
        
    		printf("1.创建二叉排序树\n");
    		printf("2.显示排序的数据\n");
    		printf("3.查找数据\n");
    		printf("4.在查找树中插入一个数据\n");
    		printf("5.在查找树中删除一个数据\n");
    		printf("6.程序结束，退出\n");
    		scanf(" %c",&ch); //输入操作选项
    		switch(ch)
    		{
        
    		case '1':
    			printf("请输入数据，以0作为数据输入结束。\n");
    			CreateBST(&T);
    			break;
    		case '2':
    			if(!T) printf("二叉排序树中没有数据。\n");
    			else {
        InOrder(T);printf("\b\b  \n");}
    			break;
           case '3':
    			printf("输入待查找的数据值:\n");
    			scanf("%d",&keyword); //输入要查找元素的关键字
    			p=SearchBST(T, keyword);
    			if(!p) printf("%d 没有找到。\n",keyword); //没有找到
    			else printf("%d 查找成功。\n",keyword); //成功找到
    			break;
           case '4':
    			printf("输入待插入的数据:");
    			scanf("%d",&keyword); //输入要插入元素的关键字
    			temp=InsertBST(&T, keyword);
    			if(temp==FALSE)
    				printf("%d 已在二叉树中!\n",keyword); //该元素已经存在
    			else
    				printf("%d 插入成功！\n",keyword);
    			break;
           case '5':
    			printf("输入待删除的数据:");
    			scanf("%d",&keyword); //输入要删除元素的关键字
    			temp=DelBST(T, keyword);
    			if(temp==FALSE) printf("%d 不存在!\n",keyword); //该元素不存在
    			else printf("成功删除%d\n",keyword); //成功删除
    			break;
           default: 
    			j='n';
    		}
     }
     printf("程序结束!\nPress any key to shut off the window!\n");
     getchar();
     getchar();
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFfNw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFfNw_size_16_color_FFFFFF_t_70]: /images/20221120/f44779a412854ae0ac7a82b6dd992ad2.png