[it認證]java語言程序設(shè)計應(yīng)試輔導二級-資料下載頁
2025-01-16 03:43本頁面
【正文】 log2n]+1。性質(zhì)6 設(shè)完全二叉樹共有n個結(jié)點，如果從根結(jié)點開始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點進行編號，則對于編號為k（k=1，2，…，n）的結(jié)點有以下結(jié)論。若k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若k1，則該結(jié)點的父結(jié)點編號為INT（k/2）。若2k≤n，則編號為k的結(jié)點的左子結(jié)點編號為2k；否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。若2k+1≤n，則編號為k的結(jié)點的右子結(jié)點編號為2k+1；否則該結(jié)點無右子結(jié)點。根據(jù)完全二叉樹的這個性質(zhì)，如果按從上到下、從左到右的順序存儲完全二叉樹的各結(jié)點，則很容易確定每一個結(jié)點的父結(jié)點、左子結(jié)點和右子結(jié)點的位置。（3）二叉樹的存儲結(jié)構(gòu)在計算機中，二叉樹通常采用鏈式存儲結(jié)構(gòu)。與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點也由兩部分組成：數(shù)據(jù)域與指針域。但在二叉樹中，由于每一個元素可以有兩個后件（即兩個子結(jié)點），因此，用于存儲二叉樹的存儲結(jié)點的指針域有兩個：一個用于指向該結(jié)點的左子結(jié)點的存儲地址，稱為左指針域；另一個用于指向該結(jié)點的右子結(jié)點的存儲地址，稱為右指針域。由于二叉樹的存儲結(jié)構(gòu)中每一個存儲結(jié)點有兩個指針域，因此，二叉樹的鏈式存儲結(jié)構(gòu)也稱為二叉鏈表。對于滿二叉樹與完全二叉樹來說，根據(jù)完全二叉樹的性質(zhì)6，可以按層序進行順序存儲，這樣，不僅節(jié)省了存儲空間，又能方便地確定每一個結(jié)點的父結(jié)點與左右子結(jié)點的位置。但順序存儲結(jié)構(gòu)對于一般的二叉樹不適用。（4）二叉樹的遍歷二叉樹的遍歷是指不重復地訪問二叉樹中的所有結(jié)點。① 前序遍歷（DLR）前序遍歷是指在訪問根結(jié)點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。因此，前序遍歷二叉樹的過程是一個遞歸的過程。② 中序遍歷（LDR）中序遍歷是指在訪問根結(jié)點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。因此，中序遍歷二叉樹的過程也是一個遞歸的過程。③ 后序遍歷（LRD）后序遍歷是指在訪問根結(jié)點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。因此，后序遍歷二叉樹的過程也是一個遞歸的過程。7．查找技術(shù)（1）順序查找順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下。從線性表的第一個元素開始，依次將線性表中的元素與被查找元素進行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查找元素進行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失?。Ｔ谶M行順序查找過程中，如果線性表中的第一個元素就是被查找元素，則只需做一次比較就查找成功，查找效率很高；但如果被查的元素是線性表中的最后一個元素，或者被查元素根本不在線性表中，則為了查找這個元素需要與線性表中所有的元素進行比較，這是順序查找的最壞情況。在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較。（2）二分查找二分查找只適用于順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）的。設(shè)有序線性表的長度為n，被查元素為x，則二分查找的方法如下。將x與線性表的中間項進行比較：若中間項的值等于x，則說明查到，查找結(jié)束；若x小于中間項的值，則在線性表的前半部分（即中間項以前的部分）以相同的方法進行查找；若x大于中間項的值，則在線性表的后半部分（即中間項以后的部分）以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0（說明線性表中沒有這個元素）為止。在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。8．排序技術(shù)（1）交換類排序所謂交換類排序是指借助數(shù)據(jù)元素之間的互相交換進行排序的一種方法。冒泡排序與快速排序?qū)儆诮粨Q類的排序方法。① 冒泡排序冒泡排序的基本過程如下。首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個逆序。顯然，在掃描過程中，不斷地將兩相鄰元素中的大者往后移動，最后就將線性表中的最大者換到了表的最后，這也是線性表中最大元素應(yīng)有的位置。然后，從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，后面的元素小于前面的元素，則將它們互換，這樣就又消去了一個逆序。顯然，在掃描過程中，不斷地將兩相鄰元素中的小者往前移動，最后就將剩下線性表中的最小者換到了表的最前面，這也是線性表中最小元素應(yīng)有的位置。對剩下的線性表重復上述過程，直到剩下的線性表變空為止，此時的線性表已經(jīng)變?yōu)橛行颉＜僭O(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要的比較次數(shù)為n(n–1)/2。但這個工作量不是必需的，一般情況下要小于這個工作量。② 快速排序快速排序的基本思想如下。從線性表中選取一個元素，設(shè)為T。然后將線性表后面小于T的元素移到前面，而前面大于T的元素移到后面，結(jié)果就將線性表分成了兩部分（稱為兩個子表），T插入到其分界線的位置處。這個過程稱為線性表的分割。通過對線性表的一次分割，就以T為分界線，將線性表分成了前后兩個子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。如果對分割后的各子表再按上述原則進行分割，并且，這種分割過程可以一直做下去，直到所有子表為空為止，則此時的線性表就變成了有序表。（2）插入類排序① 簡單插入排序所謂插入類排序，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。在線性表中，只包含第1個元素的子表顯然可以看成是有序表。接下來的問題是，從線性表的第2個元素開始直到最后一個元素，逐次將其中的每一個元素插入到前面已經(jīng)有序的子表中。一般來說，假設(shè)線性表中前j–1個元素已經(jīng)有序，現(xiàn)在要將線性表中第j個元素插入到前面的有序子表中，插入過程如下：首先將第j個元素放到一個變量T中。然后從有序子表的最后一個元素（即線性表中第j–1個元素）開始，往前逐個與T進行比較，將大于T的元素均依次向后移動一個位置，直到發(fā)現(xiàn)一個元素不大于T為止，此時就將T（即原線性表中的第j個元素）插入到剛移出的空位置上，有序子表的長度就變?yōu)閖了。在簡單插入排序中，每一次比較后最多移掉一個逆序，因此，這種排序方法的效率與冒泡排序法相同。在最壞情況下，簡單插入排序需要n(n–1)/2次比較。② 希爾排序希爾排序的基本思想如下。將整個無序序列分割成若干小的子序列分別進
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1