2011年軟考程序員考試復(fù)習(xí)筆試知識點整理(19)

　　#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沒有默認(rèn)設(shè)置為NULL的構(gòu)造函數(shù)

　　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有左子樹，找出左子樹中結(jié)點值最大的節(jié)點temp(最右下角的結(jié)點，也是中序遍歷最后一個結(jié)點， 他沒有右子樹)

　　// 用temp的結(jié)點值替換下p的結(jié)點值

　　// 刪除temp(因為temp的右子樹為空，從而直接用其左子樹根代替本身就可達(dá)到刪除結(jié)點的目的)

　　// 注： 一般的方法用temp替換p，但是這樣可能導(dǎo)致樹很不平衡。

　　軟考程序員考試歷年真題重點題總結(jié)及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)