?、谏种械谝豢脴涞母Y點就是轉換后二叉樹的根結點，依次將后一棵樹作為前一棵樹根結點的右子樹。

　　二叉樹轉換為森林的步驟是:

　?、偕值谝豢脴涞母褪嵌鏄涞母?

　?、诙鏄涞淖笞訕滢D換為森林的第一棵樹，二叉樹的右子樹對應于森林中其余的樹;③二叉樹右子樹的根結點作為余下樹中第一棵樹的根結點……，以此類推。

　　五、圖

　　圖的概念

　　圖是一種較線性表和樹形結構更為復雜的數據結構。在線性表中每個數據元素只有一個(直接)前驅和后繼，即各數據元素之間僅有線性關系。在樹形結構中，數據元素之間有明顯的層次關系，每一層中的數據元素只和上一層中的一個元素(即雙親結點)相關。而在圖中，任意兩個數據元素之間均有可能相關。

　　圖(graph)是圖型結構的簡稱。它是一種復雜的非線性數據結構。圖在各個領域都有著廣泛的應用。圖的二元組定義為:

　　G=(V，E)

　　其中，V是非空的頂點集合，即

　　V={v i |1≤i≤n，n≥1，v i ∈elemtype，n為頂點數｝

　　E是V上二元關系的集合，一般只討論僅含一個二元關系的情況，且直接用E表示這個關系。這樣，E就是V上頂點的序偶或無序對(每個無序對(x，y)是兩個對稱序偶和的簡寫形式)的集合。對于V上的每個頂點，在E中都允許有任意多個前驅和任意多個后繼，即對每個頂點的前驅和后繼個數均不加限制。回顧一下線性表和樹的二元組定義，都是在其二元關系上規定了限制條件，線性表的限制條件是只允許每個結點有一個前驅和一個后繼，樹的限制條件是只允許每個結點有一個前驅。因此，圖比線性表和樹更具有廣泛性，它包含線性表和樹在內，線性表和樹可以認為是圖的簡單情況。

　　快速排序的基本思想是把表中某元素作為基準，將表劃分為大于該值和小于該值的兩部分，然后用遞歸的方法處理這兩個子表，直到完成整個表的排序?？焖倥判虻谋容^次數為(n-1)+(n-2)+…+1=n(n-1)/2，移動次數最多也是n(n-1)/2。如果每次的基準元素剛好是表的中值，使表分為大小相等的兩個子表，則比較次數為nlog 2 n;如果表已排好序，則移動次數為0。

　　6.常用排序方法的性能比較如下表所示:

　　常用排序方法的性能比較

　　排序方法 平均時間 最壞情況的時間 輔助存儲

　　冒泡法、直接選擇法、直接插入法 O(n2 ) O(n2 ) O(1)

　　快速排序 O(nlog2 n) O(n2 ) O(log2 n)

　　堆排序 O(nlog2n) O(nlog2 n) O(1)

　　歸并排序 O(nlog2 n) O(nlog2 n) O(n)

　　注:在上表中，我們將n(n-1)/2也記為O(n2 )。如果在待排序的表中含有多個碼值相同的記錄，經過排序后，這些記錄的相對次序不變，則稱這種排序方法是穩定的，否則是不穩定的。根據上述說法，可以看出直接插入法、歸并法是穩定的;而直接選擇法、冒泡法、快速排序法、堆排序法是不穩定的。

　　七、檢索

　　1.順序檢索

　　檢索又稱為查找。順序檢索是將待查找的關鍵碼值與線性表中個結點的關鍵碼值逐一比較，直到找到所需的記錄，檢索成功;或者在表中找不到所需記錄而檢索失敗。順序檢索不要求線性表事先排序。設線性表有n個元素，則最多檢索次數為n，最少檢索次數為1。

　　2.二分法檢索

　　二分法檢索要求線性表結點按關鍵排序且以順序方式存儲。在查找時，首先與表的中間位置上結點的關鍵值比較，若相等則檢索成功;否則根據比較結果確定下一步在表的前半部或后半部中繼續進行。二分法檢索的效率較主動，設線性表有n個元素，則最多的檢索次數為大于log 2 n的最小整數，最少的檢索次數為1。

　　3.分塊檢索

　　分塊檢索把線性表分成若干塊，塊內結點不必有序，但塊與塊之間必須有序，即每一塊中各結點的關鍵值必須大于(或小于，與此類推)前一塊最大關鍵值。為加快查找，還要建立一個索引表，表中給出每一塊的最大關鍵值和指向塊內第一個結點位置的指針。分塊檢索分兩步進行，先查索引表，確定要找的記錄在哪一塊;然后再在相應的塊中檢索。分塊檢索適合于線性表很大，數據又是動態變化的情況。在查索引表時，可采用順序法或二分法;在塊內查找所求記錄時，采用順序法。由于分塊而縮小了查找范圍，從而加快檢索速。

　　4.散列表檢索

　　根據關鍵值，就可以迅速找到該記錄所對應的存儲位置，這就是建立在散列函數基礎上的散列檢索。設記錄的關鍵值為k，則該記錄的存儲位置可用散列函數H來計算H=H(k)。常用來產生的散列函數的方法是除余法，即取H(k)=k mod p設散列表長度為n，取p為小于n的最大素數。一般說來，關鍵碼值的集合比散列表存儲位的數目大得多，這正是體現散列表的優勢所在，但同時帶來了沖突問題，即不同的關鍵值經散列函數計算，可能得到相同的存儲位置。一個好的散列函數應該使沖突的可能性盡量小。最常用的解決沖突的方法是線性探測法，就是在發生沖突時，從H(k)以后的位置逐一探測，直至找到一個空位置，將新記錄插入;在檢索時，如果H(k)中不是所需關鍵值的記錄，也是從H(k)往下逐一搜索，直到找到所需關鍵值或查找失敗為止。應注意查找次序是:H(k)，H(k)+1，H(k)+2，…n-1，0，1，2，…，H(k)-1即在n-1以后，又從0開始，因為在位置上是循環的。雙重散列技術是對線性探測法的改進。它使用兩個散列函數H1和H2。對關鍵值k，計算H1(k)，求得0到n-1之間的一個散列地址;若在這個地址上沖突，下一個被探測的地址為(H1(k)+H2(k))mod n，關于選擇H2的方法在此不做討論。