計算機(jī)三級數(shù)據(jù)庫知識點總結(jié)——樹

1、樹1、對非空二叉樹遍歷的三個步驟：?訪問根節(jié)點?先序遍歷左子樹?先序遍歷右子樹。前序是按???的順序得到的序列，對稱序是按???，后序是按???。特例：根節(jié)點為A、只有左子樹B，對稱序為BA、前序為AB；上述序列A的右子樹為C，C的左子樹為D，后一個序列對稱序為BADC、前序為ABCD。2、如果對一棵有n個節(jié)點的完全二叉樹完全二叉樹的節(jié)點按層序編號，則對任意結(jié)點i（）有：如果i=1，結(jié)點i是二叉樹的根；如果i1則雙親PARENT（i）n

2、i??1是結(jié)點i2。如果2in，則結(jié)點i無左孩子無左孩子；否則其左孩子結(jié)點為2i。如果2i1n，則結(jié)點i無右孩子；否則其右孩子是結(jié)點2i1.3、B樹只適合隨機(jī)檢索，不適合順序檢索。B樹更常用于順序檢索。樹更常用于順序檢索。二者都是多路查找樹，都是動態(tài)索引結(jié)構(gòu)，都能有效支持隨機(jī)檢索。4、棧的應(yīng)用：數(shù)值轉(zhuǎn)換、括號匹配檢驗、行編輯程序、表達(dá)式求值、樹的層序遍歷、二叉樹對稱序周游算法等。5、棧的基本運算：push是往棧中插入一個元素、pop是從

3、棧中刪除一個元素、top是求棧頂元素的值。6、串——由0個或多個字符組成的有限序列。串中字符的數(shù)目就是串的長度。串的存儲有順序存儲和鏈?zhǔn)酱鎯樞虼鎯玩準(zhǔn)酱鎯煞N。串的基本運算：創(chuàng)建串、判斷串是否為空、計算串長度、串鏈接、求子串和串的定位。7、棧和隊列的存儲方式，可以是順序方式，也可以是鏈?zhǔn)椒绞?。棧和隊列都可為空。棧能?yīng)用于遞歸過程實現(xiàn)。8、隊列的基本操作：構(gòu)造空隊列、清空隊列、判斷隊列是否為空、求隊列長度、讀取隊列頭元素的值、在隊尾插

4、入新元素、刪除隊頭元素。9、二叉樹是結(jié)點的有限集合，這個有限集合或者為空集空集，或者由一個根結(jié)點及兩棵不相交的，分別稱作這個根的左子樹和右子樹的二叉樹組成。最簡單的二叉樹是空二叉樹。10、二叉樹不是樹的特殊情況。樹和二叉樹之間最主要的區(qū)別是：二叉樹的結(jié)點的子樹要區(qū)分左子樹和右子樹，即使在結(jié)點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。每一棵二叉樹都能唯一的轉(zhuǎn)化唯一的轉(zhuǎn)化成它所對應(yīng)的樹。11、二叉樹轉(zhuǎn)換為樹或森林轉(zhuǎn)換為樹或森

5、林的方式是：若結(jié)點x是雙親y的左孩子，則把x的有孩子，右孩子的右孩子……都與y用線連接起來，最后去掉所有雙親到右孩子的連線即可。12、霍夫曼算法是用來求具有最小最小帶權(quán)外部路徑長度的擴(kuò)充二叉樹的算法。13、霍夫曼樹也稱為最優(yōu)二叉樹最優(yōu)二叉樹，權(quán)值大的結(jié)點離根最近，沒有度為1的結(jié)點23、設(shè)根節(jié)點的層次為0，則高度為K的二叉樹的最大結(jié)點值（即為滿二叉樹）是2k11(有疑問），最小節(jié)點數(shù)為2k。24、在有n個結(jié)點的二叉樹的llinkrlink

6、法存儲表示中，必有n1個空指針。（n個結(jié)點的樹一共有2n個指針域，而樹中只有n1條邊，故樹中的空指針數(shù)為2n(n1)=n1）25、廣義表是遞歸定義的，可以被其他廣義表共享，當(dāng)其為空表時，其長度為0.26、三元組法和十字鏈表法都可以用于稀疏矩陣稀疏矩陣的存儲表示。27、三元組方法存儲稀疏矩陣是將稀疏矩陣中所有非零元素非零元素列舉出來，但它不反映稀疏矩陣中同行或同列元素的關(guān)系，從三元組的行數(shù)就可以知道非零元素的個數(shù)。28、二分法查找的優(yōu)點是

7、比較次數(shù)少，查找速度快，對有n個數(shù)據(jù)元素的線性表（要求以順序方式存儲）進(jìn)行二分法查找，若查找成功，給定值最多與個關(guān)鍵字進(jìn)行比較。1log2?n29、查詢處理器主要模塊：查詢編譯器和查詢執(zhí)行引擎。30、B樹的所有關(guān)鍵碼都出現(xiàn)在葉結(jié)點上，上面隔層節(jié)點中的關(guān)鍵碼均是下層結(jié)點的最大關(guān)鍵碼的復(fù)寫?；舴蚵鼞?yīng)用實例霍夫曼應(yīng)用實例：對于給出的一組權(quán)w=10，12，16，21，30，通過霍夫曼算法求出的擴(kuò)充二叉樹的帶權(quán)外部路徑長度是多少？1、每行選出最小