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

　　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;

　　//記錄左子樹(shù)中序遍歷的最后一個(gè)結(jié)點(diǎn)(值最大的點(diǎn))

　　while(temp->rchild != NULL)

　　temp = temp->rchild;

　　//刪除這個(gè)結(jié)點(diǎn)，等價(jià)于用這個(gè)結(jié)點(diǎn)的做子樹(shù)代替這個(gè)結(jié)點(diǎn)(因?yàn)檫@個(gè)結(jié)點(diǎn)沒(méi)有右子樹(shù))

　　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; //注意這兩行是不能合并在一起的，不然可能會(huì)出現(xiàn)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

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

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

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