數(shù)據(jù)結(jié)構(gòu)電子教案 第六章

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)電子教案第六章同步綜合練習(xí)及參考答案（一）基礎(chǔ)知識題6.1加設(shè)在樹中，結(jié)點(diǎn)x是結(jié)點(diǎn)y的雙親時(shí)，用(x,y)來表示樹變。已知一棵樹邊的集合為：{(i,m),(i,n),(b,e),(e,i),(b,d),(a,b),(g,i),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用樹形表示法畫出此樹，并回復(fù)以下問題：

（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉結(jié)點(diǎn)？（3）哪個(gè)是g的雙親？（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孫？

（7）哪些是e的兄弟？哪些是f的兄弟？（8）結(jié)點(diǎn)b和n的層次各是多少？（9）樹的深度是多少？

（10）以結(jié)點(diǎn)c為根的子樹的深度是多少？（11）樹的度數(shù)是多少？解：

（1）a是根結(jié)點(diǎn)。

（2）m,n,j,k,l是葉結(jié)點(diǎn)。（3）c是g的雙親。（4）a,c是g的祖先。（5）g的孩子是j,k.。（6）e的子孫是i,m,n.。

（7）e的兄弟是a,f的兄弟是g。（8）h,b在第五層。（9）樹的深度為3。

（10）以C為根的子樹的深度為3。（11）樹的度數(shù)為3。

6．2一棵度為2的有序?qū)儆谝豢枚鏄溆泻螀^(qū)別？解：

區(qū)別：度為2的樹有二個(gè)分支，沒有左右之分；以可二叉樹也有兩個(gè)分支，但有左右之分，且左右不能交換。

6．3試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。解：

3個(gè)結(jié)點(diǎn)樹形態(tài)：3個(gè)結(jié)點(diǎn)的二叉樹：

6．4已知一棵樹為m的樹中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，…nm個(gè)度為m的結(jié)點(diǎn)，問該書中有多少片葉子？解：

由于n1+n2+…+nM+n0+=1+n1+2n2+…+mnM=>n0+=1+n2+…+(m-1)nM

6.5一個(gè)深度為h的滿k叉樹有如下性質(zhì)：第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹。假使按層次順序（同層自左至右）從未有過開始對全部結(jié)點(diǎn)編號，問：

（1）各層的結(jié)點(diǎn)數(shù)目是多少？

（2）編號為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號是多少？

（3）編號為i的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)（若存在）的編號是多少？

（4）編號為i的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號是多少？解：

（1）Ki-1（2）

（3）Ki+j-1

（4）(i-1)MODK0,i+1

6．6高度為h的完全二叉樹至少有多少個(gè)結(jié)點(diǎn)？至多有多少個(gè)結(jié)點(diǎn)？解：

至少有：2h-1，至多有：2h-1

6．7在具有n個(gè)結(jié)點(diǎn)的k叉樹（k≥2）的k叉樹鏈表表示中，有多少個(gè)空指針？解：

（k-1）n+1個(gè)空指針

6．8假設(shè)二叉樹包含的結(jié)點(diǎn)數(shù)據(jù)為1，3，7，2，12。（1）畫出兩棵高度最大的二叉樹；

（2）畫出兩棵完全二叉樹，要求每個(gè)雙親結(jié)點(diǎn)的值大于其孩子結(jié)點(diǎn)的值。6．9試找出分別滿足下面條件的所有二叉樹：

（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；（3）前序序列和后序序列相同；（4）前序、中序、后序序列均相同。解：

（1）空二叉樹或任一結(jié)點(diǎn)均無左子樹的非空二叉樹（2）空二叉樹或任一結(jié)點(diǎn)均無左子樹的非空二叉樹（3）空二叉樹或僅有一個(gè)結(jié)點(diǎn)的二叉樹（4）同（3）

6．10試采用順序存儲方法和鏈接存儲方法分別畫出6.30所示各二叉樹的存儲結(jié)構(gòu)。解：①順序存儲：

(a)12φφ3φφφφ4φφφφφφφφφφ5

(b)1φ2φφ3φφφφφφφ4φφφφφφφφφφφφ5

(c)1φ2φφ34φφφφ56φφφφφφφφφφφ78(d)1234φ56φ7φφφφ89②連接存儲：

6．11分別寫出圖6.30所示各二叉樹的前序、中序和后序序列。解：

6．12若二叉樹中個(gè)結(jié)點(diǎn)的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列的中序列均能惟一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能惟一地確定一棵二叉樹。

