《数据结构__第四章树习题课》由会员分享，可在线阅读，更多相关《数据结构__第四章树习题课（17页珍藏版）》请在金锄头文库上搜索。
1、第四章 树与二叉树 习 题 课1作业：p1254-1 (省略)4-3 有m个叶子的二叉树最少有多少个结点?4-4 现有按后序遍历二叉树的结果为C，B，A，有 几种不同的二叉树可得到这一结果？24-10 设计一个算法，将一个用二叉链表存储的二叉 树的每个结点的左、右子女位置交换。void Change (BinTreeNode *t) if (!t) return 0;if(t-leftChild|t-rightChild) p= t-leftChild;t-leftChild= t-rightChild;t-rightChild=p;34-14将图4.25中的树转换成二叉树。然后对树和转换成的
2、二叉树分别进行适当的遍历，并加以对比。4一、填空题（1）对于一棵具有n个结点的树,该树中所有结点度数之和为 。（2） k叉树上的i层最大有 个结点。（3） 高度为h的k叉树最多有 个结点。n个结点的k叉树的最小高度为 。 假定一棵三叉树的结点个数为50，则它的最小高度为最大高度为 。一棵高度为5的满二叉树中的结点数为 。 一棵高度为3的满四叉树中的结点数为 。 n-150ki-1(43-1)/325-15（4）在一棵二叉树中，若度为2的结点数有5个，度为1 的结点数有6个，那么度为0的结点数有 个？（5）在一棵三叉树中，若度为3的结点数有2个，度为2的结点数有1个，度为1 的结点数有2个，那么
3、度为0的结点数有 个？一、填空题6(4) n=n0+n1+n2=n0+5+6=e+1=2*5+1*6+1 = n0=66(5) n=n0+n1+n2+n3=n0+2+1+2=e+1=3*2+2*1+1*2+1 = n0=66（6）若对一棵二叉树从0开始进行结点编号， 并按此编号把它顺序存储到一维数组a中，则ai元素的左子女结点编号为 ，右子女结点编号为 ，双亲结点编号为 。（7）对于一棵具有n个结点的二叉树的二叉链表中，指针总数为为 ，其中 个指针指向子女结点， 指针空闲。2i+12i+22n2nn-1n-1n+1n+17（8）在Huffman树中，若编码长度只允许小于等于4，则除了已对两个字
4、符编码为0和10外，还可最大对 个字符编码。（9）设高度为h（h1）的二叉树中，若设二叉树只有度为0和度为2的结点，则二叉树中所含结点个数至少 个。（10）设森林F中有4棵树，第1，2，3，4棵树的结点个数分别为n1,n2,n3,n4，当把该森林F转换成一棵二叉树后，其根结点的左子树有 个结点，右子树有 个结点。2h-14 4n1n1n2+n3+n4n2+n3+n48二、判断题(11) 二叉树是树的特殊情形。 (12) 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍 历结果序列的最后一个结点。 (13) 若有一个叶结点是二叉树中某个子树的中序遍历结果序
5、列的最后一个结点，则它一定是该子树的前序 遍历结果序列的最后一个结点。 (14) 若有一个叶结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序 遍历结果序列的最后一个结点。9二、对二叉树递归算法的理解void Preorder(BinTree *r) / 前序遍历的递归算法 if(r) coutdata; Preorder(r-leftChild); Preorder(r-rightChild);void Preorder(BinTree *r) / 消去前序遍历第二个递归调用 while(r) coutdata;Preorder(r-leftChild);r=r-
6、rightChild;ABCDE10非递归的前序遍历算法：void PreOrderTraverse(BinaryTreeNode *r)Stack s; s.InitStack()；p=r; while(p | !s.IsEmpty()while(p) cout data; s.Push(p); p=p-leftChild; if(!s.IsEmpty() p=s.Pop()；p=p-rightChild；/if/while/ lnOrderTraverse 112、如一棵树有n1个度为1的结点，有n2个度为2的结点，, nm个度为m的结点，试问有多少个度为0的结点？解：n=n0+n1+n2
7、+nm n-1=n1+2*n2+mnm化简：n=1+n2+2n3+(m-1)nm =1+1、3个结点的树和二叉树个共有多少不同形态？树有2种，二叉树有5种。12(1) 空二叉树或左子树为空的二叉树。(2) 空二叉树或右子树为空的二叉树。(3) 空二叉树或只有根结点的二叉树。3、试分别找出满足下列条件的所有二叉树： （1）二叉树的前序遍历与中序遍历相同； （2）二叉树的中序遍历与后序遍历相同； （3）二叉树的前序遍历与后序遍历相同；13四、设二叉树以二叉链表表示，试编写有关二叉树的递归算法。1. 统计二叉树中叶结点的个数。int Degrees0(BinTreeNode *t) if (!t)
8、return 0;if(!t-leftChild return Degrees0(t-leftChild)+Degrees0(t-rightChild); 或void Degrees0(BinTreeNode *t，Degrees0(t-leftChild, count);Degrees0(t-rightChild, count); 14四、设二叉树以二叉链表表示，试编写有关二叉树的递归算法。 2. 统计二叉树中度为1的结点个数。 int Degrees1(BinTreeNode *t) if (!t) return 0;if(t-leftChildreturn Degrees1(t-left
9、Child)+Degrees1(t-rightChild);或 int Degrees1(BinTreeNode *t) if (!t) return 0;if(t-leftChild15int Degrees2(BinTreeNode *t) if (!t) return 0;if(t-leftChild 3. 统计二叉树中度为2的结点个数。16int high(BinaryTreeNode *t) if (!t) return 0;lh=high(t-leftChild);rh=high(t-rightChild);return 1+(lhrh?lh:rh);4. 统计二叉树的高度int Depth (BinaryTreeNode *t ) if (!t ) return 0; else return 1+Max ( Depth ( tleftChild ), Depth ( trightChild ) ); 17
