数据结构课程设计 二叉排序树的实现

包括代码和课程设计报告。 摘要……………………………………………………………………………………………1 1 引言…………………………………………………………………………………………2 1.1 问题的提出………………………………………………………………………………2 1.2 C语言……………………………………………………………………………………2 1.3 C语言的发展过程………………………………………………………………………2 1.4 任务与分析………………………………………………………………………………2 2设计方案……………………………………………………………………………………3 2.1整体设计方案……………………………………………………………………………3 2.1.1主程序模块设计方案…………………………………………………………………3 2.1.2初始化模块设计方案…………………………………………………………………3 2.1.3中序遍历模块设计方案………………………………………………………………5 2.1.4先序遍历模块设计方案………………………………………………………………5 2.1.5查找并删除元素模块设计方案………………………………………………………6 2.1.6主函数模块设计方案…………………………………………………………………7 3程序演示……………………………………………………………………………………9 总结…………………………………………………………………………………………10 致谢…………………………………………………………………………………………11 参考文献……………………………………………………………………………………12 附录…………………………………………………………………………………………13

#include 
typedef int KeyType;
typedef char ElemType[10];
typedef struct tnode
{	
	KeyType key;
	ElemType data;
	struct tnode *lchild*rchild;
}BSTNode;
BSTNode *BSTSearch（BSTNode *btKeyType k）
{
	BSTNode *p=bt;
	while （p!=NULL && p->key!=k）
	{
		if （kkey）
            p=p->lchild;  /*沿左子树查找*/
		else
            p=p->rchild;  /*沿右子树查找*/
	}
	return（p）;
}
int BSTInsert（BSTNode *&btKeyType k）
{
	BSTNode *f*p=bt;
	while （p!=NULL）
	{
		if （p->key==k）
			return（0）;
		f=p;						/*f指向*p结点的双亲结点*/
		if （p->key>k）
			p=p->lchild;			/*在左子树中查找*/
		else
			p=p->rchild;			/*在右子树中查找*/
	}
	p=new BSTNode;	/*建立新结点*/
	p->key=k;
	p->lchild=p->rchild=NULL;
	if （bt==NULL）					/*原树为空时*p作为根结点插入*/
		bt=p;
	else if （kkey）
		f->lchild=p;				/*插入*p作为*f的左孩子*/
	else
		f->rchild=p;				/*插入*p作为*f的右孩子*/
	return（1）;
}
void CreateBST（BSTNode *&btKeyType str[]int n）
{
	bt=NULL;         			  /*初始时bt为空树*/
	int i=0;
	while （i	{  	
		BSTInsert（btstr[i]）; /*将关键字str[i]插入二叉排序树bt中*/
		i++;
    }
}

