数据结构 第四章树习题课.ppt

* 第四章 树与二叉树 习 题 课 作业：p125 4-1 (省略) 4-3 有m个叶子的二叉树最少有多少个结点? 4-4 现有按后序遍历二叉树的结果为C，B，A，有 几种不同的二叉树可得到这一结果？ 4-10 设计一个算法，将一个用二叉链表存储的二叉树的每个结点的左、右子女位置交换。 void Change (BinTreeNode *t) { if (!t) return 0; if(t-leftChild||t-rightChild) { p= t-leftChild; t-leftChild= t-rightChild; t-rightChild=p; } } 4-14．将图4.25中的树转换成二叉树。然后对树和转换成的二叉树分别进行适当的遍历，并加以对比。 一、填空题 （1）对于一棵具有n个结点的树,该树中所有结点度数之和为 。 （2） k叉树上的i层最大有 个结点。 （3） 高度为h的k叉树最多有 个结点。 n个结点的k叉树的最小高度为　　　　　　　　。　　　　　　 　　　假定一棵三叉树的结点个数为50，则它的最小高度为 最大高度为 。 　　　一棵高度为5的满二叉树中的结点数为 。 一棵高度为3的满四叉树中的结点数为 。 　　　 n-1 50 ki-1 (43-1)/3 25-1 （4）在一棵二叉树中，若度为2的结点数有5个，度为1 的结点数有6个，那么度为0的结点数有 个？ （5）在一棵三叉树中，若度为3的结点数有2个，度为2的结点数有1个，度为1 的结点数有2个，那么度为0的结点数有 个？ 一、填空题 6 n=n0+n1+n2=n0+5+6=e+1=2*5+1*6+1 = n0=6 6 (5) n=n0+n1+n2+n3=n0+2+1+2=e+1=3*2+2*1+1*2+1 = n0=6 （6）若对一棵二叉树从0开始进行结点编号， 并按此编号把它顺序 存储到一维数组a中，则a[i]元素的左子女结点编号为 ， 右子女结点编号为 ，双亲结点编号为 。 （7）对于一棵具有n个结点的二叉树的二叉链表中，指针总数为 为 ，其中 个指针指向子女结点， 指针空闲。 2i+1 2i+2 2n n-1 n+1 （8）在Huffman树中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可最大对 个字符编码。 （9）设高度为h（h≥1）的二叉树中，若设二叉树只有度为0和度为2的结点，则二叉树中所含结点个数至少 个。 （10）设森林F中有4棵树，第1，2，3，4棵树的结点个数分别为n1,n2,n3,n4，当把该森林F转换成一棵二叉树后，其根结点的左子树有 个结点，右子树有 个结点。 2h-1 4 n1 n2+n3+n4 二、判断题 (11) 二叉树是树的特殊情形。 (12) 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。 (13) 若有一个叶结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。 (14) 若有一个叶结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。 × × × × 二、对二叉树递归算法的理解 void Preorder(BinTree *r) { // 前序遍历的递归算法 if(r) { coutr-data; ② Preorder(r-leftChild); ① Preorder(r-rightChild); } } void Preorder(BinTree *r) { // 消去前序遍历第二个递归调用 while(r) { c