數(shù)據(jù)結(jié)構(gòu)與算法 課件 第4、5章 數(shù)組廣義表和串、樹與二叉樹

全國高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第四章數(shù)組、廣義表和串學(xué)習(xí)目標(biāo)掌握數(shù)組、廣義表和串的基本概念掌握數(shù)組按行主序及按列主序的存儲(chǔ)方式及二維數(shù)組地址計(jì)算方法掌握特殊矩陣的存儲(chǔ)方式及相應(yīng)的地址計(jì)算方法理解廣義表的概念，掌握廣義表的表示及基本運(yùn)算了解模式匹配概念，掌握串的模式匹配算法本章主要內(nèi)容數(shù)組及廣義表12串第一節(jié)

數(shù)組及廣義表數(shù)組是程序設(shè)計(jì)語言中的重要語法成分，很多語言都定義了數(shù)組類型以C語言為例，它定義了一維數(shù)組，數(shù)組元素還可以是數(shù)組，由此得到數(shù)組的數(shù)組，即多維數(shù)組一般地將n（n≥2）維數(shù)組看作是n-1維數(shù)組的數(shù)組從數(shù)據(jù)結(jié)構(gòu)的角度來理解，一維數(shù)組可以作為線性表的存儲(chǔ)結(jié)構(gòu)，數(shù)組中保存的各元素可以組成一個(gè)線性表多維數(shù)組在系統(tǒng)內(nèi)部都對(duì)應(yīng)一個(gè)隱含的一維數(shù)組，所以多維數(shù)組也是一種線性表例如二維數(shù)組就是以一維數(shù)組為元素的線性表數(shù)組的每個(gè)元素都是形如(index,value)的二元對(duì)，index是數(shù)組下標(biāo)，也稱為索引，value是對(duì)應(yīng)于該下標(biāo)的數(shù)值任何兩個(gè)元素的index值都不相同數(shù)組的基本操作Create(); //創(chuàng)建一個(gè)空的數(shù)組Store(index,value);//添加數(shù)據(jù)(index,value)//同時(shí)刪除有相同index值的數(shù)據(jù)對(duì)（若存在）Retrieve(index);//返回下標(biāo)為index的value值例4-1用數(shù)組表示一個(gè)星期每天的最高溫度hightem={(星期日,30),(星期一,28),(星期二,29),(星期三,32),(星期四,28),(星期五,30),(星期六,31)}數(shù)組上的操作Store(星期一,29);Retrieve(星期五);也可以約定使用0到6來分別表示星期日到星期六，此時(shí)，數(shù)組hightem可表示為hightem={(0,30),(1,28),(2,29),(3,32),(4,28),(5,30),(6,31)}數(shù)組的順序存儲(chǔ)方式數(shù)組的順序存儲(chǔ)有兩種形式。以二維數(shù)組為例，它的元素可以按行排列，也可以按列排列所謂按行排列，就是先排數(shù)組的第一行，緊隨其后排第二行，依此類推所謂按列排列，就是先排數(shù)組的第一列，緊隨其后排第二列，依此類推最終都是將數(shù)組中的全部元素排列成一個(gè)序列C語言中多維數(shù)組下標(biāo)的形式：[i1][i2][i3]…[ik]ij（1≤j≤k）為非負(fù)整數(shù)聲明值為整型類型的k維數(shù)組DkArrayintDkArray[u1][u2][u3]…[uk];每一維的下標(biāo)取值范圍是：0≤ij<uj（1≤j≤k）數(shù)組最多可容納n=u1

u2

u3

…

uk個(gè)整數(shù)所需要的內(nèi)存空間sizeof(DkArray)=n

sizeof(int)個(gè)字節(jié)若開始地址為start，則占用的空間將延伸至start+sizeof(DkArray)-1。intD2Array[3][6];對(duì)應(yīng)一個(gè)3行6列的矩陣通常int占4個(gè)字節(jié)數(shù)組D2Array中含有18個(gè)元素共占用18

4=76個(gè)字節(jié)編號(hào)對(duì)上述的下標(biāo)表格按行自上而下、同一行中自左至右進(jìn)行連續(xù)編號(hào)，從0開始按行優(yōu)先把二維數(shù)組中的下標(biāo)映射到0到n-1之間的某個(gè)整數(shù)的方式稱為行主序，也稱為行主映射按列優(yōu)先，對(duì)下標(biāo)表格從第一列開始，從上到下進(jìn)行連續(xù)編號(hào)，直到最后一列映射函數(shù)行主序所對(duì)應(yīng)的映射函數(shù)為 map(i1,i2)=i1

u2+i2

其中u2是數(shù)組的列數(shù)列主序所對(duì)應(yīng)的映射函數(shù)為 map(i1,i2)=i2

u1+i1

其中u1是數(shù)組的行數(shù)例4-3二維數(shù)組A[10][5]采用行主序方式存儲(chǔ)，每個(gè)數(shù)據(jù)元素占4個(gè)存儲(chǔ)單元，若A[0][4]的存儲(chǔ)地址是1000，則A[8][4]的存儲(chǔ)地址是多少？解：給定的數(shù)組A是10行5列，需要從A[0][4]的存儲(chǔ)地址反推出數(shù)組A的首地址，然后再計(jì)算A[8][4]的存儲(chǔ)地址行主序所對(duì)應(yīng)的映射函數(shù)為map(i1,i2)=i1

u2+i2本題中：u2=5，map(0,4)=4每個(gè)元素占4個(gè)存儲(chǔ)單元 A[0][0]的存儲(chǔ)地址=1000-4

4=984根據(jù)計(jì)算公式，A[8][4]的映射編號(hào)是 map(8,4)=8

5+4=44存儲(chǔ)地址為984+44

4=1160換一種計(jì)算方法A[0][4]和A[8][4]之間的元素個(gè)數(shù)是 8

5=40A[0][4]與A[8][4]之間的偏移量 =40

4A[8][4]的存儲(chǔ)地址 =A[0][4]的存儲(chǔ)地址+ A[0][4]與A[8][4]之間的偏移量 =1000+160=1160示例三維數(shù)組D3Array[3][2][4]按行主序下標(biāo)排列的形式對(duì)于三維數(shù)組ThrDimenArray[u1][u2][u3]，其行主序的映射函數(shù)應(yīng)為 map(i1,i2,i3)=i1