（1）已知一棵二叉樹的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF，請畫

出此二叉樹。

（2）已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，請畫出

此二叉樹。

（3）已知兩棵二叉樹前序序列和后序序列均為AB和BA，請畫出這兩棵不同的二叉樹。

解：

6．13對二叉樹中結(jié)點(diǎn)進(jìn)行按層次順序（每一層自左至右）的訪問操作稱為二叉樹的層次遍歷，遍歷所得到的結(jié)點(diǎn)序列稱為二叉樹的層次序列?，F(xiàn)已知一棵二叉樹的層次序列為ABCDEFGHIJ，中序序列為DBGEHJACIF，請畫出該二叉樹。解：

6．14試畫出圖6.30所示各二叉樹的前序、中序和后序線索樹及相應(yīng)的線索鏈表。解：

（以c為例）

①前序：12357864②前序：17583624

6．15在何種線索樹中，線索對所求指定結(jié)點(diǎn)在相應(yīng)次序下的前趨和后繼并無幫助？解：

在前序線索樹中找某一點(diǎn)的前序前趨以及在后序線索樹中尋找某一點(diǎn)的后繼，線索并無多大幫助。

6．16對圖6.31所示的森林：

（1）求各樹的前序序列和后序序列：（2）求森林的前序序列和后序序列：（3）將此森林轉(zhuǎn)換為相應(yīng)的二叉樹：

（4）給出（a）所示樹的雙親鏈表表示、孩子鏈表表示、雙親孩子鏈表表示及孩子兄

弟鏈表表示等四種存儲結(jié)構(gòu)，并指出哪些存儲結(jié)構(gòu)易于求指定結(jié)點(diǎn)的祖先，哪些易于求指定結(jié)點(diǎn)的后代？

解：

(1)abc

前序ABCDEFGHIJKLMPQRNO后序BDEFCAIJKHGQRPMNOL(2)前序：ABCDEFGHIGKLMPQRNO后序：BDEFCAIJKHGQRPMNOL

(3)二叉樹(4)1

①孩子鏈表表示發(fā)：②雙親鏈表表示發(fā)：

結(jié)點(diǎn)0123456dataABCDEFparent-1011333

③雙親孩子鏈表：④孩子兄弟鏈表表示：

⑤易于求祖先：雙親鏈表面雙親孩子⑥易于求后代：孩子鏈表雙親孩子

6．17畫出圖6.32所示的各二叉樹所應(yīng)的森林

6．18高度為h的嚴(yán)格二叉樹至少有多少個(gè)結(jié)點(diǎn)？至多有多少個(gè)結(jié)點(diǎn)？解：

最多有2n-1最少有2n-1

6．19在什么樣的情況下，等長編碼是最優(yōu)的前綴碼？解：

當(dāng)字符集中的各字符使用頻率均勻時(shí)。6．20下屬編碼哪一組不是前綴碼？

{00，01，10，11}，{0，1，00，11}，{0，10，110，111}解：

因?yàn)榍熬Y碼中不可能存在一個(gè)元素是另一個(gè)的前面部分。所以第二組不是。

6．20假設(shè)用于通信的電子由字符集{a,b,c,d,e,f,g,h}中的字母構(gòu)成，這8個(gè)字母在電文中

出現(xiàn)的概率分別為{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}（1）為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。

（2）若用三位二進(jìn)制數(shù)（0~7）對這個(gè)8個(gè)字母進(jìn)行等長編碼，則哈夫曼編碼的平均

碼長是等長編碼的百分之幾？它使電文總長平均壓縮多少？

解：

①②哈夫曼編碼碼長：

4*0.07+2*0.19+5*0.02+4*0.06+5*0.03+2*0.21+4*0.1=2.71等長碼長：3

905平均縮了10%

（二）算法設(shè)計(jì)題

6.22二叉樹的遍歷算法可寫為通用形式。例如，通用的中序遍歷為：

voidInorder(BinTreeT,void(*Visit)(Datatypex)){if(T)

{Inorder(T->lchild,Visit);/*遍歷左子樹*/

Visit(T->data);/*通過函數(shù)指針調(diào)用它所指的函數(shù)來訪問結(jié)點(diǎn)*/Inorder(T->rchild,Visit);/*遍歷右子樹*/}}

其中Visit是一個(gè)函數(shù)指針，它指向形如voidf（DdataTypex）的函數(shù)。因此我們可以將訪問結(jié)點(diǎn)的操作寫在函數(shù)f中，通過調(diào)用語句Inorder（root，f）將f的地址傳遞給Visit，來執(zhí)行遍歷操作。請寫一個(gè)打印結(jié)點(diǎn)的數(shù)據(jù)的函數(shù)，通過調(diào)用上述算法來完成書中6.3節(jié)的中序遍歷。

