工大数据结构第三章作业

数据结构与算法上机作业第三章树

一、选择题1、在一棵树中，如果结点A有3个兄弟，B是A的双亲，则B的度为D A.1 B.2 C.3 D.42、深度为h的完全二叉树至少有D个结点，至多有B个结点 A.2h B.2h-1 C.2h+1 D.2h-12^(h-1)-1+1=2^(h-1)

前（n-1）层满，第h层只有一结点3、具有n个结点的满二叉树有C个叶结点。 A.n/2 B.(n-1)/2 C.(n+1)/2 D.n/2+1因为二叉树中，有这样一个性质，如果其终端结点数（也就是叶子节点）的个数为n1，度为2的结点数为n2，则n1=n2+1;

假设叶子节点有x个，则度为2的个数为x-1：

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

所以叶子节点个数为：(n+1)/2

非终端结点为：(n+1)/2-14、一棵具有25个叶结点的完全二叉树最多有B个结点。 A.48 B.49 C.50 D.515、已知二叉树的先根遍历序列是ABCDEF，中根遍历序列是CBAEDF，则后根遍历序列是A。 A.CBEFDA B.FEDCBA C.CBEDFA D.不定6、具有10个叶结点的二叉树中有B个度为2的结点。 A.8 B.9 C.10 D.117、一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足C。 A.所有非叶结点均无左孩子 B.所有非叶结点均无右孩子 C.只有一个叶子结点 D.A和B同时成立8、在线索二叉树中，t所指结点没有左子树的充要条件是B。 A.t->left=NULL B.t->ltag=TRUE C.t->ltag=TRUE且t->left=NULL D.以上都不对9、n个结点的线索二叉树上含有的线索数为C。 A.2n B.n-1 C.n+1 D.nn-1表示结点的左右子树，其余n-1指针为空线索取代原来的空链10、二叉树按照某种顺序线索化后，任一结点都有指向其前驱和后继的线索，这种说法B。 A.正确 B.错误 C.不确定 D.都有可能11、具有n(n>1)个结点的完全二叉树中，结点i(2i>n)的左孩子结点是D。 A.2i B.2i+1 C.2i-1 D.不存在12、具有64个结点的完全二叉树的深度为C。 A.5 B.6 C.7 D.813、将一颗有100个结点的完全二叉树从上到下、从左到右一次对结点进行编号，根结点的五、已知非空二叉树T，写一个算法，求度为2的结点的个数。要求： 1、定义二叉树的抽象数据类型和型BTREE，并定义基本操作。 2、编写函数count2(BTREET)，返回度为2的节点的个数。 3、在主函数中，构建一个二叉树，并验证所编写的算法。六、用递归方法写一个算法，求二叉树的叶子结点数intleafnum(BTREET)。要求：定义二叉树的抽象数据类型和型BTREE，并定义基本操作。编写函数leafnum(BTREET)，返回树T的叶子节点的个数。在主函数中，构建一个二叉树，并验证所编写的算法。画出下图所表示的二叉树的中序线索二叉树和先序线索二叉树。八、已知二叉树的先根序列是AEFBGCDHIKJ，中根序列是EFAGBCHKIJD，画出此二叉树，并画出后序线索二叉树。九、在中序线索二叉树中插入一个结点Q作为树中某个结点P的左孩子，试给出相应的算法。要求：定义中序线索二叉树的型THTREE以及基本操作。定义函数voidLInsert(THTREEP,THTREEQ);实现题目要求的操作。在主函数中，利用操作RInsert和LInsert构造一个线索二叉树，并中序输出二叉树的结点的元素，验证结果。#include<iostream>#include<iomanip>#include<cmath>#include<cstdlib>#include<string>usingnamespacestd;typedefintelementtype;structnode{//节点的型 node*lchild; node*rchild; boolltag; boolrtag; elementtypeelement;};typedefnode*head;//指向树根roottypedefnode*tree;//指向线索树的根节点voidmakeNull(head&h)//将线索二叉树置空{ h->lchild=h; h->ltag=false; h->rchild=h; h->rtag=true;}headpointTotree(head&h,tree&t)//令head指向tree,注意head指向的并不是根节点，tree指向根节点{ h->lchild=t; h->rchild=h; h->ltag=true; h->rtag=true; returnh;}//中根遍历的下一个节点node*inNext(node*p){ node*q=p->rchild; if(p->rtag==true)//如果有右子树，找出右子树的最左节点 while(q->ltag==true) q=q->lchild; returnq;}//中根遍历的上一个节点node*inPre(node*p){ node*q=p->lchild; if(p->ltag==true)//如果P的左子树存在，则其前驱结点为左子树的最右结点 while(q->rtag==true) q=q->rchild; returnq;//左子树的最右结点}//中序遍历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;//新插入的节点木有左子树，所以lchild指向的是父节点 s->rchild=r; s->rtag=true;//原节点的右孩子为新插入的节点 if(r->rtag==true){ //这里是神马意思呢∑q|?Д?|p，就是如果被插节点s有右子树， //找出被插节点s的的next位置，即右子树中的最左节点，令其lchild指向新添加的节点r //因为插入前该最左节点的lchild指向的是原来节点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){//与插入右孩子方法相似，只需把左右方向对调即可 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; //构造线索树213 lInsert(root,lc); rInsert(root,rc); thInOrder(h); cout<<endl; //root左边插入C lInsert(root,c); thInOrder(h); return0;}十、假设现在有如下的元素：7、16、49、82、5、31、6、2、44。画出将每一个元素插入堆中以后的最大堆。要求：利用基本操作Insert的基本原理，先用第一个元素7构成一个二叉树，然后将第二个元素16插入该二叉树中，再将第三个元素49插入堆中，……，直到最后一个元素插入为止。上述过程要求画图完成。十一、编写一个函数，在最大堆中查找任意元素，并分析其时间复杂度。要求：定义最大堆的型HEAP及其基本操作。定义函数intFind(HEAPH,Elementtypee)，查找e是否为堆的元素，如果是，返回该元素在堆中的位置，如果不是，返回0。（提示：利用最大堆的元素特点进行查找，可降低复杂度）在主函数中首先构建一个二叉树，然后验证所构造的函数。typedefstryct{intkey;datathpedata;}elementtype;Typedefstruct{Elementtypeelements[Maxsize];intn;}HEAP;VoidMaxHeap(HEAPheap)//创建一个空堆{heap.n=0;}BoolHeapEmpty(HEAPheap)//判断堆是否为空{If(!(heap.n))returntrue;Elsereturnfalse;}BoolHeapFull(HEAPheap)//判断堆是否为满{if(heap.n==Maxsize-1)returntrue;Elsereturnfalse;}VoidInsert(HEAP&heap,elementtypeelement)//在堆heap中插入元素为element的结点{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;}十二、给定叶子结点的权值集合{15,3,14,2,6,9,16,17}，构造相应的哈夫曼树，并计算其带权路径长度。十三、已知n=9和一组等价关系：1≡5、6≡8、7≡2、9≡8、3≡7、4≡2、9≡3 试应用抽象数据类型MFSET设计一个算法，按输入的等价关系进行等价分类。#include<iostream.h>

