首頁 考試吧論壇 Exam8視線 考試商城 網(wǎng)絡(luò)課程 模擬考試 考友錄 實(shí)用文檔 求職招聘 論文下載
2011中考 | 2011高考 | 2012考研 | 考研培訓(xùn) | 在職研 | 自學(xué)考試 | 成人高考 | 法律碩士 | MBA考試
MPA考試 | 中科院
四六級(jí) | 職稱英語 | 商務(wù)英語 | 公共英語 | 托福 | 雅思 | 專四專八 | 口譯筆譯 | 博思 | GRE GMAT
新概念英語 | 成人英語三級(jí) | 申碩英語 | 攻碩英語 | 職稱日語 | 日語學(xué)習(xí) | 法語 | 德語 | 韓語
計(jì)算機(jī)等級(jí)考試 | 軟件水平考試 | 職稱計(jì)算機(jī) | 微軟認(rèn)證 | 思科認(rèn)證 | Oracle認(rèn)證 | Linux認(rèn)證
華為認(rèn)證 | Java認(rèn)證
公務(wù)員 | 報(bào)關(guān)員 | 銀行從業(yè)資格 | 證券從業(yè)資格 | 期貨從業(yè)資格 | 司法考試 | 法律顧問 | 導(dǎo)游資格
報(bào)檢員 | 教師資格 | 社會(huì)工作者 | 外銷員 | 國際商務(wù)師 | 跟單員 | 單證員 | 物流師 | 價(jià)格鑒證師
人力資源 | 管理咨詢師考試 | 秘書資格 | 心理咨詢師考試 | 出版專業(yè)資格 | 廣告師職業(yè)水平
駕駛員 | 網(wǎng)絡(luò)編輯
衛(wèi)生資格 | 執(zhí)業(yè)醫(yī)師 | 執(zhí)業(yè)藥師 | 執(zhí)業(yè)護(hù)士
會(huì)計(jì)從業(yè)資格考試會(huì)計(jì)證) | 經(jīng)濟(jì)師 | 會(huì)計(jì)職稱 | 注冊(cè)會(huì)計(jì)師 | 審計(jì)師 | 注冊(cè)稅務(wù)師
注冊(cè)資產(chǎn)評(píng)估師 | 高級(jí)會(huì)計(jì)師 | ACCA | 統(tǒng)計(jì)師 | 精算師 | 理財(cái)規(guī)劃師 | 國際內(nèi)審師
一級(jí)建造師 | 二級(jí)建造師 | 造價(jià)工程師 | 造價(jià)員 | 咨詢工程師 | 監(jiān)理工程師 | 安全工程師
質(zhì)量工程師 | 物業(yè)管理師 | 招標(biāo)師 | 結(jié)構(gòu)工程師 | 建筑師 | 房地產(chǎn)估價(jià)師 | 土地估價(jià)師 | 巖土師
設(shè)備監(jiān)理師 | 房地產(chǎn)經(jīng)紀(jì)人 | 投資項(xiàng)目管理師 | 土地登記代理人 | 環(huán)境影響評(píng)價(jià)師 | 環(huán)保工程師
城市規(guī)劃師 | 公路監(jiān)理師 | 公路造價(jià)師 | 安全評(píng)價(jià)師 | 電氣工程師 | 注冊(cè)測繪師 | 注冊(cè)計(jì)量師
繽紛校園 | 實(shí)用文檔 | 英語學(xué)習(xí) | 作文大全 | 求職招聘 | 論文下載 | 訪談 | 游戲
您現(xiàn)在的位置: 考試吧(Exam8.com) > 軟件水平考試 > 復(fù)習(xí)資料 > 程序員資料 > 正文

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

