數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)重點(diǎn)歸納(編輯修改稿)
2025-05-14 01:47 本頁面
【文章內(nèi)容簡介】 通雙分支樹的區(qū)別；考查滿二叉樹和完全二叉樹的性質(zhì)，普通二叉樹的五個(gè)性質(zhì)：第i層的最多結(jié)點(diǎn)數(shù)，深度為k的二叉樹的最多結(jié)點(diǎn)數(shù)，n0=n2+1的性質(zhì)，n個(gè)結(jié)點(diǎn)的完全二叉樹的深度，順序存儲二叉樹時(shí)孩子結(jié)點(diǎn)與父結(jié)點(diǎn)之間的換算關(guān)系（左為：2*i，右為：2*i+1）。二叉樹的順序存儲和二叉鏈表存儲的各自優(yōu)缺點(diǎn)及適用場合，二叉樹的三叉鏈表表示方法。2. 二叉樹的三種遍歷算法這一知識點(diǎn)掌握的好壞，將直接關(guān)系到樹一章的算法能否理解，進(jìn)而關(guān)系到樹一章的算法設(shè)計(jì)題能否順利完成。二叉樹的遍歷算法有三種：先序，中序和后序。其劃分的依據(jù)是視其每個(gè)算法中對根結(jié)點(diǎn)數(shù)據(jù)的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執(zhí)行的實(shí)際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法。由于二叉樹一章的很多算法，可以直接根據(jù)三種遞歸算法改造而來（比如：求葉子個(gè)數(shù)），所以，掌握了三種遍歷的非遞歸算法后，對付諸如：“利用非遞歸算法求二叉樹葉子個(gè)數(shù)”這樣的題目就下筆如有神了。我會在另一篇系列文章（：//）里給出三種遍歷的遞歸和非遞歸算法的背記版，到時(shí)請大家一定熟記。3. 可在三種遍歷算法的基礎(chǔ)上改造完成的其它二叉樹算法：求葉子個(gè)數(shù)，求二叉樹結(jié)點(diǎn)總數(shù)，求度為1或度為2的結(jié)點(diǎn)總數(shù)，復(fù)制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個(gè)指定結(jié)點(diǎn)，刪除值為n的某個(gè)指定結(jié)點(diǎn)，諸如此類等等等等。如果你可以熟練掌握二叉樹的遞歸和非遞歸遍歷算法，那么解決以上問題就是小菜一碟了。4. 線索二叉樹：線索二叉樹的引出，是為避免如二叉樹遍歷時(shí)的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內(nèi)存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險(xiǎn)，為了避免此類情況，線索二叉樹便堂而皇之地出現(xiàn)了。對于線索二叉樹，應(yīng)該掌握：線索化的實(shí)質(zhì)，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題（如：查找某一類線索二叉樹中指定結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)就是一類?？碱}）。？？？5. 最優(yōu)二叉樹（哈夫曼樹）：最優(yōu)二叉樹是為了解決特定問題引出的特殊二叉樹結(jié)構(gòu)，它的前提是給二叉樹的每條邊賦予了權(quán)值，這樣形成的二叉樹按權(quán)相加之和是最小的。最優(yōu)二叉樹一節(jié)，直接考查算法源碼的很少，一般是給你一組數(shù)據(jù)，要求你建立基于這組數(shù)據(jù)的最優(yōu)二叉樹，并求出其最小權(quán)值之和，此類題目不難，屬送分題。(二叉排序樹)熟練掌握二叉搜索樹的構(gòu)造,以及節(jié)點(diǎn)的刪除操作,例如刪除其根節(jié)點(diǎn)時(shí)關(guān)鍵應(yīng)找出右子樹中最小的節(jié)點(diǎn)來替代其根節(jié)點(diǎn),然后進(jìn)行后續(xù)操作7. B樹和B+數(shù)同樣掌握B樹的構(gòu)建,添加節(jié)點(diǎn)與刪除節(jié)點(diǎn)等操作8. 樹與森林：二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最多為2以及其它特征，一個(gè)最重要的特殊之處是在于：二叉樹是有序的！即：二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之后的二叉樹與原二叉樹我們認(rèn)為是不相同的兩棵二叉樹。但是，對于普通的雙分支樹而言，不具有這種性質(zhì)。樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷算法：先根與后根（對于森林而言稱作：先序與后序遍歷）。在難度比較大的考試中，也有基于此二種算法的基礎(chǔ)上再進(jìn)行擴(kuò)展要求你利用這兩種算法設(shè)計(jì)其它算法的，但一般院校很少有這種考法，最多只是要求你根據(jù)先根或后根寫出他們的遍歷序列。此二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的：先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。這一點(diǎn)成為很多學(xué)校的考點(diǎn)，考查的方式不一而足，有的直接考此句話，有的是先讓你求解遍歷序列然后回答這個(gè)問題。二叉樹、樹與森林之所以能有以上的對應(yīng)關(guān)系，全拜二叉鏈表所賜。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。樹一章，處處是重點(diǎn)，道道是考題，大家務(wù)必個(gè)個(gè)過關(guān)。第六章 圖如果說，從線性結(jié)構(gòu)向樹形結(jié)構(gòu)研究的轉(zhuǎn)變，是數(shù)據(jù)結(jié)構(gòu)學(xué)科對數(shù)據(jù)組織形式研究的一次升華，那么從樹形結(jié)構(gòu)的研究轉(zhuǎn)到圖形結(jié)構(gòu)的研究，則進(jìn)一步讓我們看到了數(shù)據(jù)結(jié)構(gòu)對于解決實(shí)際問題的重大推動作用。圖這一章的特點(diǎn)是：概念繁多，與離散數(shù)學(xué)中圖的概念聯(lián)系緊密，算法復(fù)雜，極易被考到，且容易出大題，尤其是名校，作為考研課程，如果不考查樹與圖兩章的知識，幾乎是不可想像的。下面我們看一下圖這一章的主要考點(diǎn)以及這些考點(diǎn)的考查方式：1. 考查有關(guān)圖的基本概念問題：這些概念
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1