《数据结构二叉树习题含答案.doc》由会员分享，可在线阅读，更多相关《数据结构二叉树习题含答案.doc（7页珍藏版）》请在金锄头文库上搜索。
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叉树的第k层有（ ）个结点。(1=k=lchild=NULL&T-rchild=NULL)return 1; /判断该结点
2、是否是叶子结点（左孩子右孩子都为空），若是则返回1elsereturn LeafNodeCount(T-lchild)+LeafNodeCount(T-rchild);（2）判别两棵树是否相等。（3）交换二叉树每个结点的左孩子和右孩子。void ChangeLR(BiTree &T)BiTree temp;if(T-lchild=NULL&T-rchild=NULL)return;elsetemp = T-lchild;T-lchild = T-rchild;T-rchild = temp;ChangeLR(T-lchild);ChangeLR(T-rchild);（4）设计二叉树的双序遍历算
3、法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。void DoubleTraverse(BiTree T)if(T = NULL)return;else if(T-lchild=NULL&T-rchild=NULL)coutdata;elsecoutdata;DoubleTraverse(T-lchild);coutdata;DoubleTraverse(T-rchild);（5）计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。题目分析 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。int Width(BiTree bt)/求二叉树bt的最大宽度if (bt=null) return (0); /空二叉树宽度为0else BiTree Q;/Q是队列，元素为二叉树结点指针，容量足够大 front=1;rear=1;last=1;/front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0; maxw=0; /temp记局部宽度, maxw记最大宽度 Qrear=bt; /根结点入队列 while(front=last) p=Qfron
