數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)作業(yè)第三章樹

一、選擇題1、在一棵樹中，如果結(jié)點(diǎn)A有3個(gè)兄弟，B是A的雙親，則B的度為D A.1 B.2 C.3 D.42、深度為h的完全二叉樹至少有D個(gè)結(jié)點(diǎn)，至多有B個(gè)結(jié)點(diǎn) A.2h B.2h-1 C.2h+1 D.2h-12^(h-1)-1+1=2^(h-1)

前（n-1）層滿，第h層只有一結(jié)點(diǎn)3、具有n個(gè)結(jié)點(diǎn)的滿二叉樹有C個(gè)葉結(jié)點(diǎn)。 A.n/2 B.(n-1)/2 C.(n+1)/2 D.n/2+1因?yàn)槎鏄渲?，有這樣一個(gè)性質(zhì)，如果其終端結(jié)點(diǎn)數(shù)（也就是葉子節(jié)點(diǎn)）的個(gè)數(shù)為n1，度為2的結(jié)點(diǎn)數(shù)為n2，則n1=n2+1;

假設(shè)葉子節(jié)點(diǎn)有x個(gè)，則度為2的個(gè)數(shù)為x-1：

所以：2x-1=n;所以x=(n+1)/2(滿二叉樹)

所以葉子節(jié)點(diǎn)個(gè)數(shù)為：(n+1)/2

