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