template

　　voidSortBTree::delete_node(BTreeNode * &p)

　　{

　　if(p == NULL) cout << "There isnot this node." <

　　else if(p->lchild == NULL) p =p->rchild;

　　else

　　{

　　BTreeNode* temp = p;

　　//记录左子树中序遍历的最后一个结点(值最大的点)

　　while(temp->rchild != NULL)

　　temp = temp->rchild;

　　//删除这个结点，等价于用这个结点的做子树代替这个结点(因为这个结点没有右子树)

　　BTreeNode* parent;

　　parent = temp;

　　while(parent->rchild != NULL)

　　{

　　parent = temp;

　　temp = temp->rchild;

　　}

　　parent = temp->lchild;

　　p->set_data(temp->data);

　　}

　　}

　　//deletea data

　　template

　　voidSortBTree::delete_data(BTreeNode* &root, const T&data)

　　{

　　if(root == NULL)

　　throw std::invalid_argument("Thisdata is not exsit.");

　　else if(root->data == data)delete_node(root);

　　else if(root->data > data)delete_data(root->lchild,data);

　　else delete_data(root->rchild,data);

　　}

　　//find a specific data

　　template

　　BTreeNode* SortBTree::find_data(BTreeNode*r,const T& data)

　　{

　　if(r == NULL) return r;

　　else if(r->data == data) return r; //注意这两行是不能合并在一起的，不然可能会出现NULL->data呢

　　else if(r->data > data) returnfind_data(r->lchild,data);

　　else return find_data(r->rchild,data);

　　}

　　//find a specific data in tree

　　template

　　BTreeNode*SortBTree::find_data(const T& data)const

　　{

　　if(find_data(root,data) == NULL)

　　throw std::invalid_argument("Thisdata is not exist.");

　　else

　　return find_data(root,data);

　　}

　　//return the maximum value

　　template

　　constT& SortBTree::max()const

　　{

　　if(root == NULL)

　　throw std::invalid_argument("Thisis an empty Tree.");

　　else

　　{

　　BTreeNode *q = root;

　　while(q->rchild != NULL)

　　q = q->rchild;

　　return q->data;

　　}

　　}

　　//returnthe minimum value

　　template

　　constT& SortBTree::min()const

　　{

　　if(root == NULL)

　　throw std::invalid_argument("Thisis an empty Tree.");

　　else

　　{

　　BTreeNode *q = root;

　　while(q->lchild != NULL)

　　q = q->lchild;

　　return q->data;

　　}

　　}

　　//printthe sort tree

　　template

　　voidSortBTree::display(BTreeNode*p, voidvisit(BTreeNode* p))

　　{

　　if(p != NULL)

　　{

　　display(p->lchild,visit);

　　visit(p);

　　display(p->rchild,visit);

　　}

　　}

　　#endif