int BSTDelete（BSTNode *&btKeyType k）
{
	BSTNode *p=bt*f*r*f1;
	f=NULL;						/*p指向待比较的结点f指向*p的双亲结点*/
	while （p!=NULL && p->key!=k）/*查找值域为x的结点*/
	{	f=p;
	if （p->key>k） 
		p=p->lchild;		/*在左子树中查找*/
	else
		p=p->rchild;		/*在右子树中查找*/
	}
	if （p==NULL）				/*未找到key域为k的结点*/
		return（0）;
	else if （p->lchild==NULL）  /**p为被删结点若它无左子树*/
	{
		if （f==NULL）			/**p是根结点则用右孩子替换它*/
			bt=p->rchild;
		else if （f->lchild==p）	/**p是双亲结点的左孩子则用其右子替换它*/
		{	f->lchild=p->rchild;
		delete p;
		}
		else if（f->rchild==p）	/**p是双亲结点的右孩子则用其右孩子替换它*/
		{	f->rchild=p->rchild;
		delete p;
		}
	}
	else if （p->rchild==NULL）	/**p为被删结点若它无右子树*/
	{
		if （f==NULL）			/**p是根结点则用左孩子替换它*/
			bt=p->lchild;
		if （f->lchild==p）		/**p是双亲结点的左孩子则用其左孩子替换它*/
		{	f->lchild=p->lchild;
		delete p;
		}
		else if（f->rchild==p）	/**p是双亲结点的右孩子则用其左孩子替换它*/
		{	f->rchild=p->lchild;
		delete p;
		}
	}
	else						/**p为被删结点若它有左子树和右子树*/
	{
		f1=p;r=p->lchild;		/*查找*p的左子树中的最右下结点*r*/
		while （r->rchild!=NULL）	/**r一定是无右子树的结点*f1作为r的双亲*/
		{	f1=r;
		r=r->rchild;
		}
		if （f1->lchild==r）		/**r是*f1的左孩子删除*r*/
			f1->lchild=r->rchild;
		else if （f1->rchild==r）	/**r是*f1的右孩子删除*r*/
			f1->rchild=r->lchild;
		r->lchild=p->lchild;	/*以下语句是用*r替代*p*/
		r->rchild=p->rchild;    
		if （f==NULL）			/**f为根结点*/
			bt=r;				/*被删结点是根结点*/
		else if （f->lchild==p）	/**p是*f的左孩子*/
			f->lchild=r;
		else					/**p是*f的右孩子*/
			f->rchild=r;
		delete p;
	}
	return（1）;
}
//先序遍历
void preorder（BSTNode  *t）
{ 
	if（t!=0）
	{ 
		cout<key<<“ “;
		preorder（t->lchild）;
		preorder（t->rchild）;
	}
}
//中序遍历
void inorder（BSTNode  *t）
{ 
	if（t!=0）
	{ 
		inorder（t->lchild）;
		cout<key<<“ “;
		inorder（t->rchild）;
	}
}
void main（）
{
	int n;
	BSTNode *bt=NULL*p;
	KeyType a[200]k;
	cout <<“请输入元素个数n:“;
	cin >>n;
	cout <<“请输入数据:“;
	
    for（int i=0;i	{
		cin >>a[i];
	}	
	CreateBST（btan）;

	cout<<“中序遍历二叉排序树:“;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2008-09-10 17:39  数据结构课程设计\
     文件       39424  2007-07-13 00:49  数据结构课程设计\200609010435任务书二叉排序树的实现.doc
     文件      154112  2008-09-10 17:35  数据结构课程设计\200609010435课程设计报告.doc
     目录           0  2008-09-10 17:36  数据结构课程设计\插图\
     文件       11437  2008-09-09 21:30  数据结构课程设计\插图\1.jpg
     文件       12091  2008-09-09 21:32  数据结构课程设计\插图\2.jpg
     目录           0  2008-09-10 17:36  数据结构课程设计\程序\
     目录           0  2008-09-10 08:43  数据结构课程设计\程序\Debug\
     文件       50176  2008-09-09 21:31  数据结构课程设计\程序\Debug\vc60.idb
     文件       61440  2008-09-09 19:27  数据结构课程设计\程序\Debug\vc60.pdb
     文件      213110  2008-09-09 19:27  数据结构课程设计\程序\Debug\二叉排序tree.exe
     文件      246348  2008-09-09 19:27  数据结构课程设计\程序\Debug\二叉排序tree.ilk
     文件       12971  2008-09-09 19:27  数据结构课程设计\程序\Debug\二叉排序tree.obj
     文件      244280  2008-09-09 19:24  数据结构课程设计\程序\Debug\二叉排序tree.pch
     文件      525312  2008-09-09 19:27  数据结构课程设计\程序\Debug\二叉排序tree.pdb
     文件        3643  2008-09-09 19:27  数据结构课程设计\程序\二叉排序tree.cpp
     文件        3475  2008-06-14 18:27  数据结构课程设计\程序\二叉排序tree.dsp
     文件         549  2008-06-14 18:28  数据结构课程设计\程序\二叉排序tree.dsw
     文件       50176  2008-09-10 17:35  数据结构课程设计\程序\二叉排序tree.ncb
     文件       53760  2008-09-10 17:35  数据结构课程设计\程序\二叉排序tree.opt
     文件        1244  2008-09-09 19:27  数据结构课程设计\程序\二叉排序tree.plg