非終端結(jié)點(diǎn)為：(n+1)/2-14、一棵具有25個(gè)葉結(jié)點(diǎn)的完全二叉樹最多有B個(gè)結(jié)點(diǎn)。 A.48 B.49 C.50 D.515、已知二叉樹的先根遍歷序列是ABCDEF，中根遍歷序列是CBAEDF，則后根遍歷序列是A。 A.CBEFDA B.FEDCBA C.CBEDFA D.不定6、具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有B個(gè)度為2的結(jié)點(diǎn)。 A.8 B.9 C.10 D.117、一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足C。 A.所有非葉結(jié)點(diǎn)均無(wú)左孩子 B.所有非葉結(jié)點(diǎn)均無(wú)右孩子 C.只有一個(gè)葉子結(jié)點(diǎn) D.A和B同時(shí)成立8、在線索二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是B。 A.t->left=NULL B.t->ltag=TRUE C.t->ltag=TRUE且t->left=NULL D.以上都不對(duì)9、n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為C。 A.2n B.n-1 C.n+1 D.nn-1表示結(jié)點(diǎn)的左右子樹，其余n-1指針為空線索取代原來(lái)的空鏈10、二叉樹按照某種順序線索化后，任一結(jié)點(diǎn)都有指向其前驅(qū)和后繼的線索，這種說(shuō)法B。 A.正確 B.錯(cuò)誤 C.不確定 D.都有可能11、具有n(n>1)個(gè)結(jié)點(diǎn)的完全二叉樹中，結(jié)點(diǎn)i(2i>n)的左孩子結(jié)點(diǎn)是D。 A.2i B.2i+1 C.2i-1 D.不存在12、具有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為C。 A.5 B.6 C.7 D.813、將一顆有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下、從左到右一次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的五、已知非空二叉樹T，寫一個(gè)算法，求度為2的結(jié)點(diǎn)的個(gè)數(shù)。要求： 1、定義二叉樹的抽象數(shù)據(jù)類型和型BTREE，并定義基本操作。 2、編寫函數(shù)count2(BTREET)，返回度為2的節(jié)點(diǎn)的個(gè)數(shù)。 3、在主函數(shù)中，構(gòu)建一個(gè)二叉樹，并驗(yàn)證所編寫的算法。六、用遞歸方法寫一個(gè)算法，求二叉樹的葉子結(jié)點(diǎn)數(shù)intleafnum(BTREET)。要求：定義二叉樹的抽象數(shù)據(jù)類型和型BTREE，并定義基本操作。編寫函數(shù)leafnum(BTREET)，返回樹T的葉子節(jié)點(diǎn)的個(gè)數(shù)。在主函數(shù)中，構(gòu)建一個(gè)二叉樹，并驗(yàn)證所編寫的算法。畫出下圖所表示的二叉樹的中序線索二叉樹和先序線索二叉樹。八、已知二叉樹的先根序列是AEFBGCDHIKJ，中根序列是EFAGBCHKIJD，畫出此二叉樹，并畫出后序線索二叉樹。九、在中序線索二叉樹中插入一個(gè)結(jié)點(diǎn)Q作為樹中某個(gè)結(jié)點(diǎn)P的左孩子，試給出相應(yīng)的算法。要求：定義中序線索二叉樹的型THTREE以及基本操作。定義函數(shù)voidLInsert(THTREEP,THTREEQ);實(shí)現(xiàn)題目要求的操作。在主函數(shù)中，利用操作RInsert和LInsert構(gòu)造一個(gè)線索二叉樹，并中序輸出二叉樹的結(jié)點(diǎn)的元素，驗(yàn)證結(jié)果。#include<iostream>#include<iomanip>#include<cmath>#include<cstdlib>#include<string>usingnamespacestd;typedefintelementtype;structnode{//節(jié)點(diǎn)的型 node*lchild; node*rchild; boolltag; boolrtag; elementtypeelement;};typedefnode*head;//指向樹根roottypedefnode*tree;//指向線索樹的根節(jié)點(diǎn)voidmakeNull(head&h)//將線索二叉樹置空{(diào) h->lchild=h; h->ltag=false; h->rchild=h; h->rtag=true;}headpointTotree(head&h,tree&t)//令head指向tree,注意head指向的并不是根節(jié)點(diǎn)，tree指向根節(jié)點(diǎn){ h->lchild=t; h->rchild=h; h->ltag=true; h->rtag=true; returnh;}//中根遍歷的下一個(gè)節(jié)點(diǎn)node*inNext(node*p){ node*q=p->rchild; if(p->rtag==true)//如果有右子樹，找出右子樹的最左節(jié)點(diǎn) while(q->ltag==true) q=q->lchild; returnq;}//中根遍歷的上一個(gè)節(jié)點(diǎn)node*inPre(node*p){ node*q=p->lchild; if(p->ltag==true)//如果P的左子樹存在，則其前驅(qū)結(jié)點(diǎn)為左子樹的最右結(jié)點(diǎn) while(q->rtag==true) q=q->rchild; returnq;//左子樹的最右結(jié)點(diǎn)}//中序遍歷voidthInOrder(headh){ node*temp; temp=h; do{ temp=inNext(temp); if(temp!=h) cout<<temp->element<<""; }while(temp!=h);}//插入右孩子voidrInsert(node*s,node*r){ node*w; r->rchild=s->rchild; r->rtag=s->rtag; r->lchild=s; r->ltag=false;//新插入的節(jié)點(diǎn)木有左子樹，所以lchild指向的是父節(jié)點(diǎn) s->rchild=r; s->rtag=true;//原節(jié)點(diǎn)的右孩子為新插入的節(jié)點(diǎn) if(r->rtag==true){ //這里是神馬意思呢∑q|?Д?|p，就是如果被插節(jié)點(diǎn)s有右子樹， //找出被插節(jié)點(diǎn)s的的next位置，即右子樹中的最左節(jié)點(diǎn)，令其lchild指向新添加的節(jié)點(diǎn)r //因?yàn)椴迦肭霸撟钭蠊?jié)點(diǎn)的lchild指向的是原來(lái)節(jié)點(diǎn)s w=inNext(r); w->lchild=r; }}//插入左孩子voidlInsert(node*s,node*l){ node*w; l->lchild=s->lchild; l->ltag=s->ltag; l->rchild=s; l->rtag=false; s->lchild=l; s->ltag=true; if(l->ltag==true){//與插入右孩子方法相似，只需把左右方向?qū)φ{(diào)即可 w=inPre(l); w->rchild=l; }}intmain(){ headh=newnode; node*root=newnode; node*lc=newnode; node*rc=newnode; node*c=newnode; root->element=1; lc->element=2; rc->element=3; c->element=4; h->rchild=root; h->lchild=h; h->ltag=true; h->rtag=true; root->lchild=h; root->rchild=h; root->ltag=false; root->rtag=false; //構(gòu)造線索樹213 lInsert(root,lc); rInsert(root,rc); thInOrder(h); cout<<endl; //root左邊插入C lInsert(root,c); thInOrder(h); return0;}十、假設(shè)現(xiàn)在有如下的元素：7、16、49、82、5、31、6、2、44。畫出將每一個(gè)元素插入堆中以后的最大堆。要求：利用基本操作Insert的基本原理，先用第一個(gè)元素7構(gòu)成一個(gè)二叉樹，然后將第二個(gè)元素16插入該二叉樹中，再將第三個(gè)元素49插入堆中，……，直到最后一個(gè)元素插入為止。上述過(guò)程要求畫圖完成。十一、編寫一個(gè)函數(shù)，在最大堆中查找任意元素，并分析其時(shí)間復(fù)雜度。要求：定義最大堆的型HEAP及其基本操作。定義函數(shù)intFind(HEAPH,Elementtypee)，查找e是否為堆的元素，如果是，返回該元素在堆中的位置，如果不是，返回0。（提示：利用最大堆的元素特點(diǎn)進(jìn)行查找，可降低復(fù)雜度）在主函數(shù)中首先構(gòu)建一個(gè)二叉樹，然后驗(yàn)證所構(gòu)造的函數(shù)。typedefstryct{intkey;datathpedata;}elementtype;Typedefstruct{Elementtypeelements[Maxsize];intn;}HEAP;VoidMaxHeap(HEAPheap)//創(chuàng)建一個(gè)空堆{heap.n=0;}BoolHeapEmpty(HEAPheap)//判斷堆是否為空{(diào)If(!(heap.n))returntrue;Elsereturnfalse;}BoolHeapFull(HEAPheap)//判斷堆是否為滿{if(heap.n==Maxsize-1)returntrue;Elsereturnfalse;}VoidInsert(HEAP&heap,elementtypeelement)//在堆heap中插入元素為element的結(jié)點(diǎn){IntI;If(!HeapFull(heap)){I=heap.n+1;While((i!=1)&&(element.data>heap.elements[i/2].data)){heap.elements[i]=heap.elements[i/2];i/=2;}Heap.n++;Heap.elements[i]=element;}}ElementtypeDeleteMax(HEAP&heap)//刪除堆中最大元素{intparaent=1,child=2;Elementtypeelement,tmp;If(!HeapEmpty(heap)){Element=heap.elements[1];Tmp=heap.elements[heap.n-];While(child<=heap.n){If((child<heap.n)&&(heap.elements[child].data<heap.elements[child+1].data))child++;If(tmp.data>=heap.elements[child].data)break;Heap.elements[paraent]=heap.elements[child];Paraent=child;Child*=2;}Heap.elements[paraent]=tmp;Returnelement;}}IntFind(HEAP,datatypex){intm=1;While((m<H.n)&&(H.elements[m].data!=x)){If(H.elements[m].data<x)If(H.elements[m+1].data>=x)m++;elsereturn0;elsem++;}if(m<=H.n)returnm;elsereturn0;}Intmain(){HEAPH;Elementtypeelement;Intdata[]={1,3,5,7,9,11,13};H.n=0;For(inti=0;i<7;i++){element.key=i+1;Element.data=data[i];Insert(H,element);}for(inti;i<=H.n;i++)cout<<H.elements[i].data<<endl;DeleteMax(H);For(inti=1;i<=H.n;i++)cout<<H.elements[i].data<<’’;Cout<,endl;Cout<<”查找的元素：”;Intx;Cin>>x;Cout<<Find(H,x)<<endl;}十二、給定葉子結(jié)點(diǎn)的權(quán)值集合{15,3,14,2,6,9,16,17}，構(gòu)造相應(yīng)的哈夫曼樹，并計(jì)算其帶權(quán)路徑長(zhǎng)度。十三、已知n=9和一組等價(jià)關(guān)系：1≡5、6≡8、7≡2、9≡8、3≡7、4≡2、9≡3 試應(yīng)用抽象數(shù)據(jù)類型MFSET設(shè)計(jì)一個(gè)算法，按輸入的等價(jià)關(guān)系進(jìn)行等價(jià)分類。#include<iostream.h>

