数据结构课件第六章习题_补充答案.doc

《数据结构课件第六章习题_补充答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5．该算术表达式转化的二叉树如右图所示。10．2n-1(本题等价于高度为n的满二叉树有多少叶子结点，从根结点到各叶子结点的单枝树是不同的二叉树。)11．235。由于本题求二叉树的结点数最多是多少，第7层共有27-1=64个结点，已知有10个叶子，其余54个结点均为分支结点。它在第八层上有108个叶子结点。所以该二叉树的结点数最多可达(27-1+108)=235。(注意；本题并未明说完全二叉树的高度，但根据题意，只能8层。)17．设分枝结点和叶子结点数分别是为nk和n0，因此有n=n0+nk(1)另外从树的分枝数B与结点的关系有n=B+1=K*nk+1(2

2、)由（1）和（2）有n0=n-nk=(n(K-1)+1)/K18．用顺序存储结构存储n个结点的完全二叉树。编号为i的结点，其双亲编号是ëi/2û(i=1时无双亲)，其左子女是2i(若2i<=n,否则i无左子女)，右子女是2i+1(若2i+1<=n,否则无右子女)。30．结点数的最大值2h-1（满二叉树），最小值2h-1（第一层根结点，其余每层均两个结点）。A54．(54)题图ABCDEBDCE56题图ABCEDGIHFJK56.5．[题目分析]由指示结点i左儿子和右儿子的两个一维数组L[i]和R[i]，很容易建立指示结点i的双亲的一维数组T[i]，根据T

3、数组，判断结点U是否是结点V后代的算法，转为判断结点V是否是结点U的祖先的问题。intGeneration(intU,V,N,L[],R[],T[])//L[]和R[]是含有N个元素且指示二叉树结点i左儿子和右儿子的一维数组，//本算法据此建立结点i的双亲数组T，并判断结点U是否是结点V的后代。{for(i=1;i<=N;i++)T[i]=0;//T数组初始化for(i=1;i<=N;i++)//根据L和R填写Tif(L[i]!=0)T[L[i]]=i;//若结点i的左子女是L，则结点L的双亲是结点ifor(i=1;i<=N;i++)if(R[i]!=0

4、)T[R[i]]=i;//i的右子女是r，则r的双亲是iintparent=U;//判断U是否是V的后代while(parent!=V&&parent!=0)parent=T[parent];if(parent==V){printf(“结点U是结点V的后代”);return(1);}else{printf(“结点U不是结点V的后代”);return(0);}}6．[题目分析]判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。intJudgeComplete(BiTreebt)//判断二叉树是否是完

5、全二叉树,如是，返回1，否则，返回0{inttag=0;BiTreep=bt,Q[];//Q是队列，元素是二叉树结点指针，容量足够大if(p==null)return(1);QueueInit(Q);QueueIn(Q,p);//初始化队列，根结点指针入队while(!QueueEmpty(Q)){p=QueueOut(Q);//出队if(p->lchild&&!tag)QueueIn(Q,p->lchild);//左子女入队elseif(p->lchild)return0;//前边已有结点为空，本结点不空elsetag=1;//首次出现结点为空if(p

6、->rchild&&!tag)QueueIn(Q,p->rchild);//右子女入队elseif(p->rchild)return0;elsetag=1;}return1;}//JudgeComplete[算法讨论]完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。