u2

u3+i2

u3+i3排列規(guī)律所有第一維值為i1的元素都排在第一維值大于i1的元素之前。第一維值相同的元素?cái)?shù)目為u2

u3。因此第一維值小于i1的元素?cái)?shù)目為i1

u2

u3，第一維值等于i1且第二維值小于i2的元素?cái)?shù)目為i2

u3，第一維值等于i1第二維值等于i2且第三維值小于i3的元素?cái)?shù)目為i3矩陣的壓縮存儲(chǔ)對(duì)稱矩陣和三角矩陣從節(jié)省存儲(chǔ)空間的角度考慮，對(duì)稱矩陣和上（下）三角矩陣，都可以只保存矩陣中約一半的元素，從而可以節(jié)省差不多一半的存儲(chǔ)空間這樣的存儲(chǔ)形式稱為壓縮存儲(chǔ)壓縮存儲(chǔ)對(duì)于對(duì)稱矩陣，因?yàn)閷?duì)角線以上及以下的元素對(duì)稱相等，所以只需要保存其中的一半及對(duì)角線上的元素即可對(duì)于上三角矩陣或下三角矩陣，僅保存上三角部分或下三角部分的元素，另外一半的零元素不再保存若矩陣有n行n列，則這三種形式下需要保存的元素個(gè)數(shù)為n

(n+1)/2三角部分

