[数据结构与算法]408计算机考研--数据结构--二叉排序树学习（C语言）

二叉排序树

一、二叉排序树(创建、增删改查)学习

#include<stdio.h>
#include<stdlib.h>

typedef struct BSTNode{
	int key;
	struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
//在二叉排序树插入关键字为k的新结点（递归实现），时间复杂度：O(h)-O(n)之间 
int BST_Insert(BSTree &T,int k){
	if(T==NULL){//原树为空，则新插入的结点为根结点 
		T=(BSTree)malloc(sizeof(BSTNode));
		T->key=k;
		T->lchild=T->rchild=NULL;
		return 1;//返回1，插入成功 
	}else if(k==T->key){//树中存在相同的关键字的结点，则插入失败 
		return 0;
	}else if(k<T->key){//插入到T的左子树 
		return BST_Insert(T->lchild,k);
	}else{//插入到T的右子树 
		return BST_Insert(T->rchild,k);
	}
} 
//按照str[] 数组中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T,int str[],int n){
	T=NULL;//初始时T为空树
	int i=0;
	while(i<n){//依次将每个关键字插入到二叉排序树 
		BST_Insert(T,str[i]);
		i++;
	}  
} 
//非递归查找算法1：查找对应结点 
BSTNode *BST_Search1(BSTree T,int key){
	while(T!=NULL&&T->key!=key){//若树空或等于根节点值，则结束查找 
		if(key<T->key){
			T=T->lchild;//小于，在左子树查找 
		}else{
			T=T->rchild;//大于，则在右子树上查找 
		}
	}
	return T;
} 
//非递归查找算法2：查找对应结点的父结点 
BSTNode *BST_Search2(BSTree T,int key){
	while(T!=NULL){//若树空或等于根节点值，则结束查找 
		if(T->lchild!=NULL&&T->lchild->key==key){
			return T;
		}
		if(T->rchild!=NULL&&T->rchild->key==key){
			return T;
		}
		if(key<T->key){
			T=T->lchild;//小于，在左子树查找 
		}else{
			T=T->rchild;//大于，则在右子树上查找 
		}
	}
	return T;
} 
//非递归查找算法3：查找右子树最小结点删除，并将其key返回 
int BST_Search_Del_min(BSTree &T){
	BSTree temp=T;//辅助指针 
	while(temp->lchild!=NULL){//查找到右子树最左结点为止(最小结点) 
		temp=temp->lchild; 
	}
	//删除该结点
	BST_Delete(T,temp->key); 
	return temp->key;
} 
//递归查找算法 
BSTNode *BSTSearch(BSTree T,int key){
	if(T==NULL||T->key==key){
		return T;
	}else if(key<T->key){
		T=BSTSearch(T->lchild,key);
	}else{
		T=BSTSearch(T->rchild,key);
	}
	return T;
} 
//删除结点
bool BST_Delete(BSTree &T,int key){
	BSTree cur=BST_Search1(T,key);//查找当前结点
	BSTree parent=BST_Search2(T,key);//查找当前结点的父结点 
	if(cur==NULL){//没找到该节点 
		return false;
	}else if(cur->lchild==NULL&&cur->rchild==NULL){//叶子结点 
		if(parent==NULL){//该结点为根节点  
			//不做操作，反正最后这个结点要free 
		}else if(parent->lchild!=NULL&&parent->lchild->key=key){//该结点为左子结点 
			parent->lchild=NULL; 
		}else{//该结点为右子结点 
			parent->rchild=NULL; 
		}
		free(cur);
	}else if(cur->rchild==NULL){//只有右子树 
		if(parent==NULL){//该结点为根节点 
			cur=cur->rchild; 
		}else if(parent->lchild!=NULL&&parent->lchild->key=key){//该结点为左子结点 
			parent->lchild=cur->rchild; 
			free(cur);
		}else{//该结点为右子结点 
			parent->rchild=cur->rchild; 
			free(cur);
		}
	}else if(cur->lchild==NULL){//只有左子树 
		if(parent==NULL){//该结点为根节点 
			cur=cur->lchild; 
		}else if(parent->lchild!=NULL&&parent->lchild->key=key){//该结点为左子结点 
			parent->lchild=cur->lchild; 
			free(cur);
		}else{//该结点为右子结点 
			parent->rchild=cur->lchild; 
			free(cur);
		}
	}else{//左右子树都有：查找左子树最大或右子树最小结点，现采用后者，先将删除右子树最小结点，再将原结点填充
		 int min=BST_Search_Del_min(cur->rchild); 
		 cur->key=min;//替换值 
	} 
	return true; 
} 

int main(){
	BSTree t1=(BSTree)malloc(sizeof(BSTNode));
	BSTree t2=(BSTree)malloc(sizeof(BSTNode));
	BSTree t3=(BSTree)malloc(sizeof(BSTNode));
	BSTree t4=(BSTree)malloc(sizeof(BSTNode));
	BSTree t5=(BSTree)malloc(sizeof(BSTNode));
	
	t1->key=2;t1->lchild=t2;t1->rchild=t3;
	t2->key=1;t2->lchild=NULL;t2->rchild=NULL;
	t3->key=4;t3->lchild=t4;t3->rchild=t5;
	t4->key=3;t4->lchild=NULL;t4->rchild=NULL;
	t5->key=5;t5->lchild=NULL;t5->rchild=NULL;
	
	//非递归查找算法测试
	printf("非递归查找算法1结果：%d\n",BST_Search1(t1,3)->key);
	printf("递归查找算法结果：%d\n",BSTSearch(t1,3)->key);
	printf("非递归查找算法2结果：%d\n",BST_Search2(t1,3)->key);
}