2011年软考程序员考试复习笔试知识点整理(19)2

 　#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

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，但是这样可能导致树很不平衡。