202931.cpp

数据结构（清华版）

#include<iostream.h>
#include<fstream.h>
typedef int KeyType;
//构建结构体==============================================================
struct ElemType
{
	KeyType key;
};

//创建结点结构体===========================================================
typedef struct BiTNode
{
	ElemType data;
	BiTNode *lchild,*rchild;
}*BiTree;
//创建生成二叉树函数========================================================

void CreateBiTree(BiTree &T,int s[],int &i)
{
	i++;
	if(s[i]==0)	T=NULL;
	else
	{
		T=new BiTNode;
		T->data.key=s[i];
		CreateBiTree(T->lchild,s,i);
		CreateBiTree(T->rchild,s,i);
	}
}
//创建重载函数==================================================================
void CreateBiTree(BiTree &T,int s[])
{
	int i=-1;
	CreateBiTree(T,s,i);
}
//创建插入函数==============================================================
void InsertBST(BiTree &T,ElemType x)
{
	if(!T)
	{
		T=new BiTNode;
		T->data=x;
		T->lchild=T->rchild=NULL;
	}
	else if(x.key<T->data.key)
		InsertBST(T->lchild,x);
	else if(x.key>T->data.key)
		InsertBST(T->rchild,x);
}
//创建函数生成二叉排序树=====================================================
void CreateBST(BiTree &T,char fn[])
{
	ElemType x;
	ifstream f;
	f.open(fn);
	T=NULL;
	while(!f.eof())
	{
		f>>x.key;
		InsertBST(T,x);
	}
	f.close();
}
//创建函数查找二叉排序树======================================================
BiTree SearchBST(BiTree T,KeyType key)
{
	if(!T || T->data.key==key)return T;
	else if(key<T->data.key)
		return SearchBST(T->lchild,key);
	else return SearchBST(T->rchild,key);
}
//创建函数删除二叉排序树======================================================
bool DeleteBST(BiTree &T,KeyType key)
{
	BiTree f,p,s;
	f=NULL;
	p=T;
	while(p && p->data.key!=key)
		if(key<p->data.key)
		{
			f=p;
			p=p->lchild;
		}
		else
		{
			f=p;
			p=p->rchild;
		}
	if(!p)	return false;
	if(!p->lchild)
		if(p==T)	T=p->rchild;
		else if(p==f->lchild)
			f->lchild=p->rchild;
		else	f->rchild=p->rchild;
	else
	{
		s=p->lchild;
		while(s->rchild)
			s=s->rchild;
		s->rchild=p->rchild;
		if(p==T)	T=p->lchild;
		else if(p==f->lchild)	f->lchild=p->lchild;
		else f->rchild=p->lchild;
	}
	delete p;
	return true;
}
//创建输出二叉树函数==========================================================
void preorderlists(BiTree T,void visit(ElemType))
{
	if(T)
	{
		visit(T->data);
		if(T->lchild || T->rchild)
		{
			cout<<"(";
			preorderlists(T->lchild,visit);
			cout<<",";
			preorderlists(T->rchild,visit);
			cout<<")";
		}
	}
	else	cout<<"^";
}
//
void visit(ElemType x)
{
	cout<<x.key;
}


//创建函数中序遍历二叉树======================================================

int Is_BSTree(BiTree T,int last,int flag)//判断二叉树T是否二叉排序树,是则返回1,否则返回0
{
	if(T->lchild&&flag) Is_BSTree(T->lchild, last, flag);
	if(T->data.key<last) flag=0; 
	last=T->data.key;
	if(T->rchild&&flag) Is_BSTree(T->rchild,last,flag);
	return flag;
}
//
int Is_BSTree(BiTree T)
{
	int last=0,flag=1;
	return Is_BSTree( T,last,flag);
}
//主函数=====================================================================
void main()
{
	BiTree T;
	CreateBST(T,"931.txt");
	cout<<endl;
	cout<<"此二叉树为:";
	preorderlists(T,visit);
	cout<<endl<<endl;

	if(Is_BSTree(T)==1)	cout<<"   此树是二叉排序树"<<endl;
	else cout<<"   此树不是二叉排序树!!!!"<<endl;

}