例4-4設(shè)有一個(gè)10行10列的下三角矩陣A，采用行優(yōu)先壓縮存儲(chǔ)方式，保存A中第一個(gè)元素a00的地址是100，保存a11的地址是108，則保存元素a44的地址是（）A．115B．156C．160D．212答案為B稀疏矩陣稀疏矩陣該矩陣只有10個(gè)非零元素，每個(gè)非零元素用一個(gè)三元組表示三元組表三元組表應(yīng)是一個(gè)有序序列，通常按行主序次序排列，即先按行的大小排列，同一行的三元組再按列的大小排列對(duì)應(yīng)前例的三元組表i0012234455j1200521405v891-3121624615-7稀疏矩陣的存儲(chǔ)結(jié)構(gòu)typedefstruct{ inti,j; //存儲(chǔ)非零元素的下標(biāo)

ELEMTypev; //存儲(chǔ)非零元素的值}triTerm;typedefstruct{ introws,cols; //矩陣的行數(shù)、列數(shù) intterms; //非零元素個(gè)數(shù)

triTermtri[maxSize]; //三元組表}SparseMatrix;輸入三元組生成三元組表的程序矩陣轉(zhuǎn)置矩陣轉(zhuǎn)置即是行、列互換，i行的元素放置到i列，這也意味著，j列的元素放置在j行。如果矩陣是n

m的，則轉(zhuǎn)置后得到的矩陣是m

n的很容易想到，將三元組表中的每個(gè)三元組項(xiàng)的i與j互換，即可得到轉(zhuǎn)置后矩陣的三元組表但是這樣轉(zhuǎn)換后得到的三元組表不再按行主序排列，不便于后續(xù)操作的實(shí)現(xiàn)所以要實(shí)現(xiàn)的矩陣轉(zhuǎn)置程序，必須得到一個(gè)按行主序排列的三元組表思路可以像readSparseMatrix函數(shù)那樣處理，讀入原矩陣的一個(gè)三元組，插入到目標(biāo)矩陣的三元組表中可以使用一個(gè)臨時(shí)計(jì)數(shù)數(shù)組，記錄原矩陣的每個(gè)三元組在目標(biāo)矩陣的三元組表中的插入位置，以輔助完成轉(zhuǎn)置操作，由此避免了三元組的移動(dòng)，高效率地實(shí)現(xiàn)轉(zhuǎn)置操作不失一般性，設(shè)原矩陣A的行數(shù)是rows，列數(shù)是cols。則轉(zhuǎn)置后矩陣B的行數(shù)是cols，列數(shù)是rows。三元組的個(gè)數(shù)沒有改變A中處于0列的元素，將是B中處于0行的元素。所以B的三元組表中的最前面的元素，是A中列值為0的元素。接下來是A中列值為1的元素，依此類推，最后是A中列值為cols-1的元素。使用臨時(shí)數(shù)組ColSize來保存統(tǒng)計(jì)結(jié)果前例中的矩陣，臨時(shí)數(shù)組ColSize內(nèi)容在B的三元組表中，為各行元素預(yù)留位置01234532201201234567890行元素1行元素2行元素4行元素5行元素對(duì)于A的三元組(0,1,8)和(4,1,24)，轉(zhuǎn)置后分別為(1,0,8)和(1,4,24)，它們應(yīng)該保存在上述第二部分，即位置3和位置4中故由ColSize數(shù)組中的元素值，從前向后依次相加，得到RowNext的值012345603577810轉(zhuǎn)置算法數(shù)組的應(yīng)用走迷宮是實(shí)驗(yàn)心理學(xué)中的一個(gè)經(jīng)典問題不失一般性，使用一個(gè)m行n列的矩陣maze表示迷宮，讓機(jī)器人R尋找從maze[0][0]（左上角，入口）到maze[m-1][n-1]（右下角，迷宮的唯一出口）間的可行路徑任一時(shí)刻，R在迷宮中的位置用行、列號(hào)[i][j]來表示，這時(shí)它有4個(gè)方向可以進(jìn)行試探，即從圖上看是上、下、左、右設(shè)下一位置是[g][h]，顯然[g][h]的值與走的方向有關(guān)若從[i][j]向右走一步，則g=i;h=j+1若向上走一步，則g=i-1;h=j當(dāng)R走到迷宮邊緣時(shí)，可以試探的方向不足4個(gè)，需要進(jìn)行邊界的判斷為了避免過多的邊界條件判斷，可以把原來表示迷宮的矩陣maze擴(kuò)大一圈，變成m+2行n+2列，并且令表示邊緣的這些矩陣元素全為1編寫計(jì)算機(jī)程序求解迷宮問題，一般采用一步一探查并加回溯的方法。稱R所在的位置為當(dāng)前位置，當(dāng)R走到一個(gè)位置時(shí)，除了進(jìn)入當(dāng)前位置的方向外，可以在其他3個(gè)方向進(jìn)行探查，選擇可行并尚未走過的方向走一步，所處的新位置變?yōu)楫?dāng)前位置，并再次探查下一個(gè)可行位置；當(dāng)3個(gè)方向都走不通時(shí)，只能沿來路退到前一個(gè)位置再選擇其他方向，這一步驟稱為回溯?；厮莺蟮奈恢糜肿?yōu)楫?dāng)前位置在探查的過程中，因?yàn)橛谢厮?，所以可能?huì)走到原來已走過的位置，為避免重復(fù)并找出確定的可行路徑，需要一個(gè)棧記錄已走過的每一步的位置及方向，另外還需要設(shè)置一個(gè)與原來迷宮矩陣同樣大小的標(biāo)志矩陣mark，以對(duì)走過的位置進(jìn)行標(biāo)記mark矩陣的初值全為0，當(dāng)R走到maze[i][j]位置時(shí)，則置mark[i][j]為1R走迷宮的步驟令R處在迷宮入口，此為當(dāng)前位置在當(dāng)前位置上，依右、下、左、上的順序探查前進(jìn)方向向可以進(jìn)入的方向前進(jìn)，即目標(biāo)位置的maze和mark值全為0。前進(jìn)一步后，目標(biāo)位置為當(dāng)前位置，將mark矩陣的當(dāng)前位置標(biāo)記為1，并且將前一位置的位置值及進(jìn)入當(dāng)前位置的方向入棧重復(fù)步驟②和③若找不到前進(jìn)通路，則從原路后退一步（退棧），改變探測方向，再重復(fù)步驟②、③，以尋找另一條新的通路重復(fù)步驟②~⑤，直到走出迷宮或宣布迷宮無通路為止走步時(shí)相鄰兩個(gè)位置之間行、列值的關(guān)系若向右走，則行值不變，列值加1若向下走，則行值加1，列值不變?nèi)粝蜃笞?，則行值不變，列值減1若向上走，則行值減1，列值不變將這4組值定義在move矩陣中列號(hào)0、1、2、3分別對(duì)應(yīng)著方向右,下,左,上行號(hào)0和1分別對(duì)應(yīng)著位置坐標(biāo)i和j走迷宮算法走迷宮算法廣義表廣義表是線性表的推廣，也稱為列表是由n(n≥0)個(gè)表元素組成的有限序列 LS=(a0,a1,…,an-1)LS是廣義表的名稱n是表的長度當(dāng)n=0時(shí)稱為空表ai(0≤i≤n-1)的類型可以不完全一致，既可以是單個(gè)元素（稱為原子），也可以是廣義表（稱為子表）原子不可再分第一個(gè)元素a0稱為LS的表頭（Head），其余元素組成的表(a1,a2,…,an-1)稱為LS的表尾（Tail）廣義表中括號(hào)的最大嵌套層數(shù)定義為表的深度空表的深度為1，原子的深度為0其他情況，可以遞歸求解廣義表的深度=max{各子表的深度}+1例4-5A=()A是空表，長度為0，深度為1B=(())B的長度為1，深度為2C=(6,2)C的長度為2，深度為1，兩個(gè)元素都是原子D=('a',(5,3,'x’))D的長度為2，深度為2，含一個(gè)原子及一個(gè)子表例4-5E=(C,D,A)E的長度為3，深度為3，含3個(gè)子表F=(C)F的長度為1，深度為2，含1個(gè)子表G=(4,G)G的長度為2，深度為∞，遞歸表各表的表頭和表尾示例Head(B)=()，Tail(B)=()Head(C)=6，Tail(C)=(2)Head(D)='a'，Tail(D)=((5,3,'x'))Head(E)=C，Tail(E)=(D,A)Head(F)=C，Tail(F)=()Head(G)=4，Tail(G)=(G)空表沒有定義表頭和表尾，所以不能求表A的表頭和表尾表E的表頭是表C第二節(jié)

串串（String）也稱為字符串，是由零個(gè)或多個(gè)字符組成的有限序列記為：s="a0a1…an-1"，(n≥0)，其中，s是串名，使用雙引號(hào)括起來的字符序列是串的值串中的每個(gè)符號(hào)ai(0≤i≤n-1)可以是字母、數(shù)字或其他字符，其在串中的次序定義為該符號(hào)的位置位置從0開始串中字符個(gè)數(shù)n稱為串的長度n=0時(shí)稱為空串串s中任意個(gè)連續(xù)字符組成的子序列稱為串s的子串，相應(yīng)地s稱為主串子串在主串中首次出現(xiàn)時(shí)子串首字符對(duì)應(yīng)于主串的符號(hào)位置，定義為子串在主串中的位置設(shè)有串s1="Thisisastring"，s2="is"s1為主串，s2是s1的子串s2在s1中的位置為2空串是任意串的子串任意串是其自身的子串串的模式匹配在主串中尋找子串（第一個(gè)字符）在主串中的位置，稱為串的模式匹配子串又稱為模式，主串稱為目標(biāo)樸素的模式匹配算法（B-F算法）設(shè)主串T="aaaaab"，模式串P="aab"，采用B-F算法的匹配過程在每趟匹配中，主串與模式串的字符之間的比較次數(shù)有3次，共4趟，所以共進(jìn)行了12次比較主串a(chǎn)aaaab

模式串a(chǎn)ab

第1趟

aab

第2趟

aab

第3趟

aab第4趟樸素的模式匹配算法簡單，但時(shí)間效率不高設(shè)主串長度為n，模式串長度為m。如果每次都是比較到模式串最后一個(gè)字符時(shí)才出現(xiàn)失配，且主串的最后m個(gè)字符與模式串匹配成功，這就出現(xiàn)了最壞情況此時(shí)，每一趟都進(jìn)行了m次比較，共比較了n-m+1趟，故總比較次數(shù)將達(dá)到(n-m+1)

m算法的最壞情況時(shí)間復(fù)雜度為O(n

m)改進(jìn)的模式匹配算法（KMP算法）設(shè)主串T="b0b1b2…bm-1…bn-1"，模式串P="p0p1p2…pm-1"，進(jìn)行第一趟匹配時(shí)，T與P的對(duì)應(yīng)字符進(jìn)行比較主串Tb0b1b2…bm-1…bn-1模式串Pp0p1p2…pm-1匹配過程中，若某一趟比較時(shí)出現(xiàn)失配，模式串P需要整體右移，那么P右移的位數(shù)應(yīng)該是多少呢模式串P的首字符p0對(duì)應(yīng)于主串的字符bs，且前j(j≥0)對(duì)字符都匹配成功，第j+1對(duì)字符匹配不成功則有bsbs+1bs+2…bs+j-1=p0p1p2…pj-1如果下一趟比較時(shí)模式串P與主串T匹配，也就是P與主串中從bs+1開始的子串匹配，則必須滿足p0p1p2…pj-1…pm-1=bs+1bs+2bs+3…bs+j…bs+m若知道p0p1…pj-2

p1p2…pj-1，則立刻可以斷定p0p1…pj-2

bs+1bs+2…bs+j-1，即下一趟必不匹配同樣地，若p0p1…pj-3

p2p3…pj-1，則再下一趟也不匹配，因?yàn)閜0p1…pj-3

bs+2bs+3…bs+j-1如果找到一個(gè)k值，滿足p0p1…pk+1

pj-k-2pj-k-1…pj-1但p0p1…pk=pj-k-1pj-k…pj-1則有p0p1…pk=bs+j-k-1bs+j-k…bs+j-1那么，下一趟可以直接用pk+1與bs+j進(jìn)行比較如何確定k值呢對(duì)于不同的失配位置j，k的取值是不同的，它僅依賴于模式串P本身前j個(gè)字符的構(gòu)成，而與主串無關(guān)設(shè)模式串P=p0p1…pm-2pm-1，定義特征向量next

從特征向量next的定義可知，next(0)=-1，next(1)=0。對(duì)于j≥2，要去查看模式串前j個(gè)字符組成的子串p0p1…pj-2pj-1的前綴和后綴，找到相等的兩個(gè)，next值是相等的前綴后綴的長度模式串Pp0p1…pkpk+1…pj-k-1pj-k…pj-1

…==

=模式串P

p0p1…pkp0p1...pj-2pj-1的前綴和后綴也可能有重疊例4-9設(shè)模式串p="abaabcac"，求它的特征向量。next(0)=-1，next(1)=0j=2時(shí)，p0p1="ab"，next(2)=0j=3時(shí)，p0p1p2="aba"，p0=p2，k=0，next(3)=1j=4時(shí)，p0p1p2p3="abaa"，p0=p3，k=0，next(4)=1j=5時(shí)，p0p1p2p3p4="abaab"，p0p1=p3p4，k=1，next(5)=2j=6時(shí)，p0p1p2p3p4p5="abaabc"，沒有相等的子串，next(6)=0j=7時(shí)，p0p1p2p3p4p5p6="abaabca"，p0=p6，k=0，next(7)=1得到特征向量j01234567Pabaabcacnext(j)-10011201例4-10設(shè)模式串P="abaabcac"，主串T="abaaababaabcac“第1趟失配時(shí)，失配位置值是4，next(4)=1，即將模式串的位置1對(duì)齊主串中的當(dāng)前位置主串中是字符a，模式串中是字符b，仍失配，失配位置值是1，next(1)=0，即將模式串的位置0對(duì)齊主串中的當(dāng)前位置主串a(chǎn)baaababaabcac

jnext(j)模式abaabcac

第1趟41

abaabcac

第2趟10

abaabcac

第3趟31

abaabcac第4趟

再次失配時(shí)的位置是3，此位置主串中是字符b，模式串中是字符a。next(3)=1，即讓模式串的位置1對(duì)齊主串中的當(dāng)前位置主串a(chǎn)baaababaabcac

jnext(j)模式abaabcac

第1趟41

abaabcac

第2趟10

abaabcac

第3趟31

abaabcac第4趟

匹配過程中，模式串右移3次，且右移時(shí)可以移多位主串的匹配位置始終不回退若每趟第一對(duì)字符不匹配，則共比較n-m+1趟，總比較次數(shù)最壞達(dá)(n-m)+m=n。若每趟第m對(duì)字符不匹配，則總比較次數(shù)最壞亦達(dá)到n分析示例中的向右移位第一趟失配時(shí)，模式串中位置4的字符b與主串中位置4的字符a不匹配，根據(jù)next值，模式串中位置1的字符對(duì)應(yīng)到主串的當(dāng)前位置，并進(jìn)行比較。實(shí)際上，模式串位置1的字符仍是b，所以還是失配的。再次根據(jù)next值，繼續(xù)右移模式串改進(jìn)next值的計(jì)算，當(dāng)模式串中失配位置的字符與要移到的目標(biāo)位置的字符相等時(shí)，使用目標(biāo)位置的next值來替代。由此，省略掉中間這一步的右移例4-11設(shè)模式串p="abaabcac"，求它的改進(jìn)特征向量。j01234567Pabaabcacnext(j)-10-1102-11例4-12設(shè)模式串P="abaabcac"，主串T="abaaababaabcac"匹配過程如下主串a(chǎn)baaababaabcac

jnext(j)模式abaabcac

第一趟40

abaabcac

第二趟31

abaabcac第三趟

求改進(jìn)的特征向量ThankYou!全國高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第五章樹與二叉樹學(xué)習(xí)目標(biāo)理解樹及二叉樹的基本概念，掌握二叉樹的基本性質(zhì)掌握樹及二叉樹的存儲(chǔ)方式能夠?qū)崿F(xiàn)樹及二叉樹的基本操作及遍歷算法掌握堆的概念及基本操作的實(shí)現(xiàn)。理解優(yōu)先隊(duì)列的概念理解遞歸的概念，能夠?qū)崿F(xiàn)遞歸程序掌握樹、森林與二叉樹之間的相互轉(zhuǎn)換掌握哈夫曼樹及哈夫曼編碼的概念，能夠構(gòu)造哈夫曼樹并設(shè)計(jì)哈夫曼編碼本章主要內(nèi)容樹的基本概念12二叉樹的操作3二叉樹樹和森林5哈夫曼樹及哈夫曼編碼6堆及優(yōu)先隊(duì)列4第一節(jié)樹的基本概念樹是一種層次結(jié)構(gòu)，是一種非線性結(jié)構(gòu)日常生活中，經(jīng)常會(huì)遇到具有層次關(guān)系的示例家族中部分成員的輩份關(guān)系樹的定義定義5-1一棵樹（tree）T是由一個(gè)或一個(gè)以上的結(jié)點(diǎn)組成的有限集，其中有一個(gè)特定的結(jié)點(diǎn)R稱為樹T的根結(jié)點(diǎn)。在集合中除根結(jié)點(diǎn)R外，其余的結(jié)點(diǎn)可劃分為k(k≥0)個(gè)不相交的子集T1,T2,…,Tk，其中每個(gè)子集都是樹，并且其相應(yīng)的根結(jié)點(diǎn)R1,R2,…,Rk是R的孩子結(jié)點(diǎn)，R稱為Ri(1≤i≤k)的雙親結(jié)點(diǎn)，Ri(1≤i≤k)互稱為兄弟結(jié)點(diǎn)。子集Ti

