②抹線:抹去原二叉樹中所有結點與其右孩子的連線;
③旋轉:將虛線及有關實線逆時鐘旋轉約45度，并將幾個結點按層次排列。
9.二叉樹與森林之間的轉換
森林轉換為二叉樹的步驟是:
①將森林中的每棵樹轉換為二叉樹;
②森林中第一棵樹的根結點就是轉換后二叉樹的根結點，依次將后一棵樹作為前一棵樹根結點的右子樹。
二叉樹轉換為森林的步驟是:
①森林第一棵樹的根就是二叉樹的根;
②二叉樹的左子樹轉換為森林的第一棵樹，二叉樹的右子樹對應于森林中其余的樹;③二叉樹右子樹的根結點作為余下樹中第一棵樹的根結點……，以此類推。
五、圖
圖的概念
圖是一種較線性表和樹形結構更為復雜的數據結構。在線性表中每個數據元素只有一個（直接）前驅和后繼，即各數據元素之間僅有線性關系。在樹形結構中，數據元素之間有明顯的層次關系，每一層中的數據元素只和上一層中的一個元素（即雙親結點）相關。而在圖中，任意兩個數據元素之間均有可能相關。
圖（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中都允許有任意多個前驅和任意多個后繼，即對每個頂點的前驅和后繼個數均不加限制?；仡櫼幌戮€性表和樹的二元組定義，都是在其二元關系上規(guī)定了限制條件，線性表的限制條件是只允許每個結點有一個前驅和一個后繼，樹的限制條件是只允許每個結點有一個前驅。因此，圖比線性表和樹更具有廣泛性，它包含線性表和樹在內，線性表和樹可以認為是圖的簡單情況。來源：www.examda.com
對于一個圖G，若E是序偶的集合，則每個序偶對應圖形中的一條有向邊，若E是無序對的集合，則每個無序對對應圖形中的一條無向邊，所以可把E看作為邊的集合。這樣，圖的二元組定義可敘述為:圖的非空頂點集（vertexset）和邊集（edgeset）所組成。針對圖G，頂點集和邊集可分別記為V（G）和E（G）。邊集E（G）允許是空集，若是空集，圖G中的頂點均為孤立頂點。對于一個圖G，若邊集E（G）為有向邊的集合，則稱此圖為有向圖（digraph），若邊集E（G）為無向邊的集合，則稱此圖為無向圖（undigraph）。
六、排序
1.直接插入排序
直接插入排序的基本思想是把表中元素依次插入一個已排好序的表中，就像人們打撲克摸牌時把牌插入手中的若干張牌里一樣。表中n個元素依次插入的比較次數為1+2+3+…+（n-1）=n（n-1）/2。在插入時，元素的移動次數最多為1+2+3+…+（n-1）=n（n-1）/2。如果表中元素已排好序，則只需比較n-1次，而移動次數為0。
2.直接選擇排序
直接選擇排序的基本思想是在表的n個元素中，經過n-1次比較得到其值（或最小值，下同），這就排好了第一個元素;再經過n-2次比較得到余下元素中的值，這就排好了第二個元素…直到比較1次后排好第n-1個元素，第n個元素的位置也就自然確定了。所需的比較次數為（n-1）+（n-2）++1=n（n-1）/2。所需移動次數最多也為n（n-1）/2。如果表中元素排好序，也需要比較n（n-1）/2次，而移動次數為0。
3.冒泡排序
冒泡排序的基本思想是將表中元素兩個相鄰元素依次比較，若不符合排序要求，則交換位置，這樣經過n-1次比較后，將確定出（或最?。┰氐奈恢?，這稱為一趟掃描。經過n-1次掃描后，就完成了整個表的排序。第一趟掃描的比較次數是n-1，第二趟掃描的比較次數是n-2……，總的比較次數是（n-1）+（n-2）+……+1=n（n-1）/2。如果恰好表中元素按反序排列，則需要移動的次數為3×n（n-1）/2。如果表中元素已排好序，并采用交換標志來表示并未發(fā)生過交換，則只需一趟掃描，只比較n-1次，就夠了;當然，移動次數也是0。
4.歸并排序
歸并排序的基本思想是表中元素兩兩比較排序，使表中的n個元素變成n/2個已排序的組，再兩兩組比較，而變成n/4個已排序的組……，直到表中只含有一個已排序的組，即完成排序。所需要的比較次數為nlog 2 n，移動次數為n。若表已排好序，則比較次數仍為nlog 2 n，但移動次數為0。
5.快速排序
快速排序的基本思想是把表中某元素作為基準，將表劃分為大于該值和小于該值的兩部分，然后用遞歸的方法處理這兩個子表，直到完成整個表的排序?？焖倥判虻谋容^次數為（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 ）。如果在待排序的表中含有多個碼值相同的記錄，經過排序后，這些記錄的相對次序不變，則稱這種排序方法是穩(wěn)定的，否則是不穩(wěn)定的。根據上述說法，可以看出直接插入法、歸并法是穩(wěn)定的;而直接選擇法、冒泡法、快速排序法、堆排序法是不穩(wěn)定的。
七、檢索
1.順序檢索
檢索又稱為查找。順序檢索是將待查找的關鍵碼值與線性表中個結點的關鍵碼值逐一比較，直到找到所需的記錄，檢索成功;或者在表中找不到所需記錄而檢索失敗。順序檢索不要求線性表事先排序。設線性表有n個元素，則最多檢索次數為n，最少檢索次數為1。
2.二分法檢索
二分法檢索要求線性表結點按關鍵排序且以順序方式存儲。在查找時，首先與表的中間位置上結點的關鍵值比較，若相等則檢索成功;否則根據比較結果確定下一步在表的前半部或后半部中繼續(xù)進行。二分法檢索的效率較主動，設線性表有n個元素，則最多的檢索次數為大于log 2 n的最小整數，最少的檢索次數為1。
3.分塊檢索
分塊檢索把線性表分成若干塊，塊內結點不必有序，但塊與塊之間必須有序，即每一塊中各結點的關鍵值必須大于（或小于，與此類推）前一塊關鍵值。為加快查找，還要建立一個索引表，表中給出每一塊的關鍵值和指向塊內第一個結點位置的指針。分塊檢索分兩步進行，先查索引表，確定要找的記錄在哪一塊;然后再在相應的塊中檢索。分塊檢索適合于線性表很大，數據又是動態(tài)變化的情況。在查索引表時，可采用順序法或二分法;在塊內查找所求記錄時，采用順序法。由于分塊而縮小了查找范圍，從而加快檢索速。
4.散列表檢索
根據關鍵值，就可以迅速找到該記錄所對應的存儲位置，這就是建立在散列函數基礎上的散列檢索。設記錄的關鍵值為k，則該記錄的存儲位置可用散列函數H來計算H=H（k）。常用來產生的散列函數的方法是除余法，即取H（k）=k mod p設散列表長度為n，取p為小于n的素數。一般說來，關鍵碼值的集合比散列表存儲位的數目大得多，這正是體現(xiàn)散列表的優(yōu)勢所在，但同時帶來了沖突問題，即不同的關鍵值經散列函數計算，可能得到相同的存儲位置。一個好的散列函數應該使沖突的可能性盡量小。最常用的解決沖突的方法是線性探測法，就是在發(fā)生沖突時，從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開始，因為在位置上是循環(huán)的。雙重散列技術是對線性探測法的改進。它使用兩個散列函數H1和H2。對關鍵值k，計算H1（k），求得0到n-1之間的一個散列地址;若在這個地址上沖突，下一個被探測的地址為（H1（k）+H2（k））mod n，關于選擇H2的方法在此不做討論。