习题精练第4和二叉树

无序的数据【参考答案】 对一棵具有n[B]n-【参考答案】【参考答案】任何一棵二叉树，叶子结点数为度为2的结点数减二叉树不适合用顺序结构【参考答案】【答案解析】本题主要考查二叉树的性质以及完全二叉树的定义。其中选项A正确；选项B中叶子结点数应为度为2的结点数加1；选项C二叉树可以用顺序结构；选项D成立的前n2个度为2n1个度为1n0个度为0的结点，则该二叉【参考答案】【参考答案】的个数无关）n0n0＝1＋7+2×6+3×5+4×4+5×3+6×2=78（ni表示度为i的结点数目）【归纳总结】一棵度为m的树中有N0个叶子结点数，N1个度为1的结点，N2个度为2的结点，……Nm个度为m的结点，则有：N0=1+N2+2N3+……+(m-1)Nm。有n（n＞0）【参考答案】 【参考答案】其中，有n－1个指针域存放指向孩子结点的地址，剩余的n＋1个指针域为空。中序遍历序【参考答案】【参考答案】历与后序遍历的次序正好相反。本题的选项A、B、C都符合要求但都不完整。【参考答案】【参考答案】不会发生改【参考答案】（LDR（LRD叶子结点而言，被的先后次序都是先左后右，因此，叶子结点在先序遍历、中序遍历与 【参考答案】 二叉树的先序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为【参考答案】【参考答案】题目给出的先序序列为ABDCE，可知A为根结点，选项A给出中序序列BD是左子树部分，EC是右子树部分，和先序序列不，是可能的中序序列。选项B给出的序列表示BC是左子树，DE是右子树，这两个部分在先序序列ABDCE中不连续，说明不是可能的中序序列。同理，选项C和选项D也不是可能的中序序列。【参考答案】右孩双【参考答案】【参考答案】一个结点，则该结点X又有右孩子，则指定结点的先序后继就是该结点X的右孩子最后一个结点，但该结点X没有右孩子，则指定结点没有先序后继【参考答案】【答案解析】选项D中，因为根结点必然为第一个 n个非终端结点，则二叉树中无右孩子的结点【参考答案】树后右孩子为空，所以森林中有n个非终端结点，则二叉树中无右孩子的结点有n+1。XT中的一个非根结点，BT所对应的二叉树B中，X是其双亲的右孩子，T中，X一定有右边兄弟[C]T中，X一定是叶子结点[D]T中，X一定有左边兄弟【参考答案】的右边兄弟。故X一定有左边兄弟。【参考答案】即为转化得到的森林中的每棵树的根结点。所以，在满二叉树中，设它的高度为h，对应由h【参考答案】D都不正确。先中后【参考答案】【参考答案】至少应该包含必要条件，A、D可以排除。2C。所以本题答案为B。（2035……【参考答案】AA的左【参考答案】堆树【参考答案】下面关于树的说法，不正确的树中没有度为1【参考答案】；定满足这些性质；而对于平衡二叉树来说，完全二叉树是满足它的要求的，所以答案为。【参考答案】 树是没有度数为1的分支结点。n个叶子结点的 并，产生n-1个新结点，最后求得的 [A]{0，10，110，1111}[B]{11，10，001，101，0001}[C]{00，010，0110，1000}【参考答案】一个字符的编码的前缀。在B中10编码是101编码的前缀，因此不满足前缀编码的要求。 【参考答案】【答案解析】本题主要考查树和编码的概念和性质。按左分支编码为0，右分支编码为1，A、B、C、DD中包含度为1D不可能是编码。简答题(共12题，共0.0分n个结点并且其高度为n的二叉树的数目是多少因此有nn的二叉树的数目是2n-1【解答】本题 NP的左子树中，MP的右子树中，当然，称N在M下表中﹑N分别是一棵二叉树中的两个结点，表中行号1，2，3，4分别表示四种﹑N的相对关系，列号1，2，分别表示在先序、中序、后序遍历中N之间的遍历序列中的先后次序关系。要求在，j所表示的关系能够发生的方格内打上对号。例如：如果你认为N是M的祖先，并且在中序遍历中n能比m先被，则在（，）格内打上对号。算法【解答】用C语言算法描述如下 intflag=0;if(p==NULL)return1;InitQueue(Q);//初始化队列while(!QueueEmpty(Q))p=DeQueueQifp->lchild&&!flagEnQueueQ,p->lchild左孩子入队elseif(p->lchild)return0;elseifp->rchild&&!flagEnQueue(Q,p->rchild右孩子入队elseif(p->rchild)return0;else}return}二叉树采用二叉链 编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值设根结点为第1hh+1层，则可以通过遍历计递推。设根结点为第1hh+1层，则可以通过bt的高度，则递归定义如下:用C语言算法描述如下：{intif(bt==NULL)return0;else{elsereturn(hr+1);}}用C语言算法描述如下：if(bt==NULL)return0;//空二叉树宽度为0else{front=1;rear=1;//front指向队头元素,rear指向队尾元素Q[rear]=bt;//根结点入队列last=1;//last同层最右结点在队列中的位while{p=Q[front++];ifp->lchild!=NULLQ[++rear]=p->lchild左孩子入队ifp->rchild!=NULL)Q[++rear]=p->rchild右孩子入队if(front>last){//一层结束,}}return}}设一棵完全二叉树使用顺序在数 bt[1..n]中,请写出进行非递归的先序遍历算法 结点下标大于n（完全二叉树）或0（对一般二叉树的“虚结点”。本题是完全二叉树。参 ”【解答】用C语言算法描述如下voidPreOrder(ElemTypebt,intn){//对以顺序结构 inttop=0,s[];/top是栈swhile{(i<=n){printf(bt[i访i=2*i;//沿左孩子向下}}} 结构，结点结构为(lchild,data,rchild)，设计一个递归将二叉树【解答】用C语言算法描述如下if(bt){BiTrees；bt->lchild=bt-}} 已知一棵二叉树的中序序列和后序序列，写一个建立该二叉树的二叉链 结构的算【解答】用C语言算法描述如下//in和post是二叉树的中序和后序序列,l1,h1,l2,h2分别是两序列第一和最后结点的BiTreebt=(BiTree)malloc(sizeof(BiNode));//申请结for(i=l1;i<=h1;i++)if(i==l1)bt->lchild=NULL;//处理左子树if(i==h1)bt->rchild=NULL;//处理右子树}已知深度为h的二叉树以一维数组BT(1:2h-1)作为其结构。请写一算法，求该二叉树中叶结点的【解答】用C语言算法描述如下 intBT[intlen=2h-1count=0BT是二叉树结点值一维数组，容量为2hfor(i=1;i<=len;i++)//数组元素从下标1开始存放if(i*2)>len)count++;//第i个结点 ，肯定是叶elseif(BT[2*i]==0&&2*i+1<=len&&BT[2*i+1]==0) return} 【解答】用C语言算法描述如下CreatLeafList（bt- //中序遍历左if(bt->lchild==NULL&&bt->rchild==NULL)叶子结点if(head==NULL){//第一个叶子结点head=(BiTree)malloc(sizeof(BiNode));//生成头结点head->lchild=NULL;//头结点的左链为空bt->lchild=head;//第一个叶子结点左链指向头结点pre=bt;//pre指向当前叶子结点}}CreatLeafList(bt- //中序遍历右子pre- //最后一个叶子结点的右链置空（链表结束标记}}假设非空二叉树bt采用二叉链表 【解答】用C语言算法描述如下voidMax(BiTree{intif(bt==NULL)returnif(bt->lchild==NULL&&bt->rchild==NULL)returnbt->data;elsen=Max(bt->rchild);if(m>bt->data)returnm;elsereturnbt->data;}}中序序列设计一个算法，判断给定的一棵二叉树是否为二叉排序树，假设二叉排序树中所有关