二叉排序的种模板形式
二叉排序的类模板形式
#include<iostream>
using namespace std;
template<class T>
struct Node
{
T key;
};
template<class T>
struct bitree
{
Node<T>data;
bitree<T> * lchild;
bitree<T> * rchild;
};
template<class T>
class BSTree
{
public:
Node<T> *ST;
int len;
bitree<T> *t;
bitree<T> *f;
bitree<T> *p;
BSTree();
~BSTree();
void SearchBST(bitree<T> *t,T key);
void InsertBST(bitree<T> *(&t),Node<T> e);
int DeleteBST(bitree<T> *(&t),T key);
int Delete(bitree<T> *(&p));
void DeleteElem(T key);
void InDisplay(bitree<T> *t);
void Display();
};
template<class T>
BSTree<T>::BSTree()
{
ST=new Node<T>[maxsize];
len=0;
t=NULL;
}
template<class T>
BSTree<T>::~BSTree()
{
delete[] ST;
len=0;
delete t;
cout<<"成功销毁二叉排序树\n";
}
template<class T>
void BSTree<T>::SearchBST(bitree<T> *t,T key)
{
if(t==NULL||key==t->data.key)
{
if(key==t->data.key)
cout<<"找到"<<key<<"的节点"<<endl;
else
cout<<"不存在"<<key<<"的节点"<<endl;
}
else if (key<t->data.key)
SearchBST(t->lchild,key);
else
SearchBST(t->rchild,key);
}
template<class T>
void BSTree<T>::InsertBST(bitree<T> *(&t),Node<T> e)
{
ST[len]=e;
len++;
p=t;
while(p)
{
if(p->data.key==e.key)
{
cout<<"二叉排序树中已经存在值为:"<<e.key<<"的节点\n";
exit(1);
}
f=p;
if(e.key<p->data.key)
p=p->lchild;
else
p=p->rchild;
p=new bitree<T>;
p->data=e;
p->lchild=p->rchild=NULL;
if(t==NULL)
t=p;
else
{
if(e.key<f->data.key)
f->lchild=p;
else
f->rchild=p;
}
}
}
template<class T>
int BSTree<T>::DeleteBST(bitree<T> *(&t),T key)
{
if(!t)
{
cout<<"二叉排序树为空 无法删除\n";
return FALSE;
}
else
{
if(key==t->data.key)
return Detele(t);
else if(key<t->data.key)
return DeteleBST(t->lchild,key);
else
return DeleteBST(t->rchild,key);
}
}
template<class T>
int BSTree<T>::Delete(bitree<T> *(&p))
{
bitree<T> *q, *s;
if(!p->rchild)
{
q=p;
p=p->lchild;
delete q;
cout<<"成功删除"<<endl;
}
else if (!p->lchild)
{
q=p;
p=p->rchild;
delete q;
cout<<"成功删除"<<endl;
}
else
{
q=p;
s=p->lchild;
while(s->rchild)
{
q=s;
s=s->rchild;
}
p->data=s->data;
if(q!=p)
q->rchild=s->lchild;
else
q->lchild=s->lchild;
delete s;
cout<<"成功删除"<<endl;
}
return TRUE;
}
template<class T>
void BSTree<T>::DeleteElem(T key)
{