//二叉搜索樹的類定義BSTreeF.h
//定義學(xué)生記錄類型
//定義二叉搜索樹結(jié)點(diǎn)值的類型為學(xué)生記錄類型
typedef struct student
{char num[6];//學(xué)號
 int grade; //成績
}ElemType;
template<class T>class BSTree {
 private:
  BSTree<T> *left;//左子樹指針
  BSTree<T> *right;//右子樹指針
 public:
  T data;//數(shù)據(jù)域
  //構(gòu)造函數(shù)
  BSTree():left(NULL),right(NULL) { }
  BSTree(T item,BSTree<T> *left1=NULL,
    BSTree<T> *right1=NULL):data(item),
    left(left1),right(right1){ }
  BSTree<T> *&Left(){return left;}
  BSTree<T> *&Right(){return right;}
//初始化二叉搜索樹，即把樹根指針置空
  void InitBSTree(BSTree<T> *&BST);
//判斷二叉搜索樹是否為空
  bool BSTreeEmpty(BSTree<T> *&BST);
//從二叉搜索樹中查找元素
  bool Find(BSTree<T> *&BST,T item);
//更新二叉搜索樹中的結(jié)點(diǎn)值
  bool Update(BSTree<T> *&BST,const T item,T newc);
//向二叉搜索樹中插入元素
  void Insert(BSTree<T> *&BST,const T &item);
//從二叉搜索樹中刪除元素
  bool Delete(BSTree<T> *&BST,T item);
//利用數(shù)組建立一棵二叉搜索樹
  void CreateBSTree(BSTree<T> *&BST,T a[],int n);
//中序遍歷輸出二叉搜索樹中的所有結(jié)點(diǎn)
  void Inorder(BSTree<T> *&BST);
//求二叉搜索樹的深度
  int BSTreeDepth(BSTree<T> *&BST);
//求二叉搜索樹中所有結(jié)點(diǎn)數(shù)
  int BSTreeCount(BSTree<T> *&BST);
//求二叉搜索樹中所有葉子結(jié)點(diǎn)數(shù)
  int BSTreeLeafCount(BSTree<T> *&BST);
//按照二叉搜索樹的廣義表表示輸出二叉搜索樹
  void PrintBSTree(BSTree<T> *&BT);
//清除二叉搜索樹，使之變?yōu)橐豢每諛?  void ClearBSTree(BSTree<T> *&BT);
//把BST二叉搜索樹按照先根遍歷的次序存儲到文件fname中
  void WriteFile(char* fname, BSTree *BST);
//把fname文件中按先根遍歷存儲的二叉搜索樹恢復(fù)到內(nèi)存中
  void ReadFile(char* fname, BSTree* &BST);
  void PreorderWrite(ofstream& ofs, BSTree* BST);
  void PreorderRead(ifstream& ifs, BSTree* BST, int& b);
  friend ostream& operator<<(ostream& ostr, const ElemType& x)
   {ostr<<x.num<<':'<<x.grade;return ostr;}
};