【正文】 非空樹，左子樹和右子樹又同樣都是一棵二叉樹。,也就是說，當(dāng)i為偶數(shù)時，其雙親結(jié)點(diǎn)的編號為i/2，它是雙親結(jié)點(diǎn)的左孩子，當(dāng)i為奇數(shù)時，其雙親結(jié)點(diǎn)的編號為(i1)/2，它是雙親結(jié)點(diǎn)的右孩子。理想平衡二叉樹：在一棵二叉樹中，若除最后一層外，其余層都是滿的，而最后一層上的結(jié)點(diǎn)可以任意分布，則稱此樹為理想平衡二叉樹,簡稱理想平衡樹或理想二叉樹。二叉搜索樹查找的遞歸算法的空間復(fù)雜度平均情況為O(log2n)，最差情況為O(n)，非遞歸算法的空間復(fù)雜度為O(1)。這樣圖的二元組定義可敘述為： 圖由頂點(diǎn)集(vertex set)和邊集(edge set)所組成。v 圖的鄰接矩陣存儲結(jié)構(gòu)用于表示稠密圖能夠充分利用存儲空間，但若用于表示稀疏圖，則將使鄰接矩陣變?yōu)橄∈杈仃?，從而造成存儲空間的很大浪費(fèi)。第八章 查找v 了解順序查找、二分查找以及索引查找等查找方法的原理，并熟悉應(yīng)用各方法的先決條件，查找的結(jié)束條件，適宜的存儲結(jié)構(gòu)以及表示各種查找方法性能的時間復(fù)雜度指標(biāo)v 了解散列存儲和散列函數(shù)的概念以及如何借助于散列存儲結(jié)構(gòu)來實(shí)現(xiàn)散列查找v 熟悉常用的幾種散列函數(shù)構(gòu)成法v 熟悉幾種解決散列存儲地址沖突的幾種方法，以及各方法的優(yōu)點(diǎn)與不足v 熟悉散列存儲的各項性能指標(biāo)（時間復(fù)雜度和平均查找長度），并能結(jié)合具體的數(shù)據(jù)序列和沖突解決方法來計算相關(guān)性能指標(biāo)。v 無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣可能是不對稱的。(3) 樹的帶權(quán)路徑長度 樹的帶權(quán)路徑長度定義為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，通常記為： WPL= 其中n表示葉子結(jié)點(diǎn)的數(shù)目，wi和li分別表示葉子結(jié)點(diǎn)ki的權(quán)值和樹根結(jié)點(diǎn)到ki之間的路徑長度。v 由二叉搜索樹的定義可知，在一棵非空的二叉搜索樹中，其結(jié)點(diǎn)的關(guān)鍵字是按照左子樹、根和右子樹有序的，所以對它進(jìn)行中序遍歷得到的結(jié)點(diǎn)序列必然是一個有序序列。+1熟悉滿二叉樹、完全二叉樹以及平衡二叉樹等幾種特殊的二叉樹的性質(zhì)、特點(diǎn)，并能根據(jù)這些性質(zhì)進(jìn)行相關(guān)的推理和計算滿二叉樹:叉樹每層的結(jié)點(diǎn)數(shù)達(dá)到最大值。 (2) 若n為奇數(shù)，則樹中每個分支結(jié)點(diǎn)都既有左孩子，又有右孩子；若n為偶數(shù)，則編號最大的分支結(jié)點(diǎn)（編號為n/2）只有左孩子，沒有右孩子，其余分支結(jié)點(diǎn)左、右孩子都有。x 249。熟悉樹的性質(zhì)，并能根據(jù)這些性質(zhì)進(jìn)行相關(guān)推理和計算v 性質(zhì)1: 樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。向隊列中插入新元素稱為進(jìn)隊或入隊，新元素進(jìn)隊后就成為新的隊尾元素；從隊列中刪除元素稱為離隊或出隊，元素離隊后，其后繼元素就成為隊首元素。循環(huán)鏈表和單鏈表的差別僅在于鏈表中最后一個結(jié)點(diǎn)的指針域不為“NULL”，而是指向頭一個結(jié)點(diǎn)，成為一個由鏈指針鏈結(jié)的環(huán)。了解時間復(fù)雜度的概念、時間復(fù)雜度的度量、時間復(fù)雜度的類型，能對實(shí)際的程序分析它的時間復(fù)雜度。數(shù)據(jù)結(jié)構(gòu)的二元組定義，能根據(jù)給出的二元組來判斷數(shù)據(jù)的邏輯結(jié)構(gòu)類型。v 在鏈?zhǔn)酱鎯Ψ绞街?，要求每個結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域（或稱為信息域）；另一部分用于存放指針，稱為指針域。 了解線性表的順序與鏈?zhǔn)酱鎯υ诓煌僮鲌龊舷碌臅r間復(fù)雜度指標(biāo)順序表是隨機(jī)存儲結(jié)構(gòu)，表中任一數(shù)據(jù)元素都可以通過計算直接得到地址進(jìn)行存取，時間復(fù)雜度為O(1)。v 兄弟結(jié)點(diǎn)(sibling)：同一個雙親的孩子之間互為兄弟。logk(n(k1)+1)249。 由于在二叉樹中，任一結(jié)點(diǎn)的度數(shù)小于或等于2，所以其結(jié)點(diǎn)總數(shù)n為: n = n0 + n1 + n2 (n0 :終端結(jié)點(diǎn)。log2nlchilddataparentrchild熟悉二叉樹的4種遍歷方法，能按任何一種遍歷方法來寫出給定樹的遍歷序列(1) 先序遍歷：若二叉樹為空，則空操作；否則① 訪問根結(jié)點(diǎn)； ② 先序遍歷左子樹； { 先訪問左子樹根節(jié)點(diǎn)；再遍歷左子樹根節(jié)點(diǎn)的左子樹，再遍歷左子樹根節(jié)點(diǎn)的右子樹；……直至遍歷完所有左子樹的節(jié)點(diǎn)}③ 先序遍歷右子樹。v 堆頂結(jié)點(diǎn)具有最小值(——對應(yīng)于小根堆）或最大值（—— 對應(yīng)于大根堆)。 236。v vi鄰接表中的結(jié)點(diǎn)數(shù)，對于無向圖來說，等于vi的邊數(shù)，或鄰接點(diǎn)數(shù)或度數(shù)；對于有向圖來說，等于vi的出邊數(shù)、或出邊鄰接點(diǎn)數(shù)或出度數(shù)。在這三個域中，鄰接點(diǎn)域和鏈域是必不可少的，權(quán)域可根據(jù)情況取舍，若表示的是無權(quán)圖，則可省去此域。E(G)； A[i,j]= 237。也就是說，在二叉樹中，一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)之間的分支構(gòu)成這兩個結(jié)點(diǎn)之間的路徑。 （遍歷的過程與先根級的遞歸遍歷類似） ② 訪問根結(jié)點(diǎn)； ③ 中序遍歷右子樹 （遍歷過程與先根級的遞歸遍歷相同）(3) 后序遍歷：若二叉樹為空，則空操作；否則 ① 后序遍歷左子樹； ② 后序遍歷右子樹。 此性質(zhì)可以從樹的相應(yīng)性質(zhì)中直接導(dǎo)出，也可以進(jìn)行如下證明。n/2 證明：設(shè)k叉樹的最小深度為h，則： 前h1層滿的 k叉樹結(jié)點(diǎn)數(shù) n≤ h層都滿的k叉樹結(jié)點(diǎn)數(shù)，因此有： 上式可變換為： kh1 n (k1)+1 ≤ kh 以k為底取對數(shù)可得： h1 logk( n(k1)+1) ≤h 即： logk( n(k1)+1) ≤h logk( n(k1)+1)+1因k只能為整數(shù)，所以： h=233。v 子孫結(jié)點(diǎn)：每個結(jié)點(diǎn)的所有子樹中的結(jié)點(diǎn)被