西安交通大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料-預(yù)覽頁
【正文】 另一端進(jìn)行刪除。了解隊列特別是循環(huán)隊列情況下，隊列頭指針和尾指針的設(shè)置了解隊列出現(xiàn)“假溢出”現(xiàn)象的原因及解決辦法：循環(huán)隊列的實現(xiàn)（循環(huán)頭指針和尾指針的計算、循環(huán)（和普通）隊列長度的計算以及循環(huán)隊列為空和滿的判斷方法）第五章 樹和二叉樹了解樹的定義和樹的基本術(shù)語：樹和結(jié)點的度、分支結(jié)點和葉子結(jié)點、父母結(jié)點和孩子結(jié)點、結(jié)點的層數(shù)和樹的深度、有序樹和無序樹等在樹形表示法中，結(jié)點之間的關(guān)系是通過連線表示的，雖然每條連線上都不帶有箭頭(即方向)，但它并不是無向的，而是有向的，其方向隱含為從上向下或從左向右，即連線的上方或左邊結(jié)點是下方或右邊結(jié)點的前驅(qū)，下方或右邊結(jié)點是上方或左邊結(jié)點的后繼。v 分支結(jié)點：度非零的結(jié)點稱為分支結(jié)點或稱為非終端結(jié)點。v 堂兄弟結(jié)點(cousins)：其雙親在同一層但不同的結(jié)點互為堂兄弟。在有序樹中，改變了子樹的相對次序就變成了另一棵樹。樹的總分支數(shù)為：v 性質(zhì)2： 度為k的樹中第i層上至多有ki1個結(jié)點（i≥1）。 v 性質(zhì)3 深度為h的k叉樹至多有 個結(jié)點。 分析：在結(jié)點數(shù)相同的 k叉樹中，每一層結(jié)點都滿，或除最后一層外其余層都滿的樹，其深度為最小。logk( n(k1)+1)249。v 二叉樹(binary tree)是指樹的度為2的有序樹。性質(zhì)2： 深度為k的二叉樹，最多有2k1個結(jié)點 ( k ≥1)。 n1 :單分支結(jié)點數(shù), n2 :雙分支結(jié)點數(shù)) (2) 設(shè)B為二叉樹中總的分支數(shù)目，由于二叉樹中除了根結(jié)點之外，其余結(jié)點都有一個分支進(jìn)入,而這些分支只能是由度數(shù)為1或2的結(jié)點所發(fā)出，所以： B = n1 + 2n2 于是得： n = n1 + 2n2 + 1(3) 由(1)和(2)得： n0 + n1 + n2 = n1 + 2n2 + 1 所以 n0 = n2 + 1 證畢性質(zhì)4：對完全二叉樹中編號為i的結(jié)點(1≤i≤n,n≥1，n為結(jié)點數(shù))有： (1) 若i≤235。x (4) 除樹根結(jié)點外，若一個結(jié)點的編號為i，則它的雙親結(jié)點的編號為235。性質(zhì)5：具有n個(n0)結(jié)點的完全二叉樹的深度為233。+1。 完全二叉樹的深度h和結(jié)點數(shù)n的關(guān)系，還可表示為： 2h1≤n2h 取對數(shù)后得： h1≤log2nh 即： log2nh≤log2n+1 因h只能取整數(shù)，所以： h= 235。完全二叉樹： 除最后一層外，其余層均滿；最后層或為滿，或缺少右邊若干連續(xù)結(jié)點。完全二叉樹中深度h和結(jié)點數(shù)n之間的關(guān)系，在理想平衡樹中同樣成立，了解二叉樹的鏈接存儲結(jié)構(gòu)根據(jù)二叉樹的特性，任何一個結(jié)點最多有左、右兩棵子樹，所以每個結(jié)點至少設(shè)有三個域：數(shù)據(jù)域和左、右指針域。 { 先訪問右子樹根節(jié)點；再遍歷右子樹根節(jié)點的左子樹，再遍歷右子樹根節(jié)點的右子樹；……直至遍歷完所有右子樹的節(jié)點}(2) 中序遍歷： 若二叉樹為空，則空操作；否則 ① 中序遍歷左子樹。 (1) 若它的左子樹非空，則左子樹上所有結(jié)點的關(guān)鍵字均小于樹根結(jié)點的關(guān)鍵字； (2) 若它的右子樹非空，則右子樹上所有結(jié)點的關(guān)鍵字均大于樹根結(jié)點的關(guān)鍵字； (3) 左、右子樹本身又各是一棵二叉搜索樹。v 若二叉搜索樹是一棵理想平衡樹或接近理想平衡樹，則進(jìn)行查找的時間復(fù)雜度為O(log2n)，v 若為一棵單支樹(這是最極端和最差的情況)，則其時間復(fù)雜度為O(n)，v 一般情況而言，其時間復(fù)雜度可大致可看做為O(log2n)。(1) 若樹根結(jié)點存在左孩子，則樹根結(jié)點的值小于等于左孩子結(jié)點的值；(2) 若樹根結(jié)點存在右孩子，則樹根結(jié)點的值小于等于右孩子結(jié)點的值；(3) 以左、右孩子為根的子樹又同樣各是一個堆。能采用給定的數(shù)據(jù)序列來生成一個堆（大根堆或小根堆）了解樹的帶權(quán)路徑，以及哈夫曼樹（最優(yōu)二叉樹）的概念和性質(zhì)(1) 路徑和路徑長度若在一棵樹中存在著一個結(jié)點序列k1,k2,…,kj，使得ki是ki+1的雙親(1≤ij)，則稱此結(jié)點序列是從k1到kj的路徑。 (2) 結(jié)點的權(quán)和帶權(quán)路徑長度 在許多應(yīng)用中，常常將樹中的結(jié)點賦予一個有著某種意義的實數(shù)，我們稱此實數(shù)為該結(jié)點的權(quán)。它是n個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中，帶權(quán)路徑長度WPL最小的二叉樹。若頂點集為空，則邊集必然為空，若頂點集非空，則邊集可空可不空，當(dāng)邊集為空時，圖G中的頂點均為孤立頂點。 1, 對于無向圖，(vi,vj)或(vj, vi)206。 0, 對應(yīng)邊不存在于E(G)中v 從鄰接矩陣中可查兩個結(jié)點的之間是否存在通路，若兩個結(jié)點的坐標(biāo)的交叉其值不為零并不是一個很大的值的話，則有通路，否則沒有通路。v 在無向圖中, 統(tǒng)計第 i 行 (列)中 1 的個數(shù)可得頂點i 的度。鄰接表(adjacency list)是對圖中的每個頂點建立一個鄰接關(guān)系的單鏈表，并把它們的表頭指針用向量存儲的一種圖的表示方法。v 邊結(jié)點通常包含三個域：一是鄰接點域(adjvex)，用以存儲頂點vi的一個鄰接頂點vj的序號j；二是權(quán)域(weight)，用以存儲邊(vi, vj)或 vi, vj 上的權(quán)；三是鏈域(next)，用以鏈接vi鄰接表中的下一個邊結(jié)點。這樣，圖G就可以由這個表頭向量來表示和存取。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1