我把我的BSTTree.cpp和BSTTree.h的源程序贴出来，还有一个BSTNode.h,请大家帮我看看。
以下是BSTTree.h
#if!defined _BSTTree_h
#define _BSTTree_h
#include "BSTNode.h"
#include <iostream>
using namespace std;
template <class Type>
class BSTTree {
public:
BSTTree(){LastFind=NULL;Root=NULL;}
~BSTTree(){ FreeTree(Root)}
int Insert(const Type &x) { return Insert(x,Root); }//插入x到以root为根的二叉排序树
const Type &Find(const Type &x) {
return (LasrFind=FindFromRoot(x,Root)) ? LastFind->data:ItemNotFind;
}//若查找x成功，则返回二叉排序树的相应的数据项。否则，返回ItemNotFound.
const Type &FindMin() const{
const BSTNode<Type> *p=FindMin(Root);
return p?p->data:ItemNotFound;
}//返回二叉排序树中的最小的数据项。若树为空，返回ItemNotFound
const Type &FindMax() const{
const BSTNode<Type> *p=FindMax(Root);
return p?p->data:ItemNotFound;
}//返回二叉排序树中的最大的数据项。若树为空，返回ItemNotFound
int IsFound(const Type &x){return Find(x,root)!=NULL;}//若x找到，则返回True
int WasFound() const {return LastFind!=NULL;}//最近一次查找成功，则返回True
int Remove(const Type &x) {return Remove(x,Root);}
//从二叉排序树中删除值为x的结点,删除成功返回True
int RemoveMin(){return RemoveMin(Root);}
//从二叉排序树中删除最小的结点，删除成功
int IsEmpty() const { return Root=NULL;}
//二叉排序树为空，返回True，否则为False
void MakeEmpty() {FreeTree(Root);Root=NULL;}
//清除二叉树中的所有结点
protected:
BSTNode<Type> *Root;
BSTNode<Type> *LastFind;
Type ItemNotFound;//用于查找失败时返回
const BSTNode<Type> *FindFromRoot(const Type &x,const BSTNode<Type> *T) const;
const BSTNode<Type> *FindMin(const BSTNode<Type> *T) const;
const BSTNode<Type> *FindMax(const BSTNode<Type> *T) const;
int Insert(const Type &x,BSTNode<Type> *&T);
int RemoveMin(const BSTNode<Type> *&T);
int Remove(const Type &x,const BSTNode<Type> *&T);
};
#endif
以下是BSTTree.cpp
#include "BSTTree.h"
#include <iostream>
using namespace std;
template <class Type>
const BSTNode<Type > * BSTTree<Type>::FindFromRoot(const Type & x, const BSTNode<Type > * T) const {
while ( T != NULL )
if ( X < T->data ) T = T->left else if ( X > T->data ) T = T->right; else return T;
return NULL;// 查找失败，返回空。查找成功，返回指向相应结点的指针。
}
template <class Type>
int BSTTree<Type> :: Insert (const Type & x, BSTNode<Type > *&T ) {
if ( T == NULL ) { T = new BSTNode<Type> (x); return 1; } // 新结点插入。
else if ( x < T->data ) return Insert( x, T->left ); // 转向左子树。
else if ( x > T->data ) return Insert( x, T->right ); // 转向右子树。
return 0;// 若结点已经存在，返回不必重复插入标志。
} // 插入结点到以 T 为根的二叉排序树中去。插入成功返回 1，插入失败返回 0。
template <class Type>
int BSTTree<Type>:: Remove( const Type & x, const BSTNode<Type > * &T ) {
BSTNode<Type > * p;
if ( T == NULL ) return 0; // 删除失败，返回 0。
else if ( x < T->data ) return Remove( x, T->left ); // 转向左子树。
else if ( x > T->data ) return Remove( x, T->right ); // 转向右子树。
else if ( T->left != NULL && T->right != NULL ) { // 被删结点的左右儿子非空。
p=( BSTNode<Type> * )FindMin(T->right);
T->data=p->data; //复制右子树最小结点数据值。
return RemoveMin( T->right ); //删除被删结点的右子树的最小结点。
}
p = T; // 处理被删结点的至少一个儿子结点为空的情况。
T = ( T->left == NULL ) ? T->right : T->left;
delete p;
return 1;
} // 删除成功，返回1。删除失败，返回 0。
template<class Type>
const BSTNode<Type> *BSTTree<Type>::FindMin(const BSTNode<Type> *T) const{
if(T!=NULL)
while(T->left!=NULL) T=T->left;
return T;
}
template<class Type>
const BSTNode<Type> *BSTTree<Type>::FindMax(const BSTNode<Type> *T) const{
if(T!=NULL)
while(T->right!=NULL) T=T->right;
return T;
}
template<class Type>
int BSTTree<Type>::RemoveMin(const BSTNode<Type> *&T){
if(T==NULL) return 0;
else if(T->left!=NULL) return RemoveMin(T->left);
BSTNode<Type> *p;
p=T;
T=T->right;
delete p;
return 1;
}
还有一个BSTNode.h
#if!defined _BSTNode_h
#define _BSTNode_h
#include <iostream>
using namespace std;
template <class Type>
class BSTNode { // 二叉排序树的结点的表示。
public:
Type data; // 结点的数据场。
BSTNode<Type> * left; // 给出结点的左儿子的地址。
BSTNode<Type> * right; // 给出结点的右儿子的地址。
int BalanceFactor; // 结点的平衡度，用于 AVL 树。
int Size; // 以本结点为根的子树的所有结点的个数，用于顺序统计。
BSTNode ( ): left(NULL), right(NULL), Size(1), BalanceFactor(1) { }
BSTNode ( const Type x ) : data(x), left(NULL), right(NULL), Size(1),
BalanceFactor(1) { }
BSTNode ( const Type x, BSTNode<Type> * L, BSTNode<Type> * R ): data(x), left(L), right(R), Size(1), BalanceFactor(1) { }
~BSTNode( ) { }
};
#endif