考試吧提供了“2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理”,供考生參考。

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

  23、二叉排序樹(BST, Binary SortTree) 的C++實(shí)現(xiàn)

  二叉排序樹(Binary Sort Tree)又稱二叉查找(搜索)樹(Binary Search Tree)。

  (1)二叉排序樹定義:二叉排序樹或者是空樹,或者是滿足如下性質(zhì)的二叉樹:

  ①若它的左子樹非空,則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值;

  ②若它的右子樹非空,則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值;

 �、圩�、右子樹本身又各是一棵二叉排序樹。

  上述性質(zhì)簡稱二叉排序樹性質(zhì)(BST性質(zhì)),故二叉排序樹實(shí)際上是滿足BST性質(zhì)的二叉樹。

  (2)二叉排序樹的特點(diǎn)

  由BST性質(zhì)可得:

  [1]二叉排序樹中任一結(jié)點(diǎn)x,其左(右)子樹中任一結(jié)點(diǎn)y(若存在)的關(guān)鍵字必小(大)于x的關(guān)鍵字。

  [2]二叉排序樹中,各結(jié)點(diǎn)關(guān)鍵字是惟一的。 注意:實(shí)際應(yīng)用中,不能保證被查找的數(shù)據(jù)集中各元素的關(guān)鍵字互不相同,所以可將二叉排序樹定義中BST性質(zhì)[1]里的"小于"改為"小于等于",或?qū)ST性質(zhì)[2]里的"大于"改為"大于等于",甚至可同時(shí)修改這兩個(gè)性質(zhì)。

  [3]按中序遍歷該樹所得到的中序序列是一個(gè)遞增有序序列。

  (3)在二叉排序樹上進(jìn)行查找時(shí)的平均查找長度和二叉樹的形態(tài)有關(guān):

 �、僭谧顗那闆r下,二叉排序樹是通過把一個(gè)有序表的n個(gè)結(jié)點(diǎn)依次插入而生成的,此時(shí)所得的二叉排序樹蛻化為棵深度為n的單支樹,它的平均查找長度和單鏈表上的順序查找相同,亦是(n+1)/2。

  ②在最好情況下,二叉排序樹在生成的過程中,樹的形態(tài)比較勻稱,最終得到的是一棵形態(tài)與二分查找的判定樹相似的二叉排序樹,此時(shí)它的平均查找長度大約是lgn。

 �、鄄迦�、刪除和查找算法的時(shí)間復(fù)雜度均為O(lgn)。

  (4)二叉排序樹和二分查找的比較

  就平均時(shí)間性能而言,二叉排序樹上的查找和二分查找差不多。

  就維護(hù)表的有序性而言,二叉排序樹無須移動(dòng)結(jié)點(diǎn),只需修改指針即可完成插入和刪除操作,且其平均的執(zhí)行時(shí)間均為O(lgn),因此更有效。二分查找所涉及的有序表是一個(gè)向量,若有插入和刪除結(jié)點(diǎn)的操作,則維護(hù)表的有序性所花的代價(jià)是O(n)。當(dāng)有序表是靜態(tài)查找表時(shí),宜用向量作為其存儲(chǔ)結(jié)構(gòu),而采用二分查找實(shí)現(xiàn)其查找操作;若有序表里動(dòng)態(tài)查找表,則應(yīng)選擇二叉排序樹作為其存儲(chǔ)結(jié)構(gòu)。

  //二叉查找樹代碼

  //BTreeNode.h二叉樹結(jié)點(diǎn)抽象類型

  #ifndefBTREENODE_H

  #defineBTREENODE_H

  #include

  //template class BTree;

  template class SortBTree;

  template class BTreeNode

  {

  //friend class BTree;

  friend class SortBTree;

  public:

  BTreeNode():lchild(NULL),rchild(NULL){ };

  BTreeNode(const T&dt,BTreeNode *lch =NULL , BTreeNode *rch = NULL)

  :data(dt),lchild(lch),rchild(rch){};

  T get_data()const {return data; };

  BTreeNode* get_lchild()const{return lchild; };

  BTreeNode* get_rchild()const{return rchild; };

  void set_data(const T& d) { data =d;};

  protected:

  private:

  T data;

  BTreeNode *lchild, *rchild;

  };

  #endif

  /************************************************************************

  *SortBTree.h

  * 根據(jù)給定的字符串構(gòu)造一個(gè)排序二叉樹

  * 從排序二叉樹中尋找最大值,最小值,不存在時(shí)拋出invalid_argument異常

  * 從排序二叉樹中刪除某一元素,不存在時(shí)拋出invalid_argument 異常

  * 往排序二叉樹中添加一個(gè)新元素

  ************************************************************************/

1 2 3 4 下一頁
  相關(guān)推薦:

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

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

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

文章搜索
軟件水平考試欄目導(dǎo)航
版權(quán)聲明:如果軟件水平考試網(wǎng)所轉(zhuǎn)載內(nèi)容不慎侵犯了您的權(quán)益,請(qǐng)與我們聯(lián)系800@exam8.com,我們將會(huì)及時(shí)處理。如轉(zhuǎn)載本軟件水平考試網(wǎng)內(nèi)容,請(qǐng)注明出處。