解：

#include“stdio.h〞#defineNull0

typedefcharDataType;typedefstructnode{

DataTypedata;

Structnodelchild,rchild;}BinTree;BinTree*root;BinTree*Q[100];

BinTreeCreateBinTree()/*建立二叉樹*/{

charch;

intfront,rear;

BinTreeroot,s;Root=Null;front=1;rear=0;

ch=getchar();while(ch!=’#’){

s=Null;

if(ch!=’@’){

s=(BinTree*)malloc(sizeof(BinTree));s->data=ch;s->lchild=Null;s->rchild=Null;}

rear++;Q[rear]=s;

if(rear==1)root=s;else{

if(selseQ[front]->rchild=s;if(rear%2==1)front++;}

ch=getchar();}

returnroot;}

main(){

root=CreateBinTree();Inorder(root);}

①中序遍歷法之一

Inorder(BinTree*t){

if(t){

Inorder(t->lchild);Visit(t->data);

Inorder(t->rchild);}}

Vist(inti){

printf(“%c〞,i);}

②中序遍歷法之二

Inorder(BinTree*t){

if(t){

Inorder(t->lchild);printf(“%c〞,t->data);Inorder(t->rchild);}}

6.23以二叉鏈表為存儲結(jié)構(gòu)，分別寫出求二叉樹結(jié)點(diǎn)總數(shù)及葉子總數(shù)的算法。解：

①計(jì)算結(jié)點(diǎn)總數(shù)

intCountNode(BinTree*root){

intnum1,num2;

if(root==Null)return(0);

elseif(root->lchild==Nullelse{

num1=CountNode(root->lchild);num2=CountNode(root->rchild);return(num1+num2+1);}}

②計(jì)算葉子總數(shù)

intCountLeafs(BinTree*root){

intnum1,num2;

if(root==Null)return(0);

elseif(root->lchild==Nullelse

{

num1=CountLeafs(root->lchild);num2=CountLeafs(root->rchild);return(num1+num2);

}}

6.24以二叉鏈表為存儲結(jié)構(gòu)，分別寫出求二叉樹高度及寬度的算法。所謂寬度是指在二叉樹的各層上，具有結(jié)點(diǎn)數(shù)最多的那一層上的結(jié)點(diǎn)總數(shù)。解：

①求樹的高度

思想：對非空二叉樹，其深度等于左子樹的最大深度加1。

IntDepth(BinTree*T){

intdep1,dep2;

if(T==Null)return(0);else{

dep1=Depth(T->lchild);dep2=Depth(T->rchild);

if(dep1>dep2)return(dep1+1);elsereturn(dep2+1);}

②求樹的寬度

思想：按層遍歷二叉樹，采用一個(gè)隊(duì)列q，讓根結(jié)點(diǎn)入隊(duì)列，最終出隊(duì)列，若有左右子樹，則左右子樹根結(jié)點(diǎn)入隊(duì)列，如此反復(fù)，直到隊(duì)列為空。intWidth(BinTree*T)

{

intfront=-1,rear=-1;/*隊(duì)列初始化*／intflag=0,count=0,p;

/*p用于指向樹中層的最右邊的結(jié)點(diǎn)，標(biāo)志flag記錄層中結(jié)點(diǎn)數(shù)的最大值。*／if(T!=Null){

rear++;q[rear]=T;flag=1;p=rear;}

while(frontfront++;T=q[front];

if(T->lchild!=Null){

rear++;

q[rear]=T->lchild;count++;}

if(T->rchild!=Null){

rear++;

q[rear]=T->rchild;count++;}

if(front==p)/*當(dāng)前層已遍歷完畢*/{

if(flag-1){

T=stack[top];top--;

if(T->child!=Null||T->rchild!=Null)

{/*交換結(jié)點(diǎn)的左右指針*/temp=T->lchild;

T->lchild=T->rchild;T->rchild=temp;}

if(T->lchild!=Null){

top++;

stack[top]=T->lchild;}

if(T->rchild!=Null){

top++;

stack[top]=T->rchild;}}

}/*endwhile*/}/*endif*/

main(){

intI,j,k,l;printf(“\\n〞);

root=CreateBinTree();Inorder(root);i=CountNode(root);j=CountLeafs(root);k=Depth(root);l=Width(root);

printf(“\\nTheNode’sNumber:%d〞,i);printf(“\\nTheLeafs’sNumber:%d〞,j);printf(“\\nTheDepthis:%d〞,k);printf(“\\nThewidthis:%d〞,l);Swap(root);

Printf(“\\nTheswapTreeis:〞);Inorder(root);}6．26以二叉表為存儲結(jié)構(gòu)，寫一個(gè)拷貝二叉表的算法哦（BinTreeroot,BinTree*newroot）,其中新樹的結(jié)點(diǎn)是動(dòng)態(tài)申請的，為什么newroot要說明為BinTree形指針的指針？解：

CopyTree(BinTreeroot,BinTree*(newroot))}

if(root!=Null){

*newroot=(BinTree*)malloc(sizeof(BinTree));(*newroot)->data=root->data;

CopyTree(root->lchild,CopyTree(root->rchild,Inorder(*newroot);}

elsereturn(Null);}

main(){

BinTree*newroot;intI,j,k,l;printf(“\\n〞);

root=CreateBinTree();Inorder(root);Printf(“\\n〞);/*Swap(root);*/

CopyTree(root,}

6．27以二叉樹表為存儲結(jié)構(gòu)，分別寫處在二叉樹中查找值為x的結(jié)點(diǎn)在樹中層數(shù)的算法。解：

inth=-1,lh=1,count=0;charx=’c’;/*賦初值*/

Level(BinTreeT,inth,intlh)/*求X結(jié)點(diǎn)在樹只的層樹*/{

if(T==Null)h=0;

elseif(T->data==x){

h=lh;count=h;}else{

h++;

Level(T->lchild,h,lh);

If(h==-1)Level(T->rchild,h,lh);}}

main(){

BinTree*(*newroot);Printf(“\\n〞);

Root=CreateBinTree();Inorder(root);Printf(“\\n〞);Level(root,h,lh);Printf(“%d〞,count);}

6.28一棵n個(gè)結(jié)點(diǎn)的完全二叉樹以向量作為存儲結(jié)構(gòu)，試寫一非遞歸算法實(shí)現(xiàn)對該樹的前序遍歷。解：

思想：采用棧，先讓跟結(jié)點(diǎn)如棧，然后退棧，如有左右孩子，則先讓右孩子如棧，然后左孩子如棧，如此反復(fù)實(shí)現(xiàn)前序遍歷。

typedefstruct{

intdata[100];

inttop;}seqstack;seqstack*s;

Perorder(chara[],intn){

inti=1,count=1;s->top=-1;

if(n==0)return(0);else{

if(Itop++;

s->data[s->top]=a[I];}

while(countdata[s->top]);count++;s->top--;

if(s->data[s->top]);==a[i]){/*若棧頂結(jié)點(diǎn)為a[i]結(jié)點(diǎn)，則退棧，保證父結(jié)點(diǎn)比孩子結(jié)點(diǎn)先退棧*/printf(“%c〞,s->data[s->top]);count++;s->top--;}

if((2*i+1)top++;

s->data[s->top]=a[i+1];s->top++;

s->data[s->top]=a[i];

}

elseif(a*itop++;

s->data[s->top]=a[i];

}

elseif(i/2%2==1)i=i/2/2+1;

/*父結(jié)點(diǎn)沒有右兄弟，回到祖父結(jié)點(diǎn)大右兄弟*/elsei=i/2+1;/*回到父結(jié)點(diǎn)的右兄弟*/}}}main(){

charA[]=“kognwyuvb〞;intn=strlen(A);

s=(seqstack*)malloc(sizeof(seqstack));printf(“\\n〞);Perorder(A,n);}6．29以二叉樹表為存儲結(jié)構(gòu)，寫一算法對二叉樹進(jìn)行層次遍歷（定義見習(xí)題6.13）。提醒：應(yīng)使用隊(duì)列來保存各層的結(jié)點(diǎn)。解：

voidTransLevel(BinTree*T){

intfront=0,rear=0;intp;

if(T!=Null){

printf(“%c〞,T->data);q[rear]=T;rear++;}

while(frontlchild!=Null){

printf(“%c〞,T->lchild->data);q[rear]=T->lchild;rear++;

}

if(T->rchild!=Null){

printf(“%c〞,T->rchild->dara);q[rear]=T->rchild;rear++;}

}

}

main(){

printf(“\\n〞);

root=CreateBinTree();Inorder(root);Printf(“\\n〞);TransLevel(root);}

6．30以二叉樹表為存儲結(jié)構(gòu)，寫一算法用括號形式（keyLT,RT）打印二叉樹，其中key是根結(jié)點(diǎn)數(shù)據(jù)，LT和RT分別是括號形式的左右子樹。并且要求：空樹不打印任何信息，一給結(jié)點(diǎn)x的樹打印形式是x，而不應(yīng)是（x，，）d的形式。解：

viodPrint(BinTreeT)/*喲感括號形式打印二叉樹*/{

if(T!=Null){

if(T->lchild==Null

else/*T->lchild!=Null||T->rchild!=Null*/{

printf(“(〞);

printf(“%c〞,T->data);

if(T->lchild->lchild==NullPrint(T->lchild);

if(T->rchild!=Nulll)printf(“,〞);printf(“)〞);printf(“)〞);}}}main(){

printf(“\\n〞);

root=CreateBinTree();Inorder(root);printf(“\\n〞);Print(root);}

6.31以線索鏈表為存儲結(jié)構(gòu)，分別寫出在前序線索樹中查找給定結(jié)點(diǎn)*p的后繼，以及在后序線索樹中查找*p的后序前趨的算法。解：

①找結(jié)點(diǎn)p的前序后繼

BinTheNode*PreorderSuccessor(BinThrNode*p){

BinThrNode*q;

if(p->rtag==Thread)

q=p->rchild;/*右子樹為空*/

else

{if(p->ltag==list)

q=p->lchild；/*左子樹非空*/

if(p->ltag==Thread)

q=p->rchild;/*左子樹為空*/

}

return(q);}

②找結(jié)點(diǎn)p的后序繼

BinTheNode*PostorderSuccssor(BinThrNode*p){

BinThrNode*q;

if(p->ltag==Thread)

q=p->lchild;/*左子樹為空*/else

{if(p->rtag==list)

q=p->rchild;/*右子樹非空*/if(p->ltag==Thread)

q=p->lchild;/*右子樹為空*/}

return(q);}

/*說明：list\\Thread為特別標(biāo)志，其值分別為0與1.*/6．32完成6.6.1節(jié)算法CreateHuffmanTree中調(diào)用的三個(gè)函數(shù)：InputWeight,SelecMin和InitHuffmanTree.解：

①初始化

InitHuffmanTree(HuffmanTreeT){inti;

for(i=0;iparent=-1;

T[i]->lchild=-1;T[i]->rchild=-1;T[i]->weigh=0;

}}

②讀入葉子結(jié)點(diǎn)權(quán)值

InputWeigh(HuffmanTreeT)

{intI;

for(i=0;iparent==-1)if(T[j]->weighweigh;p2=p1;p1=j;}

else

if(T[j]->weighweigh;/*改變最小權(quán)及對應(yīng)位置*/p2=j;}

}6．33分別寫出對文件進(jìn)行哈夫謾碼的算法，以及對編碼文件進(jìn)行解碼的算法。為簡單起見，可以假設(shè)文件存放在一個(gè)字符向量。解：

①編碼算法

設(shè)哈夫曼樹已求出。

HuffmanCode(code,tree)Codetypecode[];

Huffmantypetree[]/*以求出*/{intI,j,c,p;

codetypecd;/*緩沖區(qū)變量*/for(i=0;istart=n;c=i+1;

p=tyee[i]->parent;while(p!=0){cd->start=n;c=i+1;

p=tyee[i]->parent;while(p!=0)

{cd->start--;

if(tree[p-1]->lchild==c)

cd->bit[cd-start]=’0’;/*type[i]是左子樹，生成代碼為‘0’*/else

cd->bit[cd->start]=’1’；/*type[i]是右子樹，生成代碼為‘1’*/

c=p;

p=tree[p-1]->parent;}

code[i]=cd;}}注：結(jié)構(gòu)體typedefstruct

{charbit[n];/*位串*/

intstart;/*編碼在位串的起始位置*/

charch;/*字庫*/

}codetype;

codetypecode[n];②譯碼算法

Decode(code,tree)Codetypecode[];Huffmantypetree[];{intI,j,c,p,b;

intendfily=-1;/*電文終止標(biāo)志*/

i=m;/*從根結(jié)點(diǎn)開始往下探尋*/scanf(“d〞，/*讀入一個(gè)二進(jìn)制代碼*/while(b!=endfily){if(b==0)

i=tyee[i]->lchild-1;/*走向左孩子*/else

i=tyee[i]->rchild-1;/*走向右孩子*/

if(tyee[i].child==0)