aaa.cpp

二叉排序树的建立和删除

#include<iostream.h>
#include<stdlib.h>

typedef int Keytype;;
typedef struct node
{
	Keytype key;
	struct node *lchild,*rchild;
}BSTNode;
typedef BSTNode *BSTree;
BSTree CreateBST();
void SearchBST(BSTree T,Keytype Key);
void InsertBST(BSTree *T,Keytype Key);
void DelBST(BSTree *T,Keytype Key);
void InorderBST(BSTree T);

void main()
{
	BSTree T;
	char ch1,ch2;
	Keytype Key;
	cout<<"建立一棵二叉排序树"<<endl;
	T=CreateBST();
	ch1='y';
	while(ch1=='y'||ch1=='Y')
	{
		cout<<"请选择以下操作"<<endl;
		cout<<"1----------更新二叉排序树存储"<<endl;
		cout<<"2----------二叉排序树上的查找"<<endl;
		cout<<"3----------二叉排序树上的插入"<<endl;
		cout<<"4----------二叉排序树上的删除"<<endl;
		cout<<"5----------二叉排序树上的输出"<<endl;
		cout<<"6----------退出"<<endl;

		cin>>ch2;
		switch(ch2)
		{
			case '1':
				CreateBST();
				break;
			case '2':
				cout<<"请输入要查找的数据:";
				cin>>Key;
				SearchBST(T,Key);
				cout<<"查找完毕"<<endl;
				break;
			case '3':
				cout<<"请输入要插入的数据:";
				cin>>Key;
				InsertBST(&T,Key);
				cout<<"插入操作完毕"<<endl;
				break;
			case '4':
				cout<<"请输入要删除的数据:";
			    cin>>Key;
				DelBST(&T,Key);
				cout<<"删除操作完毕"<<endl;
				break;
			case '5':
				InorderBST(T);
				cout<<"二叉排序树输出完毕"<<endl;
				break;
			case '6':
				ch1='n';
				break;
			default:
				ch1='n';
		}
	}
}


BSTree CreateBST()
{
	BSTree T;
	Keytype Key;
	T=NULL;
	cout<<"请输入一组关键字,以零结束"<<endl;
	cin>>Key;
	while(Key)
	{
		InsertBST(&T,Key);
		cout<<"请输入下一个关键字"<<endl;
		cin>>Key;
	}
	return T;
}

void SearchBST(BSTree T,Keytype Key)
{
	BSTNode *p=T;
	while(p)
	{
		if(p->key==Key)
		{
			cout<<"已找到"<<endl;
			return;
		}
		p=(Key<p->key)?p->lchild:p->rchild;
	}
	cout<<"没有找到。。。";
}

void InsertBST(BSTree *T,Keytype Key)
{
	BSTNode *f,*p;
	p=(*T);
	while(p)
	{
		if (p->key==Key)
		{
			cout<<"树中已有Key不需插入"<<endl;
			return;
		}
		f=p;
		p=(Key<p->key)?p->lchild:p->rchild;
	}
		p=(BSTNode*)malloc(sizeof(BSTNode));
		p->key=Key;
		p->lchild=p->rchild=NULL;
		if ((*T)==NULL) (*T)=p;
		else if (p->key<f->key) f->lchild=p;
				else f->rchild=p;
}

void DelBST(BSTree *T,Keytype Key)
{
	BSTNode *parent=NULL,*p,*q,*child;
	p=*T;
	while(p)
	{
		if (p->key==Key) break;
		parent=p;
		p=(Key<p->key)?p->lchild:p->rchild;
	}
	if (!p)
	{
		cout<<"没有找到要删除的节点"<<endl;
		return;
	}

	q=p;
	if (q->lchild&&q->rchild)
		for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);
	
	child=(p->lchild)?p->lchild:p->rchild;
	if(!parent) *T=child;
	else
	{
		if(p==parent->lchild) parent->lchild=child;
		else parent->rchild=child;
		if (p!=q) q->key=p->key;
	}
	free(p);
}

void InorderBST(BSTree T)
{
	if (T!=NULL)
	{
		InorderBST(T->lchild);
		cout<<T->key<<"      ";
		InorderBST(T->rchild);
	}
}