#define

n

9//MEFSET元素个数

//MFSET抽象数据型struct

mfnode{

int

father;//指向父节点的链

int

count;//树结点个数

};

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;

}

//

等价分类

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结束等价分类

{

k=Find(i,

S);

m=Find(j,

S);

if(k!=m)

Union(k,

m,

S);

cin>>i;

cin>>j;

}

}

void

print_MFSET(MFSET

S)//输出等价类

{

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);

}

十四、画出下图所示的森林经转换后所对应的二叉树，并指出在二叉树中某结点为叶子结点时，所对应的森林中结点应满足的条件。十五、已知森林F的先根序列为：ABCDEFGHIJKL，后根序列为：CBEFDGAJIKLH，试画出森林F。提示：先画出森林F所对应的二叉树B，然后再将B转换为森林。十六、画出表达式(A+B*C/D)*E+F*G所对应的树结构，并写出该表达式的波兰表示式和逆波兰表示式。十七、利用逆波兰表达式求一个四则混合元算的值。具体要求：定义二叉树的型BTREE和位置的型position。实现二叉树的基本操作。实现将一个四则混合运算转换成二叉树的函数：BTREEconvert(char*express)，其中参数express为四则混合运算表达式，返回值为生成的树。实现计算四则混合运算的值的函数：doublecomputer(BTREEbt)，其中，参数bt为四则运算所对应的树，返回值为计算结果。提示：先求树的的波兰表达式，然后利用栈结构计算表达式的值。在主函数中进行测试，求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)//将逆波兰式用中缀形式打印出来{ 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)//判断为带符号且紧跟括号的情况,酌情在前面添"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();