(1≤i≤k)稱為根R的子樹（subtree）樹的結(jié)點(diǎn)集合至少包含一個(gè)結(jié)點(diǎn)只含有一個(gè)結(jié)點(diǎn)的樹是只有根結(jié)點(diǎn)的樹，也就是單結(jié)點(diǎn)樹對(duì)于多結(jié)點(diǎn)的樹，必須有一個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)之間通過邊來連接，邊也稱為分支。含n個(gè)結(jié)點(diǎn)的樹有且僅有n-1條邊，這是樹的重要特性之一根結(jié)點(diǎn)的各子樹之間不會(huì)有重疊樹是一種層次結(jié)構(gòu)，也是遞歸形式的含有A,B,C,D,E,F,G,H,I,J共10個(gè)結(jié)點(diǎn)的樹TA為根結(jié)點(diǎn)，{B,E,F}，{C,G}和{D,H,I,J}構(gòu)成根結(jié)點(diǎn)A的三棵子樹，B,C,D分別是這三棵子樹的根樹中每個(gè)結(jié)點(diǎn)擁有的子樹的個(gè)數(shù)稱為結(jié)點(diǎn)的度結(jié)點(diǎn)的度即為其子結(jié)點(diǎn)的個(gè)數(shù)樹中結(jié)點(diǎn)的度的最大值稱為樹的度度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，或終端結(jié)點(diǎn)度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)如果樹中每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間規(guī)定了次序，則樹稱為有序樹具有同一雙親結(jié)點(diǎn)的結(jié)點(diǎn)是兄弟結(jié)點(diǎn)從任一結(jié)點(diǎn)到根結(jié)點(diǎn)之間所經(jīng)過的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的祖先結(jié)點(diǎn)以任一結(jié)點(diǎn)為根的子樹中的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的后代將線性結(jié)構(gòu)中的前驅(qū)和后繼概念引申至樹中，將某結(jié)點(diǎn)的雙親結(jié)點(diǎn)看作是它的前驅(qū)，它的孩子結(jié)點(diǎn)看作是它的后繼除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均只有一個(gè)前驅(qū)結(jié)點(diǎn)根的前驅(qū)結(jié)點(diǎn)個(gè)數(shù)為0，除葉結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有若干個(gè)后繼結(jié)點(diǎn)葉結(jié)點(diǎn)的后繼結(jié)點(diǎn)個(gè)數(shù)為0樹中每個(gè)元素的前驅(qū)的個(gè)數(shù)不會(huì)多于1個(gè)，后繼的個(gè)數(shù)可以是任意個(gè)樹是一種層次結(jié)構(gòu)，設(shè)根為0層，根的孩子結(jié)點(diǎn)為1層，依此類推一般地，若某個(gè)結(jié)點(diǎn)位于i（i≥0）層，則它的孩子結(jié)點(diǎn)位于i+1層樹中結(jié)點(diǎn)的最大層數(shù)定義為樹的深度最大層數(shù)加1為樹的高度樹中從某一結(jié)點(diǎn)出發(fā)，到達(dá)另一個(gè)結(jié)點(diǎn)之間所經(jīng)過的邊組成一條路徑路徑中所含的邊數(shù)為路徑長度雖然樹的路徑定義中并沒有限制路徑的方向，但路徑通常是沿一個(gè)方向延伸的，即從某一結(jié)點(diǎn)向根的方向延伸，或是從某一結(jié)點(diǎn)向葉結(jié)點(diǎn)方向延伸通常，以組成路徑的結(jié)點(diǎn)序列來表示該條路徑m（m≥0）棵互不相交的樹構(gòu)成森林對(duì)樹中每個(gè)結(jié)點(diǎn)來說，其子樹的集合即為森林第二節(jié)二叉樹定義5-2二叉樹（binarytree）是結(jié)點(diǎn)的一個(gè)有限集合，這個(gè)集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為這個(gè)根的左子樹和右子樹的二叉樹組成。左子樹和右子樹的根分別稱為此二叉樹根結(jié)點(diǎn)的左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)二叉樹的左子樹和右子樹都可以存在或者為空，不同的存在狀態(tài)可以組合出5種基本形態(tài)一棵高度為h的二叉樹若有2h-1個(gè)結(jié)點(diǎn)，則二叉樹稱為滿二叉樹從形式上來看，滿二叉樹中除葉結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)，即除最后一層外，每一層的結(jié)點(diǎn)都是“滿”的滿二叉樹中的n個(gè)結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，從編號(hào)為0的結(jié)點(diǎn)開始，由連續(xù)編號(hào)的任意多個(gè)結(jié)點(diǎn)組成的二叉樹稱為完全二叉樹特殊二叉樹滿二叉樹和完全二叉樹完全二叉樹的特性

