《数据结构C语言版第二版(严蔚敏)第5章树和二叉树答案.pdf》由会员分享，可在线阅读，更多相关《数据结构C语言版第二版(严蔚敏)第5章树和二叉树答案.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 第 5 章 树和二叉树 1选择题（1）把一棵树转换为二叉树后，这棵二叉树的形态是（）。A 唯一的 有多种 C 有多种，但根结点都没有左孩子 有多种，但根结点都没有右孩子 答案：A 解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。（2）由 3 个结点可以构造出多少种不同的二叉树？（）A 2 B3 C4 D 5 答案：D 解释：五种情况如下：ACB ACB ACB ACB ACB（3）一棵完全二叉树上有 1001个结点，其中叶子结点的个数是（）。A 250 B 500 C254 D501 答案：D 解释：设度为 0结点（叶子结点）个数为 A，度为 1的结点
2、个数为 B，度为 2 的结点个数为 C，有 A=C+1，A+B+C=1001，可得 2C+B=1000，由完全二叉树的性质可得 B=0或 1，又因为 C为整数，所以 B=0，C=500，A=501，即有 501个叶子结点。（4）一个具有 1025个结点的二叉树的高 h 为（）。A 11 B10 C11 至 1025之间 D10 至 1024之间 答案：C 解释：若每层仅有一个结点，则树高 h为 1025；且其最小树高为 log21025+1=11，即 h在 11 至 1025 之间。（5）深度为 h 的满 m 叉树的第 k 层有（）个结点。(1=k=lchild=NULL&T-rchild=N
3、ULL)return 1;/判断结点是否是叶子结点（左孩子右孩子都为空），若是则返回 1 e lse return LeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);（2）判别两棵树是否相等。题目分析 先判断当前节点是否相等(需要处理为空、是否都为空、是否相等)，如果当前节点不相等，直接返回两棵树不相等;如果当前节点相等，那么就递归的判断他们的左右孩子是否相等。算法描述 int compareTree(TreeNode*tree1,TreeNode*tree2)/用分治的方法做，比较当前根，然后比较左子树和右子树 bool tree1IsNull=
4、(tree1=NULL);bool tree2IsNull=(tree2=NULL);if(tree1IsNull!=tree2IsNull)return 1;if(tree1IsNull&tree2IsNull)/如果两个都是 NULL，则相等 return 0;/如果根节点不相等，直接返回不相等，否则的话，看看他们孩子相等不相等 if(tree1-c!=tree2-c)return 1;return(compareTree(tree1-left,tree2-left)&compareTree(tree1-right,tree2-right)(compareTree(tree1-left,t
5、ree2-right)&compareTree(tree1-right,tree2-left);/算法结束 （3）交换二叉树每个结点的左孩子和右孩子。题目分析 如果某结点左右子树为空，返回，否则交换该结点左右孩子，然后递归交换左右子树。算法描述 void ChangeLR(BiTree&T)BiTree temp;if(T-lchild=NULL&T-rchild=NULL)return;else temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;/交换左右孩子 ChangeLR(T-lchild);/递归交换左子树 ChangeLR(T-rchild
6、);/递归交换右子树 （4）设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。题目分析 若树为空，返回；若某结点为叶子结点，则仅输出该结点；否则先输出该结点，递归遍历其左子树，再输出该结点，递归遍历其右子树。算法描述 void DoubleTraverse(BiTree T)i f(T=NULL)return;e lse if(T-lchild=NULL&T-rchild=NULL)coutdata;/叶子结点输出 e lse coutdata;DoubleTraverse(T-lch
7、ild);/递归遍历左子树 coutdata;DoubleTraverse(T-rchild);/递归遍历右子树 （5）计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。题目分析 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。算法描述 int Width(BiTree bt)/求二叉树 bt 的最大宽度 if(bt=null)return(0);/空二叉树宽度为 0 else BiTree Q;/Q是队列，元素为二叉树结点指针，容量足够大 front=1;rear=1;last=1;/
8、front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0;maxw=0;/temp记局部宽度,maxw记最大宽度 Qrear=bt;/根结点入队列 while(frontlchild!=null)Q+rear=p-lchild;/左子女入队 if(p-rchild!=null)Q+rear=p-rchild;/右子女入队 if(frontlast)/一层结束，last=rear;if(tempmaxw)maxw=temp;/last指向下层最右元素,更新当前最大宽度 temp=0;/if /while return(maxw);/结束 width （6）用按层次顺
9、序遍历二叉树的方法，统计树中具有度为 1 的结点数目。题目分析 若某个结点左子树空右子树非空或者右子树空左子树非空，则该结点为度为 1 的结点 算法描述 int Level(BiTree bt)/层次遍历二叉树，并统计度为 1 的结点的个数 int num=0;/num统计度为 1 的结点的个数 if(bt)QueueInit(Q);QueueIn(Q,bt);/Q是以二叉树结点指针为元素的队列 while(!QueueEmpty(Q)p=QueueOut(Q);coutdata;/出队,访问结点 if(p-lchild&!p-rchild|!p-lchild&p-rchild)num+;/度
10、为 1 的结点 if(p-lchild)QueueIn(Q,p-lchild);/非空左子女入队 if(p-rchild)QueueIn(Q,p-rchild);/非空右子女入队 /while(!QueueEmpty(Q)/if(bt)return(num);/返回度为 1 的结点的个数 （7）求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。题目分析 因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。算法描述 v
11、oid LongestPath(BiTree bt)/求二叉树中的第一条最长路径长度 BiTree p=bt,l,s;/l,s是栈，元素是二叉树结点指针，l 中保留当前最长路径中的结点 int i，top=0,tag,longest=0;while(p|top0)while(p)s+top=p；tagtop=0;p=p-Lc;/沿左分枝向下 if(tagtop=1)/当前结点的右分枝已遍历 if(!stop-Lc&!stop-Rc)/只有到叶子结点时，才查看路径长度 if(toplongest)for(i=1;i0)tagtop=1;p=stop.Rc;/沿右子分枝向下/while(p!=nu
12、ll|top0)/结束 LongestPath （8）输出二叉树中从每个叶子结点到根结点的路径。题目分析 采用先序遍历的递归方法，当找到叶子结点*b 时，由于*b 叶子结点尚未添加到path 中，因此在输出路径时还需输出 b-data 值。算法描述 void AllPath(BTNode*b,ElemType path,int pathlen)int i;if(b!=NULL)if(b-lchild=NULL&b-rchild=NULL)/*b 为叶子结点 cout data 到根结点路径:data;for(i=pathlen-1;i=0;i-)cout data;/将当前结点放入路径中 pathlen+;/路径长度增 1 AllPath(b-lchild,path,pathlen);/递归扫描左子树 AllPath(b-rchild,path,pathlen);/递归扫描右子树 pathlen-;/恢复环境 /if(b!=NULL)/算法结束