#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