实验10--查找

#include
#include
#include
#include
#include
#define OK 1
#define ERROR 0
using namespace std;
typedef int Status;
//typedef float KeyType;
typedef int KeyType;
typedef char InfoType;
//typedef char *KeyType;//字符串
typedef struct{
	KeyType key;
	InfoType data;
}*SElemType,SNode;
typedef struct BSTNode{
	int data;
	BSTNode* lchild;
	BSTNode* rchild;
}BSTNode,*BSTree;
int SearchSeq(SElemType &K,KeyType key,int len);
int BinarySearch(SElemType &K,KeyType key,int len);
void InOderTraverse(BSTree bst);
BSTNode* BuyNode(int data);
Status Insert(BSTree *bst, int key);
BSTNode* FindParent(BSTree bst, BSTNode *child);
void Delete(BSTree *bst, int key);
Status Search(BSTree bst, int key, BSTree f, BSTree *p);
BSTNode* SearchBST(BSTNode* bst,int key);
int main(){
	SElemType K;
	int num;
	BSTNode *root=NULL;
	cout<<"********************************************"<>s;
	switch(s){
		case 1:{
			cout<<"请输入关键字个数:";
			cin>>num;
			K=(SElemType)malloc((num+1)*sizeof(SNode));
				cout<<"请输入关键字及信息(例如1 a 2 b):";
			for(int i=1;i<=num;i++){
				cin>>(K+i)->key>>(K+i)->data;
			}
			cout<<"请输入要顺序查找的关键字:";
			int key;
			cin>>key;
			SearchSeq(K,key,num);
			break;
			}
		case 2:{
			cout<<"请输入关键字个数:";
			cin>>num;
			K=(SElemType)malloc((num+1)*sizeof(SNode));
				cout<<"请输入关键字及信息(例如1 a 2 b):";
			for(int i=1;i<=num;i++){
				cin>>(K+i)->key>>(K+i)->data;
			}
			cout<<"请输入要折半查找的关键字:";
			int key;
			cin>>key;
			BinarySearch(K,key,num);
			break;
			}
		case 3:{
			cout<<"请输入要插入关键字的个数:";
			cin>>num;
			int a[num];
			cout<<"请输入关键字信息:";
			for(int i=0;i>a[i];
				Insert(&root,a[i]);
			}
			cout<<"插入成功"<>key;
			Delete(&root,key);
			cout<<"删除成功"<>key;
			BSTNode *p=SearchBST(root,key);
			if(p==NULL)cout<<"查找失败";
			else cout<<"查找成功";
			break;
		}
		case 6:{
			cout<<"二叉树遍历结果:";
			InOderTraverse(root);
			break;
		}
		default:{
			
			exit(0);
		}
		}
	}

	
} 
int SearchSeq(SElemType &K,KeyType key,int len){
	K->key=key;
	for(int i=1;i<=len;i++){
		if((K+i)->key==key){
			cout<<"关键字信息:";
			cout<<(K+i)->data;
			return i;
		}
	}
	return 0;
}
int BinarySearch(SElemType &K,KeyType key,int len){
	int low,high,mid;
	low=1;
	high=len;
	while(low<=high){
		mid=(low+high)/2;
		if((K+mid)->key==key){
			cout<<"关键字信息:";
			cout<<(K+mid)->data;
			return mid;
		}else if((K+mid)->key>key){
			high=mid-1;
		}else if((K+mid)->keylchild);
		printf("%d ", bst->data);
		InOderTraverse(bst->rchild);
	}
}
 
BSTNode* BuyNode(int data){
	BSTNode *pTmp=(BSTNode*)malloc(sizeof(BSTNode));
	if(pTmp==NULL){
		exit(0);
	}
	pTmp->data=data;
	pTmp->lchild=NULL;
	pTmp->rchild=NULL;
	return pTmp;
}
 
Status Insert(BSTree *bst, int key){
	if(*bst==NULL){
		*bst=BuyNode(key); 
		return OK;
	}
	BSTNode *p;
	if(!Search(*bst,key,NULL,&p)){
		BSTNode *pNew=BuyNode(key);
		if(keydata){
			p->lchild=pNew;
		}else if(key>p->data){
			p->rchild=pNew;
		}
		return OK; 
	}
	return ERROR;
}
 
BSTNode* FindParent(BSTree bst, BSTNode *child){
	if(bst==NULL){
		return NULL;
	}
 
	if(bst->lchild==child||bst->rchild==child){
		return bst;
	}else if(bst->lchild!=NULL){
		FindParent(bst->lchild,child);
	}else if(NULL != bst->rchild){
		FindParent(bst->rchild,child);
	}
}
 
void Delete(BSTree *bst, int key){
	if (*bst==NULL){
		exit(1); 
	}
	BSTNode *p;
	BSTNode *f=NULL;
	BSTNode *q,*s;
	if(Search(*bst, key, NULL, &p)){
 		if (NULL == p->lchild && NULL != p->rchild){
			q=p->rchild;
			p->data=q->data;    
			p->rchild=q->rchild;
			p->lchild=q->lchild;
			free(q);
		}else if(p->rchild==NULL&&p->lchild!=NULL){
			q=p->lchild;
			p->data=q->data;
			p->rchild=q->rchild;
			p->lchild=q->lchild;
			free(q);
		}
		else if(NULL != p->rchild && NULL != p->lchild){
			q=p;
			s=p->lchild;
			while (s->rchild){
				q=s;
				s=s->rchild;
			}
			p->data=s->data;
			if(q!=p){
				q->rchild=s->lchild;
			}else{
				q->lchild=s->lchild;
			}
			free(s);
		}else{
			if(*bst==p){
				free(*bst);
				*bst = NULL;
				return;
			}
 		BSTNode* parent = FindParent(*bst, p);
			if(parent->lchild==p){
				parent->lchild=NULL;
			}else{
				parent->rchild=NULL;
			}
			free(p);
		}
	}
}
 
Status Search(BSTree bst, int key, BSTree f, BSTree *p){
	if (!bst){
		*p=f;
		return ERROR;
	}
	if(bst->data==key){
		*p=bst;
		return OK;
	}else if(bst->datarchild,key,bst,p);
	}
	return Search(bst->lchild,key,bst,p);
}
BSTNode* SearchBST(BSTNode* bst,int key){
	if(!bst||bst->data==key)return bst;
	else if(keydata)return (SearchBST(bst->lchild,key));
	else return (SearchBST(bst->rchild,key));
}