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

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)電子教案第六章同步綜合練習(xí)及參考答案（一）基礎(chǔ)知識題6.1加設(shè)在樹中，結(jié)點x是結(jié)點y的雙親時，用(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）哪個是根結(jié)點？（2）哪些是葉結(jié)點？（3）哪個是g的雙親？（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孫？

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

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

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

（2）m,n,j,k,l是葉結(jié)點。（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的樹有二個分支，沒有左右之分；以可二叉樹也有兩個分支，但有左右之分，且左右不能交換。

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

3個結(jié)點樹形態(tài)：3個結(jié)點的二叉樹：

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

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

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

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

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

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

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

（1）Ki-1（2）

（3）Ki+j-1

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

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

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

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

（k-1）n+1個空指針

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

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

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

（1）空二叉樹或任一結(jié)點均無左子樹的非空二叉樹（2）空二叉樹或任一結(jié)點均無左子樹的非空二叉樹（3）空二叉樹或僅有一個結(jié)點的二叉樹（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若二叉樹中個結(jié)點的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列的中序列均能惟一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能惟一地確定一棵二叉樹。

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

出此二叉樹。

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

此二叉樹。

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

解：

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

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

（以c為例）

①前序：12357864②前序：17583624

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

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

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

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

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

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

解：

(1)abc

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

(3)二叉樹(4)1

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

結(jié)點0123456dataABCDEFparent-1011333

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

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

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

6．18高度為h的嚴格二叉樹至少有多少個結(jié)點？至多有多少個結(jié)點？解：

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

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

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

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

因為前綴碼中不可能存在一個元素是另一個的前面部分。所以第二組不是。

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

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

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

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

解：

①②哈夫曼編碼碼長：

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è)計題

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

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

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

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

其中Visit是一個函數(shù)指針，它指向形如voidf（DdataTypex）的函數(shù)。因此我們可以將訪問結(jié)點的操作寫在函數(shù)f中，通過調(diào)用語句Inorder（root，f）將f的地址傳遞給Visit，來執(zhí)行遍歷操作。請寫一個打印結(jié)點的數(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é)點總數(shù)及葉子總數(shù)的算法。解：

①計算結(jié)點總數(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);}}

②計算葉子總數(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é)點數(shù)最多的那一層上的結(jié)點總數(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);}

②求樹的寬度

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

{

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

/*p用于指向樹中層的最右邊的結(jié)點，標志flag記錄層中結(jié)點數(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é)點的左右指針*/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)，寫一個拷貝二叉表的算法哦（BinTreeroot,BinTree*newroot）,其中新樹的結(jié)點是動態(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é)點在樹中層數(shù)的算法。解：

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

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

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個結(jié)點的完全二叉樹以向量作為存儲結(jié)構(gòu)，試寫一非遞歸算法實現(xiàn)對該樹的前序遍歷。解：

思想：采用棧，先讓跟結(jié)點如棧，然后退棧，如有左右孩子，則先讓右孩子如棧，然后左孩子如棧，如此反復(fù)實現(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é)點為a[i]結(jié)點，則退棧，保證父結(jié)點比孩子結(jié)點先退棧*/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é)點沒有右兄弟，回到祖父結(jié)點大右兄弟*/elsei=i/2+1;/*回到父結(jié)點的右兄弟*/}}}main(){

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

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

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é)點數(shù)據(jù)，LT和RT分別是括號形式的左右子樹。并且要求：空樹不打印任何信息，一給結(jié)點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é)點*p的后繼，以及在后序線索樹中查找*p的后序前趨的算法。解：

①找結(jié)點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é)點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為特別標志，其值分別為0與1.*/6．32完成6.6.1節(jié)算法CreateHuffmanTree中調(diào)用的三個函數(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é)點權(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分別寫出對文件進行哈夫謾碼的算法，以及對編碼文件進行解碼的算法。為簡單起見，可以假設(shè)文件存放在一個字符向量。解：

①編碼算法

設(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;/*電文終止標志*/

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

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

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

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