shujujiegou3.cpp

本源码是关于数据结构的操作的源码

#include<iostream.h>
template<class Type> class bst;
template<class Type>class bstnode
{
	friend class bst<Type>;
	public:
		bstnode():leftchild(NULL),rightchild(NULL){}
		bstnode(Type d):data(d),leftchild(NULL),rightchild(NULL){}
	private:
		Type data;
		bstnode<Type> *leftchild,*rightchild;
};
template<class Type>class bst
{
	public:
		bst():root(NULL){}
		bst(Type value);
		bstnode<Type> *getroot(){return root;}
		bstnode<Type> *min(bstnode<Type> *ptr);
		void insert(Type &x,bstnode<Type> * & ptr);
        bstnode<Type> *find(const Type &x,bstnode<Type> * ptr)const;
		void inorder(bstnode<Type> * p);
		void remove(Type &x,bstnode<Type> * & ptr);
		void fun();
		bstnode<Type> *root;
	private:
		Type refvalue;
}; 
template<class Type>bst<Type>::bst(Type value)
{
	Type x;
	root=NULL;
	refvalue=value;
	cout<<"请输入数:";
	cin>>x;
	while(x!=refvalue)
	{
		insert(x,root);
		cout<<"请输入数:";
		cin>>x;
	}
	cout<<"所构建的二叉搜索树为:";
	inorder(root);
	cout<<endl;
}
template<class Type>bstnode<Type>* bst<Type>::find(const Type &x,bstnode<Type> * ptr)const
{
	if(ptr==NULL)return NULL;
	else if(x<ptr->data)return find(x,ptr->leftchild);
	else if(x>ptr->data)return find(x,ptr->rightchild);
	else return ptr;
}
template<class Type>void bst<Type>::insert(Type &x,bstnode<Type>* & ptr)
{
	if(ptr==NULL)
	{
		ptr=new bstnode<Type>(x);
		if(ptr==NULL)
		{
			cout<<"内存分配失败!"<<endl;
			return;
		}
	}
else if(x<ptr->data) insert(x,ptr->leftchild);
else if(x>ptr->data) insert(x,ptr->rightchild);
}
template<class Type> void bst<Type>::inorder(bstnode<Type> *p)
{
	if(p!=NULL)
	{
		inorder(p->leftchild);
		cout<<p->data<<"  ";
		inorder(p->rightchild);
	}	
}
template<class Type>void bst<Type>::remove(Type &x,bstnode<Type> * & ptr)
{
	bstnode<Type> *temp;
	if(ptr!=NULL)
		if(x<ptr->data) remove(x,ptr->leftchild);
		else if(x>ptr->data) remove(x,ptr->rightchild);
		else if(ptr->leftchild!=NULL&&ptr->rightchild!=NULL)
		{
			temp=min(ptr->rightchild);		
			ptr->data=temp->data;
			remove(ptr->data,ptr->rightchild);
		}
		else{
			temp=ptr;
			if(ptr->leftchild==NULL)
				ptr=ptr->rightchild;
			else if(ptr->rightchild==NULL)
				ptr=ptr->leftchild;
			delete temp;
		}	
}
template<class Type>bstnode<Type> *bst<Type>::min(bstnode<Type> * p)
{
	bstnode<Type> *q=p;
	while(q->leftchild!=NULL&&q!=NULL)
		q=q->leftchild;
	return q;
}
template<class Type>void bst<Type>::fun()
{
	Type x;int t; 
	do
	{
		cout<<"请选择操作: 1(查找) 2(删除) 3(插入) 4(输出) 5(退出)";
		cin>>t;
		if(t==1)
		{
			cout<<"请输入你要查找的数据：";
			cin>>x;
			if(find(x,root)==NULL)cout<<"查找失败！";
			else cout<<"查找成功！\n";
		   
		}
		else if(t==2)
		{
			cout<<"请输入你要删除的数据：";
			cin>>x;
			remove(x,root);
		}
		else if(t==3)
		{
			cout<<"请输入你要插入的数据：";
			cin>>x;
			insert(x,root);
		}
		else if(t==4){inorder(root);cout<<endl;}
		else break;
		}while(t!=5);
}
void main()
{
    char ch;
	cout<<"请选择二叉搜索树结点数据类型:i(int) c(char) f(float): ";
	cin>>ch;
	switch(ch)
	{
	    case 'c':
			{
				char value;
				cout<<"请输入该类型空结点作为输入结束: ";
				cin>>value;
				bst<char> tree(value);
				tree.fun();
				break;
			}
		case 'i':
			{
				int value;
				cout<<"请输入该类型空结点作为输入结束: ";
				cin>>value;
				bst<int> tree(value);
				tree.fun();
				break;
			}
			case 'f':
			{
				float value;
				cout<<"请输入该类型空结点作为输入结束: ";
				cin>>value;
			    bst<float> tree(value);
				tree.fun();
				break;
			}
		}

}