二叉樹的性質(zhì)性質(zhì)1在二叉樹的i層上最多有2i個(gè)結(jié)點(diǎn)(i≥0)證明：使用數(shù)學(xué)歸納法證明

歸納基礎(chǔ)：

對(duì)于非空的二叉樹T，根在0層，本層只有20=1個(gè)結(jié)點(diǎn)，結(jié)論成立

歸納假設(shè)：

設(shè)二叉樹T中i-1層最多有2i-1個(gè)結(jié)點(diǎn)，考慮i層，由于i層的結(jié)點(diǎn)均為i-1層結(jié)點(diǎn)的孩子結(jié)點(diǎn)，而二叉樹中每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)，故i層最多有2

2i-1=2i個(gè)結(jié)點(diǎn)

根據(jù)歸納法原理，性質(zhì)1得證

性質(zhì)3對(duì)任何非空二叉樹T，設(shè)n0是葉結(jié)點(diǎn)的個(gè)數(shù)，n2是度為2的結(jié)點(diǎn)的個(gè)數(shù)，則有n0=n2+1證明：設(shè)二叉樹T中度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，則T中結(jié)點(diǎn)總數(shù)n為 n=n0+n1+n2 n-1=2

n2+1

n1+0

n0

將上兩式聯(lián)立求解，得到 n0=n2+1