#define

n

9//MEFSET元素個(gè)數(shù)

//MFSET抽象數(shù)據(jù)型struct

mfnode{

int

father;//指向父節(jié)點(diǎn)的鏈

int

count;//樹結(jié)點(diǎn)個(gè)數(shù)

};

typedef

mfnode

MFSET[n+1];

void

Union(int

A,

int

B,

MFSET

C)//合并A和B

{

if(C[A].count>C[B].count)

{

C[B].father=A;//B并入A

C[A].count+=C[B].count;

}

else

{

C[A].father=B;//A并入B

C[B].count+=C[A].count;

}

}

int

Find(int

x,

MFSET

C)//求包含元素x的樹的根

{

int

f;

f=x;

while(C[f].father!=0)//未到根

f=C[f].father;

return

f;

}

void

Initial(int

A,

MFSET

C)//集合A只包含元素A

{

C[A].father=0;

C[A].count=1;

}

//

等價(jià)分類

void

Equivalence(MFSET

S)

{

int

i,

j,

m,

k;

for(i=1;

i<=n;

i++)

Initial(i,

S);

cin>>i;

cin>>j;

while(!(i==0

&&

j==0))//輸入0,0結(jié)束等價(jià)分類

{

k=Find(i,

S);

m=Find(j,

S);

if(k!=m)

Union(k,

m,

S);

cin>>i;

cin>>j;

}

}

