《数据结构 Java语言版 教学课件 ppt 王学军习题答案 第7章 树与二叉树》由会员分享，可在线阅读，更多相关《数据结构 Java语言版 教学课件 ppt 王学军习题答案 第7章 树与二叉树（4页珍藏版）》请在金锄头文库上搜索。
1、第七章习题参考答案一、简答题1【参考答案】 ：无序树：如果树中任意结点的各孩子结点的排列没有严格次序，可交换位置，则称该树为无序树。有序树：如果树中任意结点的各孩子结点的排列有严格的次序，不可交换位置，则称该树为有序树。2 【参考答案】 ：满二叉树：若深度为h的二叉树，恰好具有-1个结点，则称为满二叉树。完全二叉树：若一棵具有n个结点的二叉树的逻辑结构与满二叉树的前n个结点的逻辑结构完全相同，则称该二叉树为完全二叉树。3【参考答案】 ： 最多-1个结点，最少-1个结点。4【参考答案】 ：存储二叉树时，同时存储结点在遍历序列中的前驱和后继信息，使在对二叉树进行各种操作时就会更加地方便。5【参考答
2、案】 ： 如下图：ABFCGDEH6【参考答案】 ：如右图ABHECIKFGDJLNMO此二叉树有6层7【参考答案】 ：（1） 如右图7923512161052238带权路径：7*2+9*2+12*2+5*3+2*4+3*4=91哈夫曼编码：A：1000 B：1001 C：101 D：00 E：01 F：11二、实验题1【参考答案】 ：public void SearchTree(TreeNode root)java.util.Queue q = new java.util.LinkedList();if(root = null)return;TreeNode tn;q.add(root);w
3、hile(!q.isEmpty()tn = q.remove();System.out.print(tn.getData();if(tn.getLeft()!=null)q.add(tn.getLeft();if(tn.getRight()!=null)q.add(tn.getRight();2【参考答案】 ：public int ObtainDeep(TreeNode root)if(root = null)return 0;int ileft=1,iright=1,ideep=1;TreeNode tn = root;if(tn != null)ileft += ObtainDeep(tn
4、.getLeft();iright += ObtainDeep(tn.getRight();if(ileft=iright)ideep = ileft;elseideep = iright;return ideep;3 【参考答案】 ：public boolean isFullTree(TreeNode root)if(root = null)return false;TreeNode tn = root;if(tn != null)if(tn.getLeft() = null)if(tn.getRight() != null)return false;return true;elseif(t
5、his.hasChildNode(tn)if(tn.getRight() = null)return false;return isFullTree(tn.getLeft();return false;4【参考答案】 ：public boolean equals(TreeNode r1, TreeNode r2)if(r1=r2)return true;if(r1=null&r2=null)return true;if(r1=null | r2=null)return false;boolean rflag, lflag;if(r1.equals(r2)lflag = equals(r1.getLeft(), r2.getLeft();rflag = equals(r1.getRight(), r2.getRight();elsereturn false;return lflag & rflag;5【参考答案】 ： 该程序的功能为求二叉树中结点个数。6【参考答案】 ：该程序的功能将二叉树中左、右全部结点进行交换。7【参考答案】 ：参考P147。三、思考题1【参考答案】 ：（1）能（2）能（3）能2【参考答案】 ：根据二叉排序树的概念可知，当遇到相同元素时，后面插入的元素进入到前面元素的右子树中，但是具体位置要看目前二叉排序树该结点的右子树状态而定。107
