西安交通大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料-閱讀頁(yè)
2025-05-02 12:21本頁(yè)面
【正文】 og2nh 即： log2nh≤log2n+1 因h只能取整數(shù)，所以： h= 235。+1熟悉滿二叉樹、完全二叉樹以及平衡二叉樹等幾種特殊的二叉樹的性質(zhì)、特點(diǎn)，并能根據(jù)這些性質(zhì)進(jìn)行相關(guān)的推理和計(jì)算滿二叉樹:叉樹每層的結(jié)點(diǎn)數(shù)達(dá)到最大值。完全二叉樹： 除最后一層外，其余層均滿；最后層或?yàn)闈M，或缺少右邊若干連續(xù)結(jié)點(diǎn)。理想平衡二叉樹：在一棵二叉樹中，若除最后一層外，其余層都是滿的，而最后一層上的結(jié)點(diǎn)可以任意分布，則稱此樹為理想平衡二叉樹,簡(jiǎn)稱理想平衡樹或理想二叉樹。完全二叉樹中深度h和結(jié)點(diǎn)數(shù)n之間的關(guān)系，在理想平衡樹中同樣成立，了解二叉樹的鏈接存儲(chǔ)結(jié)構(gòu)根據(jù)二叉樹的特性，任何一個(gè)結(jié)點(diǎn)最多有左、右兩棵子樹，所以每個(gè)結(jié)點(diǎn)至少設(shè)有三個(gè)域：數(shù)據(jù)域和左、右指針域。這種存儲(chǔ)結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，也便于查找雙親結(jié)點(diǎn)，當(dāng)然也帶來存儲(chǔ)空間的相應(yīng)增加。 { 先訪問右子樹根節(jié)點(diǎn)；再遍歷右子樹根節(jié)點(diǎn)的左子樹，再遍歷右子樹根節(jié)點(diǎn)的右子樹；……直至遍歷完所有右子樹的節(jié)點(diǎn)}(2) 中序遍歷： 若二叉樹為空，則空操作；否則 ① 中序遍歷左子樹。 ③ 訪問根結(jié)點(diǎn)；（4）按層遍歷二叉樹：① 訪問根結(jié)點(diǎn)；②遍歷左子樹根結(jié)點(diǎn)；③遍歷右子樹根結(jié)點(diǎn)。 (1) 若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于樹根結(jié)點(diǎn)的關(guān)鍵字； (2) 若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的關(guān)鍵字均大于樹根結(jié)點(diǎn)的關(guān)鍵字； (3) 左、右子樹本身又各是一棵二叉搜索樹。v 由二叉搜索樹的定義可知，在一棵非空的二叉搜索樹中，其結(jié)點(diǎn)的關(guān)鍵字是按照左子樹、根和右子樹有序的，所以對(duì)它進(jìn)行中序遍歷得到的結(jié)點(diǎn)序列必然是一個(gè)有序序列。v 若二叉搜索樹是一棵理想平衡樹或接近理想平衡樹，則進(jìn)行查找的時(shí)間復(fù)雜度為O(log2n)，v 若為一棵單支樹(這是最極端和最差的情況)，則其時(shí)間復(fù)雜度為O(n)，v 一般情況而言，其時(shí)間復(fù)雜度可大致可看做為O(log2n)。二叉搜索樹查找的遞歸算法的空間復(fù)雜度平均情況為O(log2n)，最差情況為O(n)，非遞歸算法的空間復(fù)雜度為O(1)。(1) 若樹根結(jié)點(diǎn)存在左孩子，則樹根結(jié)點(diǎn)的值小于等于左孩子結(jié)點(diǎn)的值；(2) 若樹根結(jié)點(diǎn)存在右孩子，則樹根結(jié)點(diǎn)的值小于等于右孩子結(jié)點(diǎn)的值；(3) 以左、右孩子為根的子樹又同樣各是一個(gè)堆。v 若一棵完全二叉樹是堆，則該樹中以每個(gè)結(jié)點(diǎn)為根的子樹也都是一個(gè)堆。能采用給定的數(shù)據(jù)序列來生成一個(gè)堆（大根堆或小根堆）了解樹的帶權(quán)路徑，以及哈夫曼樹（最優(yōu)二叉樹）的概念和性質(zhì)(1) 路徑和路徑長(zhǎng)度若在一棵樹中存在著一個(gè)結(jié)點(diǎn)序列k1,k2,…,kj，使得ki是ki+1的雙親(1≤ij)，則稱此結(jié)點(diǎn)序列是從k1到kj的路徑。因樹中每個(gè)結(jié)點(diǎn)只有一個(gè)雙親結(jié)點(diǎn)，所以它也是這兩個(gè)結(jié)點(diǎn)之間的惟一路徑。 (2) 結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度 在許多應(yīng)用中，常常將樹中的結(jié)點(diǎn)賦予一個(gè)有著某種意義的實(shí)數(shù)，我們稱此實(shí)數(shù)為該結(jié)點(diǎn)的權(quán)。(3) 樹的帶權(quán)路徑長(zhǎng)度 樹的帶權(quán)路徑長(zhǎng)度定義為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記為： WPL= 其中n表示葉子結(jié)點(diǎn)的數(shù)目，wi和li分別表示葉子結(jié)點(diǎn)ki的權(quán)值和樹根結(jié)點(diǎn)到ki之間的路徑長(zhǎng)度。它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中，帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹。這樣圖的二元組定義可敘述為： 圖由頂點(diǎn)集(vertex set)和邊集(edge set)所組成。若頂點(diǎn)集為空，則邊集必然為空，若頂點(diǎn)集非空，則邊集可空可不空，當(dāng)邊集為空時(shí)，圖G中的頂點(diǎn)均為孤立頂點(diǎn)。設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的圖，頂點(diǎn)序號(hào)依次為0,1,2,…,n1，則G的鄰接矩陣是具有如下定義的n階方陣。 1, 對(duì)于無向圖，(vi,vj)或(vj, vi)206。 對(duì)于有向圖，vi, vj206。 0, 對(duì)應(yīng)邊不存在于E(G)中v 從鄰接矩陣中可查兩個(gè)結(jié)點(diǎn)的之間是否存在通路，若兩個(gè)結(jié)點(diǎn)的坐標(biāo)的交叉其值不為零并不是一個(gè)很大的值的話，則有通路，否則沒有通路。v 無向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣可能是不對(duì)稱的。v 在無向圖中, 統(tǒng)計(jì)第 i 行 (列)中 1 的個(gè)數(shù)可得頂點(diǎn)i 的度。v 圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)用于表示稠密圖能夠充分利用存儲(chǔ)空間，但若用于表示稀疏圖，則將使鄰接矩陣變?yōu)橄∈杈仃?，從而造成存?chǔ)空間的很大浪費(fèi)。鄰接表(adjacency list)是對(duì)圖中的每個(gè)頂點(diǎn)建立一個(gè)鄰接關(guān)系的單鏈表，并把它們的表頭指針用向量存儲(chǔ)的一種圖的表示方法。 vi鄰接表中的每個(gè)結(jié)點(diǎn)用來存儲(chǔ)以該頂點(diǎn)為端點(diǎn)或起點(diǎn)的一條邊的信息，因而被稱為邊結(jié)點(diǎn)。v 邊結(jié)點(diǎn)通常包含三個(gè)域：一是鄰接點(diǎn)域(adjvex)，用以存儲(chǔ)頂點(diǎn)vi的一個(gè)鄰接頂點(diǎn)vj的序號(hào)j；二是權(quán)域(weight)，用以存儲(chǔ)邊(vi, vj)或 vi, vj 上的權(quán)；三是鏈域(next)，用以鏈接vi鄰接表中的下一個(gè)邊結(jié)點(diǎn)。v 對(duì)于每個(gè)頂點(diǎn)vi的鄰接表，需要設(shè)置一個(gè)表頭指針，若圖G中有n個(gè)頂點(diǎn)，則就有n個(gè)表頭指針。這樣，圖G就可以由這個(gè)表頭向量來表示和存取。第八章 查找v 了解順序查找、二分查找以及索引查找等查找方法的原理，并熟悉應(yīng)用各方法的先決條件，查找的結(jié)束條件，適宜的存儲(chǔ)結(jié)構(gòu)以及表示各種查找方法性能的時(shí)間復(fù)雜度指標(biāo)v 了解散列存儲(chǔ)和散列函數(shù)的概念以及如何借助于散列存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)散列查找v 熟悉常用的幾種散列函數(shù)構(gòu)成法v 熟悉幾種解決散列存儲(chǔ)地址沖突的幾種方法，以及各方法的優(yōu)點(diǎn)與不足v 熟悉散列存儲(chǔ)的各項(xiàng)性能指標(biāo)（時(shí)間復(fù)雜度和平均查找長(zhǎng)度），并能結(jié)合具體的數(shù)據(jù)序列和沖突解決方法來計(jì)算相關(guān)性能指標(biāo)。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1