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