void

print_MFSET(MFSET

S)//輸出等價(jià)類

{

int

r[n+1][n+1]={0},

k;

for(int

i=1;

i<=n;

i++)

{

k=Find(i,

S);

r[k][0]++;

r[k][r[k][0]]=i;

}

for(i=1;

i<=n;

i++)

{

if(r[i][0]>0)

{

cout<<'{';

for(int

j=1;

j<r[i][0];

j++)

cout<<r[i][j]<<',';

cout<<r[i][r[i][0]]<<'}'<<endl;

}

}

}

void

main()

{

MFSET

S;

Equivalence(S);

print_MFSET(S);

}

十四、畫出下圖所示的森林經(jīng)轉(zhuǎn)換后所對(duì)應(yīng)的二叉樹，并指出在二叉樹中某結(jié)點(diǎn)為葉子結(jié)點(diǎn)時(shí)，所對(duì)應(yīng)的森林中結(jié)點(diǎn)應(yīng)滿足的條件。十五、已知森林F的先根序列為：ABCDEFGHIJKL，后根序列為：CBEFDGAJIKLH，試畫出森林F。提示：先畫出森林F所對(duì)應(yīng)的二叉樹B，然后再將B轉(zhuǎn)換為森林。十六、畫出表達(dá)式(A+B*C/D)*E+F*G所對(duì)應(yīng)的樹結(jié)構(gòu)，并寫出該表達(dá)式的波蘭表示式和逆波蘭表示式。十七、利用逆波蘭表達(dá)式求一個(gè)四則混合元算的值。具體要求：定義二叉樹的型BTREE和位置的型position。實(shí)現(xiàn)二叉樹的基本操作。實(shí)現(xiàn)將一個(gè)四則混合運(yùn)算轉(zhuǎn)換成二叉樹的函數(shù)：BTREEconvert(char*express)，其中參數(shù)express為四則混合運(yùn)算表達(dá)式，返回值為生成的樹。實(shí)現(xiàn)計(jì)算四則混合運(yùn)算的值的函數(shù)：doublecomputer(BTREEbt)，其中，參數(shù)bt為四則運(yùn)算所對(duì)應(yīng)的樹，返回值為計(jì)算結(jié)果。提示：先求樹的的波蘭表達(dá)式，然后利用棧結(jié)構(gòu)計(jì)算表達(dá)式的值。在主函數(shù)中進(jìn)行測(cè)試，求2+3*（5+8）/4-5的值。#include"./stack.cpp"#include<iostream>#include<sstream>#defineMAXSIZE30usingnamespacestd;charmatch[]=">><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>>><<<<<=";charopera[]="+-*/()@";constchar&Match(constchar&ch1,constchar&ch2){ inti=0,j=0; while(opera[i]!=ch1)i++; while(opera[j]!=ch2)j++; returnmatch[i*7+j];}classTNode{public: TNode(stringstr="",intb=0,TNode*l=NULL,TNode*r=NULL,TNode*p=NULL){ strcpy(id,str.c_str()); bit=b; left=l; right=r; parent=p; } TNode(constcharch,TNode*l=NULL,TNode*r=NULL,TNode*p=NULL){ id[0]=ch; id[1]=0; bit=0; left=l; right=r; parent=p; } constTNode&operator=(constTNode&tn){ strcpy(id,tn.id); bit=tn.bit; left=tn.left; right=tn.right; parent=tn.parent; } charid[MAXSIZE]; intbit; TNode*parent,*left,*right;};intReadExpr(char*str,char*expr,intstart,intbit,int&length){ length=0; if(str[start]==0){ expr[0]=0; return0; } elseif(str[start]=='*'||str[start]=='/'||str[start]=='('||str[start]==')'||str[start]=='@'){ expr[0]=str[start]; expr[1]=0; length=1; return2; } elseif(bit||isdigit(str[start])||str[start]=='.'){//readadigitstring intb=0; intk=0;//indexforexpr while(str[start]=='+'||str[start]=='-'){//readsign if(str[start]=='-')b++; start++; length++; } if(b%2)expr[k++]='-'; while(isdigit(str[start])||str[start]=='.'){ expr[k++]=str[start++]; length++; } expr[k]=0; return1; } elseif(str[start]=='+'||str[start]=='-'){//readaoper'+'or'-' intb=0; while(str[start]=='+'||str[start]=='-'){ if(str[start]=='-')b++; start++; length++; } if(b%2)expr[0]='-'; elseexpr[0]='+'; expr[1]=0; return2; } elsereturn-1;//error}TNode*Translate(conststring&str)//translateaexpressionstringtoaexpressiontree{ charsubstr[MAXSIZE]; Stack<char>cstk; Stack<TNode*>tstk; char*tempstr=newchar[str.length()+2]; intstart=0,bit=1; intt,length; strcpy(tempstr,str.c_str()); tempstr[str.length()]='@'; tempstr[str.length()+1]=0; cstk.push('@'); t=ReadExpr(tempstr,substr,start,bit,length); while(cstk.top()!='@'||substr[0]!='@'){ if(t==1){//isadigitstring TNode*np=newTNode(substr,1); tstk.push(np); bit=0; } elseif(t==2){//isaoper if(substr[0]=='(')bit=1; elsebit=0; chartch=cstk.top(); if(Match(tch,substr[0])=='>'){ TNode*right=tstk.top(); tstk.pop(); TNode*left=tstk.top(); tstk.pop(); TNode*np=newTNode(tch,left,right); left->parent=np; right->parent=np; tstk.push(np); cstk.pop(); continue; } elseif(Match(tch,substr[0])=='<')cstk.push(substr[0]); elsecstk.pop(); } start+=length; t=ReadExpr(tempstr,substr,start,bit,length); } delete[]tempstr;returntstk.top();}voidprint(TNode*root){ if(root->left){ print(root->left); print(root->right); cout<<root->id; } elsecout<<root->id;}voidprints(TNode*);doublesolve(TNode*);voidprintExpr(stringstr){ TNode*root=Translate(str); cout<<"后綴式:"; print(root); cout<<endl;cout<<"中綴式:"; prints(root); cout<<"="<<solve(root)<<endl;}voidprints(TNode*root)//將逆波蘭式用中綴形式打印出來(lái){ if(root->left==NULL)cout<<root->id;//isaleaf elseif(root->parent==NULL){ prints(root->left); cout<<root->id; prints(root->right); } elseif(root->parent->left==root&&Match(root->id[0],root->parent->id[0])=='>'){ prints(root->left); cout<<root->id; prints(root->right); } elseif(root->parent->right==root){ if(Match(root->parent->id[0],root->id[0])=='<'||root->parent->id[0]=='+'){ prints(root->left); cout<<root->id; prints(root->right); } else{ cout<<"("; prints(root->left); cout<<root->id; prints(root->right); cout<<")"; } } else{ cout<<"("; prints(root->left); cout<<root->id; prints(root->right); cout<<")"; }}doublesolve(TNode*root){ if(root->left==NULL){ istringstreamin; in.str(root->id); doublevalue; in>>value; returnvalue; } else{ switch(root->id[0]){ case'+': returnsolve(root->left)+solve(root->right); case'-': returnsolve(root->left)-solve(root->right); case'*': returnsolve(root->left)*solve(root->right); case'/': returnsolve(root->left)/solve(root->right); } }}voidCheck(char*str)//判斷為帶符號(hào)且緊跟括號(hào)的情況,酌情在前面添"0-"{ intk=0,i=0; if(str[0]=='+'||str[0]=='-'){ intb=0; while(str[k]=='+'||str[k]=='-'){ if(str[k]=='-')b++; k++; } if(str[k]!='(')return; char*np=newchar[strlen(str)+3]; if(b%2){ np[0]='0'; np[1]='-'; memcpy(np+2,str+k,strlen(str)+1-k); memcpy(str,np,strlen(np)+1); } else{ memcpy(np,str+k,strlen(str)+1-k); memcpy(str,np,strlen(np)+1); } delete[]np; }} voidmain(){ charbuf[100]; while(1){ cin>>buf;Check(buf); printExpr(buf); }}//stack類#include<iostream>#include<string>usingnamespacestd;//classstacktemplate<typenameT>classSNode{public:SNode(){next=NULL;}SNode(constT&td,SNode<T>*p=NULL){data=td;next=p;}Tdata;SNode<T>*next;};template<typenameT>classStack{public:Stack(){pdata=NULL;length=0;}~Stack();boolisEmpty();boolpop();