例5-3一棵二叉樹共有20個(gè)結(jié)點(diǎn)，其中葉結(jié)點(diǎn)為5個(gè)，則度為l的結(jié)點(diǎn)個(gè)數(shù)是（）。A．11B．9C．6D．4答案為A二叉樹的存儲(chǔ)——順序存儲(chǔ)結(jié)構(gòu)對(duì)于完全二叉樹，各層自上至下，同層間自左至右，將結(jié)點(diǎn)依次存入數(shù)組從前至后的各個(gè)元素中。按照前面使用過的編號(hào)方法，一般來講，編號(hào)為i的結(jié)點(diǎn)存放在數(shù)組中下標(biāo)為i的位置使用這樣的存儲(chǔ)規(guī)則可以很方便地找到二叉樹中的相關(guān)結(jié)點(diǎn)，即若知道二叉樹某一結(jié)點(diǎn)保存在數(shù)組中下標(biāo)i的位置，則可以很方便地求出它的雙親結(jié)點(diǎn)（若存在）和左、右孩子結(jié)點(diǎn)（若存在）在數(shù)組中的位置對(duì)于一般的二叉樹，順序存儲(chǔ)的思想是，針對(duì)二叉樹中的每個(gè)位置，不論這個(gè)位置有沒有結(jié)點(diǎn)，都在數(shù)組中預(yù)留保存空間。采用這種存儲(chǔ)方式保存完全二叉樹時(shí)，既不浪費(fèi)空間，又便于有關(guān)操作的實(shí)現(xiàn)例5-4設(shè)高度為k（k≥1）的二叉樹T采用順序存儲(chǔ)結(jié)構(gòu)保存在數(shù)組B[2k-1]中，在沒有保存T中元素的數(shù)組位置中，保存一個(gè)區(qū)別于T中元素的特殊標(biāo)記。B中保存的特殊標(biāo)記個(gè)數(shù)最多為（）。A．k-1B．2k-1C．2k-k-1D．2k-1答案為C鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義一個(gè)結(jié)點(diǎn)結(jié)構(gòu)：它含有兩個(gè)指針域，一個(gè)指針用來指向該結(jié)點(diǎn)左孩子所在的結(jié)點(diǎn)，稱為左孩子指針，簡稱為左指針；另一個(gè)指針用來指向該結(jié)點(diǎn)右孩子所在的結(jié)點(diǎn)，稱為右孩子指針，簡稱為右指針。此外，還定義一個(gè)用來保存結(jié)點(diǎn)中數(shù)據(jù)的數(shù)據(jù)域二叉鏈表表示二叉樹結(jié)點(diǎn)類的定義及二叉樹的定義二叉鏈表中結(jié)點(diǎn)類的定義及二叉樹的定義typedefintELEMType;typedefstructBNode //二叉樹結(jié)點(diǎn){ ELEMTypedata; //數(shù)據(jù)域 structBNode*left,*right;

//指向左孩子、右孩子的指針}BinTNode;typedefBinTNode*BTree; //二叉樹二叉鏈表中到底有多少空指針域呢設(shè)二叉樹中有n個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都含有兩個(gè)指針域，則二叉鏈表中共有2

n個(gè)指針域已知含n個(gè)結(jié)點(diǎn)的樹中僅含有n-1個(gè)分支，即只有n-1個(gè)指針域不為空，則其余的n+1個(gè)指針域均為空可以看出，二叉鏈表中有超過一半的指針域都是空的，這些都是結(jié)構(gòu)性開銷第三節(jié)二叉樹的操作二叉樹的生成按照二叉樹的順序存儲(chǔ)方式，將二叉樹各結(jié)點(diǎn)值保存在一維數(shù)組中，然后建立二叉鏈表如要建立如下的二叉鏈表輸入的數(shù)組是inta[]={0,1,2,3,4,NA,5,NA,NA,NA,NA,NA,NA,6};函數(shù)CreateBinaryTree遞歸處理二叉鏈表的生成調(diào)用它的主程序中先創(chuàng)建一個(gè)根結(jié)點(diǎn)，其中保存數(shù)組首元素的值，該結(jié)點(diǎn)作為參數(shù)傳遞給函數(shù)CreateBinaryTree。這個(gè)結(jié)點(diǎn)的位置是下標(biāo)0，將這個(gè)位置值也作為參數(shù)傳給函數(shù)CreateBinaryTree主程序中BTreeroot;root=(BTree)malloc(sizeof(BinTNode));root->data=a[0];root->left=NULL;root->right=NULL;調(diào)用函數(shù)CreateBinaryTree。參數(shù)0是起始位置CreateBinaryTree(0,n,a,root);生成二叉鏈表如果下標(biāo)i處的結(jié)點(diǎn)有左孩子，則其應(yīng)該保存在下標(biāo)2

i+1處如果有右孩子，則應(yīng)該保存在下標(biāo)2

i+2處故在函數(shù)內(nèi)，判斷數(shù)組中位置2

i+1及位置2

i+2處是否保存了元素值如果確實(shí)有值，則分配空間創(chuàng)建結(jié)點(diǎn)且保存數(shù)組中相應(yīng)位置的元素值，并讓下標(biāo)i處結(jié)點(diǎn)的相應(yīng)指針指向新創(chuàng)建的結(jié)點(diǎn)然后再以2

i+1或2

i+2為參數(shù)值，遞歸調(diào)用函數(shù)，去處理2

i+1或2

i+2位置處結(jié)點(diǎn)的左孩子和右孩子如果數(shù)組中數(shù)據(jù)的存儲(chǔ)是正確的，則能正確建立二叉鏈表。如果位置2

i+1或位置2

