#ifndefSORTBTREE_H

　　#defineSORTBTREE_H

　　#include"BTreeNode.h"

　　#include

　　#include

　　template

　　classSortBTree

　　{

　　public:

　　SortBTree(T* p , int n);

　　const T& max()const; // return themaximum

　　const T& min()const; // return theminimum

　　BTreeNode* find_data(const T&data)const; //return the node of data, if data is not exist, throw error

　　//delete the node of data, if data is notexist, throw error

　　void delete_data(const T& data) {delete_data(root,data); };

　　void insert_data(const T& data) { insert_data(root,data);};

　　BTreeNode* get_root()const {returnroot; }; // return the root of tree

　　void display()const { display(root,visit); cout <

　　protected:

　　static void insert_data(BTreeNode *&root, const T& ndata); //这里必须是对指针的引用,切记，切记

　　static BTreeNode*find_data(BTreeNode* r,const T& data);

　　static void delete_node(BTreeNode* &p);

　　static void delete_data(BTreeNode*&r, const T& data);

　　static void display(BTreeNode*p,void visit(BTreeNode* p));

　　private:

　　BTreeNode *root;

　　};

　　//constructionfunction

　　template

　　SortBTree::SortBTree(T*p, int n)

　　{

　　root = new BTreeNode;

　　root = NULL; //注意这行很必要，BTreeNode没有默认设置为NULL的构造函数

　　for(int i = 0; i != n; ++i)

　　{

　　insert_data(root,p[i]);

　　}

　　}

　　//insert a new data

　　template

　　voidSortBTree::insert_data(BTreeNode *&rt,const T& ndata)

　　{

　　if(rt == NULL)

　　{

　　rt = newBTreeNode(ndata,NULL,NULL);

　　//rt->data = ndata; //这三条语句不等于上面那条

　　//rt->lchild = NULL; //用这三条语句是错的

　　//rt->rchild = NULL;

　　}

　　else if(rt->data == ndata) return;

　　else if(rt->data > ndata)insert_data(rt->lchild, ndata);

　　else insert_data(rt->rchild, ndata);

　　}

　　//delete a node from tree(improved)

　　// 如果p没有左子树，则让p的右子树的根代替p即可。

　　// 如果p有左子树，找出左子树中结点值最大的节点temp(最右下角的结点，也是中序遍历最后一个结点， 他没有右子树)

　　// 用temp的结点值替换下p的结点值

　　// 删除temp(因为temp的右子树为空，从而直接用其左子树根代替本身就可达到删除结点的目的)

　　// 注： 一般的方法用temp替换p，但是这样可能导致树很不平衡。