202933.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;
}

//创建函数从大到小输出二叉排序树T中所有不小于x的元素=================================================
void PrintBT(BiTree T,int x)
{
	if(T->rchild) PrintBT(T->rchild,x);
	if(T->data.key<x) return; 
	cout<<"  "<<T->data.key;
	if(T->lchild) PrintBT(T->lchild,x); 
}
//主函数=============================================================================================
void  main()
{
	BiTree T;
	CreateBST(T,"933.txt");
	cout<<"此二叉树是:"<<endl;
	preorderlists(T,visit);
	cout<<endl;

	cout<<"从大到小输出不小于指定元素的关键字的数据元素:";
	PrintBT(T,5);
	cout<<endl;
}