c语言实现二叉搜索树的基本功能

淡淡的烟草味﹌ 2022-05-16 09:08 178阅读 0赞

**查找1：**

pTreeNode find(int x,pTreeNode t){
    	if(!t){
    	return NULL;
    	}else if(x>t->data){
    		return find(x,t->right);
    	}else if(x<t->data){
    		return find(x,t->left);
    	}else{
    	return t;
    	}
    }

注意：（1）.当找到直接返回t，找不到继续找（return find(x,t->right);），记得加上return.

**查找2：**

pTreeNode iterFind(int x,pTreeNode t){
    	while(t){
    		if(x>t->data){
    			t=t->right;
    		}else if(x<t->data){
    		t=t->left;
    		}else{
    		return t;
    		}
    	}
    	return NULL;
    }

注意：（1）.通过while循环，t不为空才循环，为空直接返回null，然后通过变化t=t->right实现查找

**递归找最小：**

pTreeNode FindMin(pTreeNode t){
    	if(!t){
    	return NULL;
    	}else if(!t->left){
    	return t;
    	}else{
    		return FindMin(t->left);
    	}
    }

注意：（1）.最小定是在最左边，并且没有左儿子，然后左儿子为空，则返回t就是最小，否则继续寻找（return FindMin(t->left);），记得也要return

**迭代找最大：**

pTreeNode FindMax(pTreeNode t){
    	while(t->right){
    		t=t->right;
    	}
    	return t;
    }

注意：（1）.如果t的右儿子不为空，则不是最大，则变化t（t=t->right），直到为空，则返回t

**插入:**

pTreeNode insert(int x,pTreeNode *t){
    	if(!(*t)){
    		(*t)=(pTreeNode)malloc(sizeof(TreeNode));
    		(*t)->data=x;
    		(*t)->left=NULL;
    		(*t)->right=NULL;
    	}else if(x>(*t)->data){
    		(*t)->right=insert(x,&((*t)->right));
    	}else if(x<(*t)->data){
    		(*t)->left=insert(x,&((*t)->left));
    	}//如果x已存在，什么都不做
    	return (*t);
    }

注意：（1）如果t为空，则申请空间，然后直接存放数据进去，然后返回（\*t）

（2）.如果t不为空，则比较，然后因为都有返回（\*t），所以用(\*t)->right=insert(x,&((\*t)->right));实现连接

（3）.如果x已存在，则直接返回（\*t），什么都不进行操作

pTreeNode Delete(int x,pTreeNode *t){
    	pTreeNode temp;
    	if(!(*t)){
    	printf("要删除的元素不存在!");
    	}else{
    		if(x>(*t)->data){
    			(*t)->right=Delete(x,&((*t)->right));
    		}else if(x<(*t)->data){
    			(*t)->left=Delete(x,&((*t)->left));
    		}else{
    			if((*t)->left&&(*t)->right){
    				temp=FindMin((*t)->right);
    				(*t)->data=temp->data;
    				(*t)->right=Delete((*t)->data,&((*t)->right));
    			}else{
    				temp=(*t);
    				if(!((*t)->right)){
    					(*t)=(*t)->left;
    				}else if(!((*t)->left)){
    					(*t)=(*t)->right;
    				}
    				free(temp);
    			}
    		}
    	}
    	return (*t);
    }

