【正文】 于2，并且最下一層上的所有結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。在下圖的4棵二叉樹中，分別是深度為3和4的完全二叉樹：滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍然是一棵完全二叉樹。在完全二叉樹中，若某個結(jié)點沒有左子結(jié)點，則它一定沒有右子結(jié)點，即該結(jié)點必是葉子結(jié)點。(3) 二叉樹的性質(zhì)假設定義根結(jié)點的層數(shù)為1(注意：有些資料中規(guī)定根結(jié)點的層數(shù)為0)。性質(zhì)1：在二叉樹的第i層上，最多有2i1(i≥1)個結(jié)點。性質(zhì)2：深度為k的二叉樹最多有2k1(k≥1)個結(jié)點。性質(zhì)3：在任意二叉樹中，若度為0的結(jié)點(即葉子結(jié)點)的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則：n0= n2+1(對于完全二叉樹還有如下屬性)性質(zhì)4：具有n個結(jié)點的完全二叉樹，其深度為[log2n]+1。注：[log2n]表示取log2n的整數(shù)部分。性質(zhì)5：如果將一棵有n個結(jié)點的完全二叉樹自頂向下、同一層自左向右連續(xù)給結(jié)點編號…、n，則對于任意結(jié)點i(1≤i≤n)有如下結(jié)論：1) 如果i=1，此結(jié)點為根結(jié)點，無前驅(qū)(即無父結(jié)點)；如果i1，則該結(jié)點的父結(jié)點編號為Int(i/2)。也可表示成[i/2]，都表示取整數(shù)。2) 如果2in，則結(jié)點i無左子結(jié)點，顯然也沒有右子結(jié)點，是葉子結(jié)點。如果2i≤n，則結(jié)點i的左子結(jié)點是編號為2i的結(jié)點。3) 如果2i+1n，則結(jié)點i無右子結(jié)點。如果2i+1≤n，則結(jié)點i的右子結(jié)點的編號為2i+1。(4) 二叉樹的遍歷二叉樹的遍歷就是遵從某種次序，訪問二叉樹中的所有結(jié)點，使得每個結(jié)點僅被訪問一次。一棵非空二叉樹是由根結(jié)點、左子樹和右子樹三部分組成。因此遍歷一棵非空二叉樹的問題就可以分解為三項“子任條”：① 訪問根結(jié)點(假設用D表示)。② 遍歷左子樹(假設用L表示)。③ 遍歷右子樹(假設用R表示)。在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。在先左后右的原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷可分為三種：前序遍歷(DLR)、中序遍歷(LDR)、后序遍歷(LRD)。 以下圖中的二叉樹為例： 前序遍歷(DLR)： 首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時，仍然先訪問子樹的根結(jié)點，然后遍歷其左子樹，最后遍歷其右子樹。即，前序遍歷是指訪問所有的根結(jié)點(包括子樹的根結(jié)點)都在遍歷其左、右子樹之前。 前序遍歷的操作： 若二叉樹為空，則結(jié)束反返回。否則： ① 訪問根結(jié)點② 前序遍歷左子樹③ 前序遍歷右子樹如，對上圖中的二叉樹進行前序遍歷的結(jié)果是：F C A D B E G H P 中序遍歷(LDR)： 首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷其左子樹，然后訪問子樹的根結(jié)點，最后遍歷其右子樹。即，中序遍歷是指訪問所有的根結(jié)點(包括子樹的根結(jié)點)都在遍歷其左子樹之后、在遍歷其右子樹之前。 中序遍歷的操作： 若二叉樹為空，則結(jié)束反返回。否則： ① 中序遍歷左子樹② 訪問根結(jié)點③ 中序遍歷右子樹如，對上圖中的二叉樹進行中序遍歷的結(jié)果是：A C B D F E H G P 后序遍歷(LRD)： 首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。在遍歷左、右子樹時，仍然先遍歷其左子樹，然后遍歷其右子樹，最后訪問子樹的根結(jié)點。即，后序遍歷是指訪問所有的根結(jié)點(包括子樹的根結(jié)點)都在遍歷其左、右子樹之后。 后序遍歷的操作： 若二叉樹為空，則結(jié)束反返回。否則： ① 后序遍歷左子樹② 后序遍歷右子樹③ 訪問根結(jié)點如，對上圖中的二叉樹進行后序遍歷的結(jié)果是：A B D C H P G E F查找又稱檢索。查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。通常，根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，應采用不同的查找方法。 順序查找順序查找又稱順序搜索或線性查找。順序查找一般是指在線性表中查找指定的元素。順序查找的基本思想：在n個結(jié)點組成的線性表中，從線性表的一端開始，依次將線性表中的元素與被查元素進行比較，若相等則表示找到，即查找成功；若線性表中所有的元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找的元素，即查找失敗。在順序查找中，查找成功時最多需要比較n次、最少比較1次、平均比較次數(shù)約為表長的一半。查找失敗時比較n+1次。順序查找的時間復雜度為O(n)。對于無序表(即表中的元素的排列是無序的)和鏈式存儲結(jié)構(gòu)的線性表(有序的和無序的)，只能用順序查找。順序查找的優(yōu)點：算法簡單而適用范圍廣。對表中元素的排列次序無要求，既可以是按關(guān)鍵字排列的有序表，也可以是無序表；對表的存儲結(jié)構(gòu)也無任何要求，既適用于順序存儲的順序表，也適用于鏈接存儲的鏈表。 順序查找的缺點： 查找效率低，平均查找長度較大。當n很大時不宜采用順序查找。 二分查找二分查找又稱折半查找。它是一種查找效率較高的查找方法。該方法只適用于順序存儲結(jié)構(gòu)的有序表。通常是指有序表中的元素按值升序排列(非遞減有序排列)。二分查找不能用于鏈式存儲結(jié)構(gòu)的線性表。 二分查找的基本思想：參見“C語言程序設計”或“VB程序設計”課件的相應內(nèi)容動畫。 對于長度為n的有序線性表，查找成功時最多需要比較log2(n+1)次、最少比較1次、平均查找長度近似log2n。當查找失敗時，比較log2n或log2(n+1)次。 不管二分查找成功與否，其時間復雜度均為O(log2n)。 二分查找的最壞性能和平均性能相當接近。 排序 排序就是將文件中的記錄進行整理，使之按照關(guān)鍵字進行遞增或遞減的順序排列起來，成為一個有序序列的過程。在本節(jié)所介紹的排序方法中，其排序的對象一般認為是順序存儲的線性表，在程序設計語言中就是一維數(shù)組。 這里的排序算法，都是針對升序排序。 交換排序 交換排序是兩兩比較待排序記錄的關(guān)鍵字，若發(fā)現(xiàn)兩個記錄關(guān)鍵字的次序相反時即進行交換，直到?jīng)]有反序的記錄為止。下面介紹兩種常用的交換排序。(1) 冒泡排序冒泡排序的基本思想：參見“C語言程序設計”或“VB程序設計”課件的相應內(nèi)容動畫。 對于長度為n的線性表，在最壞情況下，冒泡排序需要經(jīng)過n/2遍的掃描，比較次數(shù)為n(n1)/2。 冒泡排序算法的平均時間復雜度為O(n2)，空間復雜度為O(1)。(2) 快速排序快速排序的基本思想： 參見下圖： 從線性表中選取一個元素，設為T，將線性表后面小于T的元素移到前面，將線性表前面大于T的元素移到后面，結(jié)果就把線性表分成了兩部分(稱為兩個子表)，T插入到其分界線的位置處，這個過程稱為線性表的分割。通過對線性表的一次分割，就以T為分界線，將線性表分成了前后兩個子表，且前面子表中的所有元素均不大于T，后面子表中的所有元素均不小于T。 如果對分割后的各子表再按上述原則進行分割，并且這種分割過程可以一直做下去，隨著對各子表不斷地進行分割，劃分出的子表會越來越多(一次只能對一個子表進行再分割處理)，直到所有子表中的元素都排好序為止，則此時的線性表就變成了有序表。 對于長度為n的線性表：在最壞情況下，快速排序比較次數(shù)為n(n1)/2。算法的時間復雜度為O(n2)，空間復雜度為O(n)。 在最好情況下，快速排序算法的時間復雜度為O(nlog2n)，空間復雜度為O(log2n)?？焖倥判蛩惴ǖ钠骄鶗r間復雜度是O(nlog2n)，平均比較次數(shù)不大于(n+1)log2n 插入排序 插入排序是每次將一個待排序的記錄按其關(guān)鍵字大小，插入到前面已排好的序列中的適當