1、第 6 章 树和二叉树1 选 择 题（ 1） 把 一 棵 树 转 换 为 二 叉 树 后 ， 这 棵 二 叉 树 的 形 态 是 （ ） 。 A唯 一 的 有 多 种C有多种，但根结点都没有左孩子 有多种，但根结点都没有右孩子（ 2） 由 3 个结点可以构造出多少种不同的二叉树？（ ）A2 B3 C4 D5 （ 3） 一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（ ） 。A250 B 500 C254 D501 （ 4） 一个具有 1025 个结点的二叉树的高 h 为（ ） 。A11 B10 C11 至 1025 之间 D10 至 1024 之间（ 5） 深度为 h 的满 m 叉
2、树的第 k 层有（ ）个结点。(1=lchild=NULL /判断该结点是否是叶子结点（左孩子右孩子都为空） ，若是则返回 1elsereturn LeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);（ 2） 判别两棵树是否相等。（ 3） 交换二叉树每个结点的左孩子和右孩子。void ChangeLR(BiTree if(T-lchild=NULLelsetemp = T-lchild;T-lchild = T-rchild;T-rchild = temp;weight parent lchild rchild1 3 8 0 02 12 12 0 0
3、3 7 10 0 04 4 9 0 05 2 8 0 06 8 10 0 07 11 11 0 08 5 9 5 19 9 11 4 810 15 12 3 611 20 13 9 712 27 13 2 1013 47 0 11 12ChangeLR(T-lchild);ChangeLR(T-rchild);（ 4） 设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树） 。void DoubleTraverse(BiTree T)if(T = NULL)return;else if(T-
4、lchild=NULLelsecoutdata;DoubleTraverse(T-lchild);coutdata;DoubleTraverse(T-rchild);（ 5） 计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值） 。题目分析 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。int Width(BiTree bt)/求二叉树 bt 的最大宽度if (bt=null) return (0); /空二叉树宽度为 0else BiTree Q;/Q 是队列，元素为二叉树结点指针，容量
5、足够大front=1;rear=1;last=1;/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;/i
6、f /whilereturn (maxw);/结束 width（ 6） 用按层次顺序遍历二叉树的方法，统计树中具有度为 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); printf(p-data); /出队,访问结点if(p-lchild /度为 1 的结点if(p-lchild) QueueIn(Q,p-lc
7、hild); /非空左子女入队if(p-rchild) QueueIn(Q,p-rchild); /非空右子女入队 /if(bt) return(num); /返回度为 1 的结点的个数 （ 7） 求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。题目分析因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。void LongestPath(BiTree bt)/求二叉树中的第一条最长路径长度BiTree p=bt,l
8、,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 i0) tagtop=1; p=stop.Rc; /沿右子分枝向下/while(p!=null|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 for (i=pathlen-1;i=0;i-)cout data; /将当前结点放入路径中pathlen+; /路径长度增 1AllPath(b-lchild,path,pathlen); /递归扫描左子树AllPath(b-rchild,path,pathlen); /递归扫描右子树pathlen-; /恢复环境