注意：（1）.如果找不到要删除的x，则继续找，找到了，有两种情况，第一种是叶节点（没有儿子）或只有一个节点，此时如果右儿子为空，则返回左儿子，如果是叶节点，则返回的是null，最后只需用（\*t）->left=Delete(x,&((\*t)->left)进行连接就可以了，记得用temp存（\*t），然后free（temp）;

(2).如果左右儿子都存在，则在右子树中找最小，把最小的数据替换上去，最后删除该最小

(3).该函数最后都要返回（\*t），这样才能保证每一步都能进行连接

**完整代码如下:**

#include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    typedef struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    }TreeNode,*pTreeNode;
    
    void create(pTreeNode *t){
    	int ch;
    	scanf_s("%d",&ch);
    	if(ch==-1){
    	*t=NULL;
    	return;
    	}else{
    		*t=(pTreeNode)malloc(sizeof(TreeNode));
    		(*t)->data=ch;
    		printf("请输入比%d小的左节点数据:",ch);
    		create(&((*t)->left));
    		printf("请输入比%d大的右节点数据:",ch);
    		create(&((*t)->right));
    	}
    }
    pTreeNode find(int x,pTreeNode t){
    	if(!t){
    	return NULL;
    	}else if(x>t->data){
    		return find(x,t->right);
    	}else if(x<t->data){
    		return find(x,t->left);
    	}else{
    	return t;
    	}
    }
    pTreeNode iterFind(int x,pTreeNode t){
    	while(t){
    		if(x>t->data){
    			t=t->right;
    		}else if(x<t->data){
    		t=t->left;
    		}else{
    		return t;
    		}
    	}
    	return NULL;
    }
    pTreeNode FindMin(pTreeNode t){
    	if(!t){
    	return NULL;
    	}else if(!t->left){
    	return t;
    	}else{
    		return FindMin(t->left);
    	}
    }
    pTreeNode FindMax(pTreeNode t){
    	while(t->right){
    		t=t->right;
    	}
    	return t;
    }
    
    pTreeNode insert(int x,pTreeNode *t){
    	if(!(*t)){
    		(*t)=(pTreeNode)malloc(sizeof(TreeNode));
    		(*t)->data=x;
    		(*t)->left=NULL;
    		(*t)->right=NULL;
    	}else if(x>(*t)->data){
    		(*t)->right=insert(x,&((*t)->right));
    	}else if(x<(*t)->data){
    		(*t)->left=insert(x,&((*t)->left));
    	}//如果x已存在，什么都不做
    	return (*t);
    }
    
    void MiddleOrderBinaryTree(pTreeNode t){
    	if(!t){
    	return;
    	}else{
    		MiddleOrderBinaryTree(t->left);
    		printf("%d ",t->data);
    		MiddleOrderBinaryTree(t->right);
    	}
    }
    
    pTreeNode Delete(int x,pTreeNode *t){
    	pTreeNode temp;
    	if(!(*t)){
    	printf("要删除的元素不存在!");
    	}else{
    		if(x>(*t)->data){
    			(*t)->right=Delete(x,&((*t)->right));
    		}else if(x<(*t)->data){
    			(*t)->left=Delete(x,&((*t)->left));
    		}else{
    			if((*t)->left&&(*t)->right){
    				temp=FindMin((*t)->right);
    				(*t)->data=temp->data;
    				(*t)->right=Delete((*t)->data,&((*t)->right));
    			}else{
    				temp=(*t);
    				if(!((*t)->right)){
    					(*t)=(*t)->left;
    				}else if(!((*t)->left)){
    					(*t)=(*t)->right;
    				}
    				free(temp);
    			}
    		}
    	}
    	return (*t);
    }
    void main(){
    pTreeNode t;
    printf("请输入第一个节点数据,-1代表无数据:");
    create(&t);
    system("pause");
    MiddleOrderBinaryTree(t);
    system("pause");
    //pTreeNode p=find(5,t);
    //
    //printf("%d----%d",p,(*p).data);
    //system("pause");
    //pTreeNode p1=iterFind(5,t);
    //printf("%d----%d",p,(*p).data);
    //system("pause");
    //
    //pTreeNode min=FindMin(t);
    //printf("min:%d",(*min).data);
    //system("pause");
    //pTreeNode max=FindMax(t);
    //printf("max:%d",(*max).data);
    //system("pause");
    //pTreeNode i=insert(15,&t);
    //printf("%d----%d",i,i->data);
    //system("pause");
    Delete(5,&t);
    MiddleOrderBinaryTree(t);
    system("pause");
    //pTreeNode max=FindMax(t);
    //printf("max:%d",max->data);
    //system("pause");
    
    }