i+2處沒有保存元素值，則遞歸結(jié)束二叉樹的遍歷對(duì)非空的二叉樹的遍歷可以相應(yīng)地分解為三項(xiàng)“子任務(wù)”訪問根結(jié)點(diǎn)遍歷左子樹（即依相應(yīng)的規(guī)律訪問左子樹中的全部結(jié)點(diǎn)）遍歷右子樹（即依相應(yīng)的規(guī)律訪問右子樹中的全部結(jié)點(diǎn)）常規(guī)的3種遍歷算法分別是先序遍歷、中序遍歷和后序遍歷。這3種遍歷也分別稱為先根遍歷、中根遍歷和后根遍歷先序遍歷算法若二叉樹為空，則返回；否則依次執(zhí)行以下操作（1）訪問根結(jié)點(diǎn)（2）先序遍歷左子樹（3）先序遍歷右子樹中序遍歷算法若二叉樹為空，則返回；否則依次執(zhí)行以下操作（1）中序遍歷左子樹（2）訪問根結(jié)點(diǎn)（3）中序遍歷右子樹后序遍歷算法若二叉樹為空，則返回；否則依次執(zhí)行以下操作（1）后序遍歷左子樹（2）后序遍歷右子樹（3）訪問根結(jié)點(diǎn)先序遍歷過程中序遍歷過程后序遍歷過程例5-6寫出其先序、中序及后序遍歷序列先序遍歷序列為A,B,D,G,H,J,K,E中序遍歷序列為G,D,J,H,K,B,E,A后序遍歷序列為G,J,K,H,D,E,B,A先序遍歷算法先序遍歷算法中序遍歷算法中序遍歷算法后序遍歷算法后序遍歷算法給出二叉樹的先序遍歷序列和中序遍歷序列，能唯一確定該二叉樹給出二叉樹的后序遍歷序列和中序遍歷序列，能唯一確定該二叉樹例5-7設(shè)二叉樹T的先序遍歷序列是A,B,D,G,H,J,K,E，中序遍歷序列是G,D,J,H,K,B,E,A，畫出二叉樹T由先序遍歷序列可知，T的根是A在中序遍歷序列中查找A的位置，位于A前面的是其左子樹的中序遍歷序列，位于A后面的是其右子樹的中序遍歷序列從而將原問題的求解（對(duì)整棵樹的還原）分解為兩個(gè)更小問題的求解（對(duì)兩棵子樹的還原）例5-8統(tǒng)計(jì)以二叉鏈表表示的二叉樹T中葉結(jié)點(diǎn)的個(gè)數(shù)T中葉結(jié)點(diǎn)的個(gè)數(shù)等于根左子樹中葉結(jié)點(diǎn)的個(gè)數(shù)加上根右子樹中葉結(jié)點(diǎn)的個(gè)數(shù)。所以如果遞歸調(diào)用已經(jīng)得到了兩棵子樹中葉結(jié)點(diǎn)的個(gè)數(shù)，那么將結(jié)果相加即求解例5-9編寫程序，返回二叉樹T的高度仍是使用遞歸的思想去編寫程序。如果左子樹的高度和右子樹的高度都已經(jīng)知道，則二叉樹T的高度就可求得，樹的高度是兩棵子樹中較高者的高度再加1層序遍歷所謂按層遍歷，即是從根結(jié)點(diǎn)開始逐層向下遍歷，直到最后一層對(duì)于同一層的結(jié)點(diǎn)，由左到右遍歷各結(jié)點(diǎn)同一層中的結(jié)點(diǎn)相繼被訪問，同時(shí)，它們之間的相對(duì)次序也決定著它們孩子結(jié)點(diǎn)的相對(duì)次序。即同一層中的結(jié)點(diǎn)u和結(jié)點(diǎn)v，若先遍歷u再遍歷v，則u的孩子結(jié)點(diǎn)的遍歷也早于v的孩子結(jié)點(diǎn)的遍歷按層進(jìn)行遍歷先訪問最上面一層即0層中的元素，輸出1然后依次訪問1的子結(jié)點(diǎn)2和3再繼續(xù)訪問2的子結(jié)點(diǎn)和3的子結(jié)點(diǎn)依此類推，得到的層序遍歷結(jié)果是：1,2,3,4,5,6,7層序遍歷算法二叉樹層序遍歷的算法遍歷的非遞歸實(shí)現(xiàn)仍然將一棵二叉樹分為三部分：根、左子樹和右子樹。從根開始遍歷二叉樹時(shí)，根的左子樹和右子樹的遍歷不能同時(shí)進(jìn)行，只能先遍歷一棵子樹，同時(shí)保存二叉樹中尚不能遍歷部分的信息，留待一棵子樹處理完畢后再處理分析二叉樹的遍歷過程可知，使用棧來保存相關(guān)信息先序遍歷算法在進(jìn)入左子樹進(jìn)行處理之前，需要在棧中保存右子樹的相關(guān)信息，以便當(dāng)左子樹處理完畢，能夠根據(jù)保存的線索找到右子樹的根。所以，棧中保存右子樹的根即可程序中序遍歷算法中序遍歷時(shí)，先進(jìn)行左子樹的遍歷，然后遍歷根，再遍歷右子樹。所以棧中保存根的信息，遍歷完左子樹后，從棧中找到根，訪問根，同時(shí)也能容易地找到右子樹程序后序遍歷算法類似于中序遍歷過程，在進(jìn)入左子樹遍歷之前，需要先保存根的信息。當(dāng)左子樹遍歷結(jié)束，從棧中找到根，但此時(shí)因?yàn)橛易訕渖形幢闅v，所以根并不能從棧中彈出，仍需要保存在棧中，只有當(dāng)右子樹也遍歷結(jié)束后，才能訪問根棧中保存的結(jié)點(diǎn)需要入棧兩次出棧兩次。為了能有所區(qū)別，二叉樹結(jié)點(diǎn)入棧時(shí)，附帶一個(gè)標(biāo)記位flag。第一次出棧時(shí)，并不訪問結(jié)點(diǎn)。第二次出棧時(shí)才訪問它將二叉樹結(jié)點(diǎn)和標(biāo)記組合在一起，定義新的棧的類型，專用于非遞歸實(shí)現(xiàn)二叉樹的后序遍歷過程typedefstruct SNode //進(jìn)棧帶標(biāo)記結(jié)點(diǎn){ BinTNode

