【正文】 親結(jié)點(diǎn)的左孩子，當(dāng)i為奇數(shù)時(shí)，其雙親結(jié)點(diǎn)的編號(hào)為(i1)/2，它是雙親結(jié)點(diǎn)的右孩子。即2i≤n，則編號(hào)為i的結(jié)點(diǎn)為分支結(jié)點(diǎn)，否則為葉子結(jié)點(diǎn)。v 二叉樹(shù)的遞歸定義為：二叉樹(shù)或者是一棵空樹(shù)，或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的分別稱做根的左子樹(shù)和右子樹(shù)所組成的非空樹(shù)，左子樹(shù)和右子樹(shù)又同樣都是一棵二叉樹(shù)。logk( n(k1)+1)249。 假設(shè)第i1層(i1)命題成立，該層上有ki2 個(gè)結(jié)點(diǎn)。有序樹(shù)：結(jié)點(diǎn)的子樹(shù)從左到右有序安排。v 樹(shù)的度：一棵樹(shù)上所有結(jié)點(diǎn)的度的最大值就是這棵樹(shù)的度。但在動(dòng)態(tài)鏈表中進(jìn)行插入和刪除結(jié)點(diǎn)時(shí)，不需要移動(dòng)結(jié)點(diǎn)，只需要修改指針。除了線性表第一個(gè)數(shù)據(jù)元素作為該鏈表的頭結(jié)點(diǎn)外，在某些線性鏈表存儲(chǔ)結(jié)構(gòu)中，還可在單鏈表第一個(gè)結(jié)點(diǎn)之前附加一個(gè)同結(jié)構(gòu)結(jié)點(diǎn)，稱為附加頭結(jié)點(diǎn)。v 插入、刪除運(yùn)算靈活方便，不需移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中指針域的值即可了解單鏈表、雙向鏈表和循環(huán)鏈表的結(jié)構(gòu)和特點(diǎn)通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起的結(jié)點(diǎn)序列我們就稱為鏈表。v 所有數(shù)據(jù)元素ai在同一個(gè)線性表中必須是相同的數(shù)據(jù)類(lèi)型。這個(gè)取值函數(shù)也稱為散列函數(shù)。第一章 緒 論數(shù)據(jù)結(jié)構(gòu)的主要研究?jī)?nèi)容①數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)關(guān)系之間的邏輯關(guān)系 ②數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示 數(shù)據(jù)邏輯結(jié)構(gòu)的種類(lèi)：集合、線性表、樹(shù)和圖的性質(zhì)和特點(diǎn)。 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和總的數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系v 邏輯結(jié)構(gòu)相同，但存儲(chǔ)結(jié)構(gòu)不同，則認(rèn)為是不同的數(shù)據(jù)結(jié)構(gòu)。熟悉順序線性表（順序存儲(chǔ)的線性表）的存儲(chǔ)方式及其表單元（簡(jiǎn)單數(shù)據(jù)類(lèi)型和記錄數(shù)據(jù)類(lèi)型）的定位和計(jì)算。如果這一鏈表中每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，則稱該鏈表為線性鏈表或單鏈表，否則則稱為雙向鏈表。頭結(jié)點(diǎn)數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)如線性表的長(zhǎng)度等類(lèi)的附加信息；頭結(jié)點(diǎn)指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針(即第一個(gè)元素的存儲(chǔ)位置)。第四章 棧和隊(duì)列了解棧的定義及性質(zhì)棧（stack）又稱堆棧，它是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。 v 葉子結(jié)點(diǎn)：度為零的結(jié)點(diǎn)稱葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)。也即樹(shù)T中各子樹(shù)T1，T2，…，Tn的相對(duì)次序是有意義的。 對(duì)于第i層，最多結(jié)點(diǎn)數(shù)為：= ki1 命題得證。因此得到具有n個(gè)結(jié)點(diǎn)的一般k叉樹(shù)的最小深度為： 233。v 性質(zhì)1：在二叉樹(shù)第i 層上最多有2i1個(gè)結(jié)點(diǎn)( i≥1)。表達(dá)式235。此點(diǎn)也適合于一般二叉樹(shù)。log2(n+1)249。v 顯然，理想平衡樹(shù)包含滿二叉樹(shù)和完全二叉樹(shù)。熟悉樹(shù)的遍歷序列與樹(shù)結(jié)構(gòu)之間的關(guān)系，并能由特定的遍歷序列來(lái)恢復(fù)樹(shù)結(jié)構(gòu)和寫(xiě)出另外的遍歷序列熟悉樹(shù)與二叉樹(shù)的共性和差異之處熟悉樹(shù)的幾種遍歷算法能根據(jù)樹(shù)的定義（包括結(jié)點(diǎn)類(lèi)型的定義）編程實(shí)現(xiàn)樹(shù)的一些基本運(yùn)算第六章 二叉樹(shù)的應(yīng)用了解二叉搜索樹(shù)的定義，性質(zhì)并能根據(jù)定義由給定序列構(gòu)造二叉搜索樹(shù)v 二叉搜索樹(shù)(Binany Searching Tree)又稱做二叉排序樹(shù)(Binary Sorting Tree)，它或者是一棵空樹(shù)，或者是一棵具有如下特性的非空二叉樹(shù)。了解堆的定義和性質(zhì)堆(Heap)分為小根堆和大根堆兩種，對(duì)于一個(gè)小根堆，它是具有如下特性的一棵完全二叉樹(shù)。從k1到kj所經(jīng)過(guò)的分支數(shù)稱為這兩點(diǎn)之間的路徑長(zhǎng)度，它等于路徑上的結(jié)點(diǎn)數(shù)減1。針對(duì)圖G，頂點(diǎn)集和邊集可分別記為V(G)和E(G)。E(G) 238。v 圖的鄰接矩陣表示，需要使用一個(gè)二維數(shù)組存儲(chǔ)頂點(diǎn)之間相鄰的關(guān)系，為了存儲(chǔ)圖中n個(gè)頂點(diǎn)元素的信息，通常還需要使用一個(gè)一維數(shù)組，用數(shù)組中下標(biāo)為i的元素存儲(chǔ)頂點(diǎn)vi的信息。為了便于隨機(jī)訪問(wèn)任一頂點(diǎn)的鄰接表，需要把這n個(gè)表頭指針用一個(gè)向量(即一維數(shù)組)存儲(chǔ)起來(lái)，其中第i個(gè)分量存儲(chǔ)vi鄰接表的表頭指針。圖的邊集數(shù)組的定義v 能根據(jù)鄰接矩陣或鄰接表或邊集數(shù)組來(lái)得到圖的結(jié)構(gòu)v 熟悉圖的深度和廣度優(yōu)先遍歷的方法，并能根據(jù)相應(yīng)遍歷方法對(duì)給定的圖寫(xiě)出其遍歷序列v 了解圖的生成樹(shù)和最小生成樹(shù)的定義和性質(zhì)v 熟悉普里姆算法和克魯斯卡爾算法，并能寫(xiě)出根據(jù)給定的圖用這兩種算法之一來(lái)構(gòu)成最小生成樹(shù)的過(guò)程。v 為頂點(diǎn)vi建立的鄰接關(guān)系的單鏈表稱作vi鄰接表。若其值大于1則為該通路的權(quán)值。 了解圖的鄰接矩陣、鄰接表、逆鄰接表和十字鄰接表的定義及性質(zhì)鄰接矩陣(adjacency matrix)是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度規(guī)定為從樹(shù)根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積。 大根堆的定義與上述類(lèi)似，只要把小于等于改為大于等于就得到了。 在一個(gè)二叉搜索樹(shù)中，當(dāng)每個(gè)結(jié)點(diǎn)的元素類(lèi)型為簡(jiǎn)單類(lèi)型時(shí)，則結(jié)點(diǎn)的關(guān)鍵字就為該結(jié)點(diǎn)的值；當(dāng)結(jié)點(diǎn)的元素類(lèi)型為記錄類(lèi)型時(shí)，則結(jié)點(diǎn)的關(guān)鍵字為該結(jié)點(diǎn)的某一個(gè)域的值。其結(jié)點(diǎn)結(jié)構(gòu)為：Leftdataright其中data表示值域，用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素，left和right分別表示左指針域和右指針域，用以分別存儲(chǔ)左孩子和右孩子結(jié)點(diǎn)的存貯位置（即指針）v 鏈接存儲(chǔ)的另一種方法是：在上面的結(jié)點(diǎn)結(jié)構(gòu)中再增加一個(gè)parent指針域，用來(lái)指向其雙親結(jié)點(diǎn)。log2nlog2(n+1)249。表示對(duì)x進(jìn)行向下取整。性質(zhì)3：若二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)有n2個(gè),則有：n0=n2+1證明: (1)注： 233。 證明：利用性質(zhì) 2來(lái)證明，k 叉樹(shù)的最大結(jié)點(diǎn)數(shù)為每一層最大結(jié)點(diǎn)數(shù)之和，則有： 當(dāng)一棵k叉樹(shù)上的結(jié)點(diǎn)數(shù)等于 時(shí)，則稱該樹(shù)為滿k叉樹(shù)。 無(wú)序樹(shù)：結(jié)點(diǎn)的子樹(shù)順序任意。v 孩子結(jié)點(diǎn)(child) ：某結(jié)點(diǎn)子樹(shù)的根或者說(shuō)某個(gè)結(jié)