【正文】 read2(ThrNode *t) /* 中序遍歷線索化以t為根的二叉樹(shù)*/ { if( t ){ inthread2(tlchild)。 /*左子樹(shù)線索化*/ if(pre!=NULL){ if( prerchild==NULL){ /* 建立pre結(jié)點(diǎn)的后繼線索*/ preRtag=1。 prerchild=t。 } } pre=t。 /*pre指向t的前驅(qū)*/ inthread2(trchild)。 /*右子樹(shù)線索化*/ } }/* inthread2 */ 題圖 42FBDHKGJICAE11．畫出與題圖42所示二叉樹(shù)對(duì)應(yīng)的森林。解：FBDHKGJICAE上機(jī)實(shí)習(xí)題 一、實(shí)習(xí)目的1．掌握樹(shù)的結(jié)構(gòu)的非線性特點(diǎn)、遞歸性特點(diǎn)和動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)等特點(diǎn)。 2．掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)、各種遍歷算法以及基于遍歷算法的其他操作的實(shí)現(xiàn)。二、實(shí)習(xí)內(nèi)容 1．編寫一個(gè)C語(yǔ)言程序，對(duì)二叉樹(shù)實(shí)現(xiàn)以下操作：（1）按先根、中根和后根次序遍歷二叉樹(shù)；（2）按二叉樹(shù)的層次輸出各結(jié)點(diǎn)（每一行輸出一層）；（3）利用遍歷算法，將二叉樹(shù)中所有結(jié)點(diǎn)的左右子樹(shù)交換。2．在一段文字中10個(gè)常用漢字及出現(xiàn)的頻度如下： 的 地 得 于 個(gè) 和 在 再 是 有 26 6 4 15 7 6 8 5 18 5 試為這些常用漢字設(shè)計(jì)哈夫曼編碼表。第五章 12341 V1入度2,出度1，v2入度1，出度2,v3入度1，出度0，v4入度1，出度2鄰接陣G0001101000001100鄰接表v1v4v2v1v3v4v1v2逆鄰接表v1v2v4v2v4v3v2v4v12廣度優(yōu)先序列是：v2,v1,v3,v6,v4,v5深度優(yōu)先序列是:v2,v1,v3,v4,v5,v63深度優(yōu)先序列是：v1,v3,v4,v2,v5（根據(jù)存儲(chǔ)順序，如果根據(jù)序號(hào)大小有不同結(jié)果）4給出歸并順序： 普里姆：v1,v3v4v5v2克魯斯卡爾：v4,v5邊，v4,v2邊，v3,v4邊，v3,v1邊（有權(quán)值相同的邊，不唯一）５最短路徑(v1v3 )5 (v1v6) 15 (v1v4) 19 (v1v2) 20 (v1v5) 25 6 AOV網(wǎng)絡(luò)v1,v4,(或者v4,v1)可換。v2位置不可變，v5,v3(或者v3,v5)，v6不可變 鄰接表中: v1,v4,v2,v3,v5,v6第六章1 算法說(shuō)明：本程序使用兩個(gè)結(jié)點(diǎn)鏈交換的方法，比較復(fù)雜，要簡(jiǎn)化的同學(xué)可以直接交換內(nèi)容。代碼可以省去三分之二。/*insert sort via LinkList*/struct Node{ int data。 struct Node *next。}。struct Node * locateCount(struct Node *h,int k){ int i=0。 struct Node *h1=h。 for(i=1。i=k。i++) h1=h1next。 return h1。} 。 show(struct Node *head){ struct Node *p。 p=headnext。 while(p!=0){ printf( : %3d : ,pdata)。 p=pnext。 } printf(\n)。 return。}sort(struct Node *head){ struct Node *h,*searchGoalPtr,*p,*q,*qStart,*preGoal。 struct Node *temp,*pt1,*pt2,*goalNext。 int count=2。 h=head。 preGoal=headnext。 searchGoalPtr=headnextnext。 qStart=head。 while(searchGoalPtr!=0){/*go */ hdata=searchGoalPtrdata。 q=qStart。 while(qnextdatahdata){ q=qnext。 } pt1=qnext。 qnext=searchGoalPtr。 pt2=searchGoalPtrnext。 searchGoalPtrnext=pt1。 preGoalnext=pt2。 preGoal=locateCount(head,count)。 count++。 searchGoalPtr=locateCount(head,count)。 show(head)。 }/*while*/}main(){ struct Node *h,*p1,tail。 int var=0。 h= (struct Node*) malloc(sizeof(struct Node))。 hdata=0。 hnext=0。 /*construct a linked list*/ while(1){ printf(Please input a Node,enter 1 end:)。 scanf(%d,amp。var)。 if (var==1) break。 p1=(struct Node*) malloc(sizeof(struct Node))。 p1data=var。 p1next=hnext。 hnext=p1。 } show(h)。 sort(h)。 show(h)。 /*yes constructed!*/ free(h)。 return 。}2 排序過(guò)程56 67 59 41 98 47 26 38 75 52 16 原始數(shù)據(jù)16 26 38 41 52 47 67 59 75 98 56 d=516 26 38 41 52 47 67 56 75 98 59 d=316 26 38 41 47 52 56 59 67 75 98 d=13 不需要，因?yàn)榕判蛞呀?jīng)完成4 冒泡過(guò)程14 15 28 5 10 30 a14 15 5 10 28 30 b14 5 10 15 28 30 c10 14 15 28 30 d快速過(guò)程14 15 30 28 5 1010 15 30 28 5 1410 14 30 28 5 1510 5 30 28 14 1510 5 14 28 30 15 分左右再內(nèi)部排序得10 14 15 28 305 直接插入5 冒泡5 快速146 提示：。7 /*insert sort via LinkList*/struct Node{ int data。 struct Node *next。}。 show(struct Node *head){ struct Node *p。 p=headnext。 while(p!=0){ printf( : %3d : ,pdata)。 p=pnext。 } printf(\n)。 return。}sort(struct Node *head){ struct Node *p,*ptr1,*ptr2。 int min。 int temp。 ptr1=headnext。 while(ptr1){ ptr2=ptr1next。 min=ptr1data。 while(ptr2){ if (ptr2datamin) { temp=ptr1data。 ptr1data=ptr2data。 ptr2data=temp。 }/*if*/ ptr2=ptr2next。 }/*ptr2*/ ptr1=ptr1next。 } show(head)。 }/*while*/main(){ struct Node *h,*p1,tail。 int var=0。 h= (struct Node*) malloc(sizeof(struct Node))。 hdata=0。 hnext=0。 /*construct a linked list*/ while(1){ printf(Please input a Node,enter 1 end:)。 scanf(%d,amp。var)。 if (var==1) break。 p1=(struct Node*) malloc(sizeof(struct Node))。 p1data=var。 p1next=hnext。 hnext=p1。 } show(h)。 sort(h)。 show(h)。 /*yes constructed!*/ free(h)。 return 。}8 4符合堆的特性。9 19 34 26 97 56 75是一個(gè)堆先19出堆，調(diào)整75上來(lái)，得 1975 34 26 97 56 ,調(diào)整后26 34 75 97 56 ，得26調(diào)整56上來(lái)得56 34 75 97 調(diào)整得34 56 75 97 出 34調(diào)整97上來(lái)得97 56 75調(diào)整得56 97 75 出56最后出75 和9710 56 67 59 41 98 47 26 38 75 52 16 L=156 67 41 59 47 98 26 38 52 75 16 L=241 56 59 67 26 38 47 98 16 52 75 L=416 26 38 41 47 52 56 59 67 75 98 結(jié)果原因是r 是一次歸并結(jié)果，放在r2里臨時(shí)存放，最后放回r以便下次再處理。第七章1．有一個(gè)有序文件，其中各記錄的關(guān)鍵字為：{3,4,5,6,7,8,10,17,19,20,27,32,43,54,65,76,87}，當(dāng)用折半查找算法查找關(guān)鍵字為4,20,65時(shí)，其比較次數(shù)分別為多少?解：K=46571110128213151416491317K=20K=65判定樹(shù)該有序文件長(zhǎng)度為17，根據(jù)折半查找算法畫出判定樹(shù)如下圖所示。從圖中可得出：當(dāng)關(guān)鍵字為4,20,65時(shí)，其比較次數(shù)分別為3，4，3。２、 若對(duì)大小均為n的有序順序表和無(wú)序順序表分別進(jìn)行順序查找，試就下列三種情況分別討論兩者在等查找概率時(shí)的平均查找長(zhǎng)度是否相同?(1)查找失?。?2)查找成功；(3)查找成功，表中有多個(gè)關(guān)鍵字等于給定值的記錄，一次查找要求找出所有記錄。解：(1)平均查找長(zhǎng)度不相同。有序順序表小于等于無(wú)序順序表。(2)平均查找長(zhǎng)度相同。(3) 平均查找長(zhǎng)度不相同，有序順序表小于等于無(wú)序順序表。３、 試按下列次序?qū)⒏麝P(guān)鍵字插入到二叉平衡樹(shù)中，畫出重新平衡的情況。關(guān)鍵字依次為：111解： 生成并調(diào)整成平衡二叉排序樹(shù)的過(guò)程如下圖(a)～(j)所示。89128RR89(b)不調(diào)整1289(c)調(diào)整(a)初始912821LL912281(e)調(diào)整91282(d)不調(diào)整9122815LR9128251LL9825112(f)調(diào)整39825112(g)不調(diào)整39825112(h)不調(diào)整63982511267RR1985621273(i)調(diào)整9111856212731211985621173111985621273RRRL(j)調(diào)整４、已知長(zhǎng)度為12的表：（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）。(1) 試按表中元素的順序，依次插入一棵初始為空的