btreeNode; //二叉樹結(jié)點(diǎn)

intflag; //標(biāo)記}StackTNode; typedefstruct{ //用于后序遍歷的棧

StackTNodeelement[maxSize]; inttop; //棧頂位置}SeqBTreeStackforPostT;程序二叉樹的應(yīng)用可以使用二叉樹來表示一個(gè)表達(dá)式，這樣的二叉樹稱為表達(dá)式樹2*y*(a+3*y)-b畫出表達(dá)式樹先根據(jù)運(yùn)算符的優(yōu)先級(jí)對(duì)表達(dá)式加括號(hào)去掉最外層括號(hào)。中間的運(yùn)算符為根，前后兩部分分別對(duì)應(yīng)于左子樹和右子樹對(duì)左子樹遞歸執(zhí)行步驟②對(duì)右子樹遞歸執(zhí)行步驟②當(dāng)遇到空串時(shí)，遞歸結(jié)束例5-12已知算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為（）A．-A+B*C/DEB．-A+B*CD/EC．-+*ABC/DED．-+A*BC/DE答案：D

第四節(jié)堆及優(yōu)先隊(duì)列前一種關(guān)系表明，任何一個(gè)分支結(jié)點(diǎn)的值都不大于它子結(jié)點(diǎn)的值，所以樹根結(jié)點(diǎn)的值是全部結(jié)點(diǎn)中的最小值。這樣的堆稱為最小堆或小根堆后一種關(guān)系表明，任何一個(gè)分支結(jié)點(diǎn)的值都不小于它子結(jié)點(diǎn)的值，故樹根結(jié)點(diǎn)的值是全部結(jié)點(diǎn)中的最大值。這樣的堆稱為最大堆或大根堆樹根結(jié)點(diǎn)稱為堆頂堆的定義中還隱含了遞歸的含義，當(dāng)用完全二叉樹的形式表示堆時(shí)，樹中的任意一棵子樹都可以構(gòu)成堆，并且保持與原來同樣的性質(zhì)最大堆中任何結(jié)點(diǎn)的子樹仍是最大堆最小堆中任何結(jié)點(diǎn)的子樹仍是最小堆最小堆和最大堆堆的類型定義#defineHeapSize30 //堆的容量typedefintELEMType; //元素類型typedefstructHeap{

ELEMTypeheap[HeapSize]; //存放元素的數(shù)組 intn; //堆中當(dāng)前元素個(gè)數(shù)};堆的基本操作intcreatHeap(maxHeap*H,ELEMType

arr[],intn); //創(chuàng)建堆intinsertHeap(maxHeap*H,ELEMTypex); //在堆中插入元素xintdeleteHeap(maxHeap*H,ELEMType*x); //刪除堆頂元素intisHeapEmpty(maxHeap*H); //如果堆為空，則返回1，否則返回0intisHeapFull(maxHeap*H); //如果堆為滿，則返回1，否則返回0最大堆的類型定義#defineHeapSize30 //堆的容量typedefintELEMType; //元素類型typedefstructmaxHeap{

ELEMTypeheap[HeapSize]; //存放元素的數(shù)組 intn; //堆中當(dāng)前元素個(gè)數(shù)};判空、判滿創(chuàng)建最大堆向最大堆中插入新元素刪除堆頂元素例5-1370,13,65,24,56,48,92,86，將其建成最大堆例5-14在最大堆中插入新元素40例5-15刪除最大堆的堆頂優(yōu)先隊(duì)列一些應(yīng)用中，各元素本身還被賦予一個(gè)優(yōu)先值，可以用一個(gè)非負(fù)整數(shù)表示優(yōu)先值。優(yōu)先值也稱為優(yōu)先權(quán)。具有優(yōu)先值的各元素保存在一個(gè)結(jié)構(gòu)中，這個(gè)結(jié)構(gòu)稱為優(yōu)先隊(duì)列。輸出時(shí)，選擇最優(yōu)先的元素輸出。“最優(yōu)先”取決于優(yōu)先值的定義，可以是優(yōu)先值最小，也可以是優(yōu)先值最大。第五節(jié)樹和森林樹的存儲(chǔ)結(jié)構(gòu)父結(jié)點(diǎn)表示法孩子結(jié)點(diǎn)表示法孩子-兄弟表示法父結(jié)點(diǎn)表示法樹中每個(gè)結(jié)點(diǎn)至少含兩個(gè)域，一個(gè)域用來保存結(jié)點(diǎn)本身的值，另一個(gè)域用來保存結(jié)點(diǎn)之父結(jié)點(diǎn)的相關(guān)信息孩子結(jié)點(diǎn)表示法父結(jié)點(diǎn)-孩子結(jié)點(diǎn)表示法孩子-兄弟表示法為樹中的每個(gè)結(jié)點(diǎn)定義一個(gè)存儲(chǔ)結(jié)點(diǎn)，其中有左、右兩個(gè)指針域，左指針域指向這個(gè)結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)，右指針域指向這個(gè)結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)樹、森林與二叉樹的轉(zhuǎn)換樹和二叉樹都可以用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)同一個(gè)二叉鏈表，若按樹的存儲(chǔ)含義來解釋，可以還原為樹。若按二叉樹的存儲(chǔ)含義來解釋，可以還原為二叉樹正是因?yàn)檫@一點(diǎn)，可以在樹與二叉樹之間建立一種對(duì)應(yīng)關(guān)系轉(zhuǎn)換規(guī)則規(guī)則1：將森林轉(zhuǎn)換成二叉樹設(shè)F={T1,T2,…,Tm}是森林，則可按如下規(guī)則將森林F轉(zhuǎn)換為一棵二叉樹B=(root,LB,RB)（1）若F為空（m=0），則B為空樹（2）若F非空（m>0），則森林中T1的根作為二叉樹B的根root；T1中各子樹組成的森林F1={T11,T12,…,T1s}轉(zhuǎn)換成的二叉樹作為B的左子樹BL；森林F’={T2,T3,…,Tm}轉(zhuǎn)換成的二叉樹作為B的右子樹BR森林轉(zhuǎn)換為二叉樹轉(zhuǎn)換規(guī)則規(guī)則2：將二叉樹還原為森林設(shè)B=(root,BL,BR)是一棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林F={T1,T2,…,Tm}（1）若B為空，則F為空（2