第四章 树习题,一、选择题,1、3个结点可构成_棵不同形态的二叉树。a 2 b 3 c 4 d 5,d,一、选择题,2、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是_的二叉树。a 任一结点无左孩子b 任一结点无右孩子 c 高度等于其结点数d 空或者只有一个结点,c,一、选择题,3、深度为6（根的层次为1）的二叉树至多有_结点。a 32 b 31 c 64 d 63,d,一、选择题,4、在有n个结点的二叉链表中，值为非空的链域的个数是_。a n-1 b 2n-1 c n+1 d 2n+1,c,一、选择题,5、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为_。a 98 b 99 c 50 d 48,a,一、选择题,6、在有n个叶子结点的哈夫曼树中，其结点总数为_。a 不确定 b 2n c 2n1 d 2n1,d,二、判断题,1、哈夫曼树的带权路径长度等于其中所有分支结点中的权值之和。（ ） 2、一棵树中的叶子结点数和其对应的二叉树中的叶子数一定相同。（ ）,二、判断题,3、先序序列中最后一个结点是叶子结点。（ ） 4、完全二叉树度为1的结点可能超过1个。（ ）,三、填空题,1、3个结点可构成_棵不同形态的树。 2、树有三种常用的存储结构。即_ ，孩子链表法和孩子兄弟链表法。,双亲表示法,2,三、填空题,3、有105个结点的完全二叉树有_ 个叶子结点。 4、具有100个结点的完全二叉树的深度为_。,7,53,三、填空题,5、在有n个叶子结点的哈夫曼树中，其总结点数是_。 6、以1,2,4,5,6,8,9作为叶子结点的权值所构造的哈夫曼树的带权路径长度是_。,2n-1,91,解,wpl=3+7+15+11+20+35=91,四、应用题,1、已知一棵二叉树的先序和中序序列如下，试画出该二叉树。 先序：ABCDEFG 中序：CDBEAFG,解,五、算法设计题,1、设二叉树采用二叉链表表示，设计算法求在先序序列中处于第K个位置的结点。 2、设二叉树采用二叉链表表示，设计算法求求此二叉树中的结点的个数。,解,五、算法设计题,1、设二叉树采用二叉链表表示，设计算法求在先序序列中处于第K个位置的结点值。,解,bnode *Knode(bnode *t,int k) bnode *temp=null;int num=0;preorder(t);return(temp); ,void preorder(bnode *t) if(t!=null) num+;if(num=k) temp=t;return;preorder(t-lchild);preorder(t-rchlid); ,五、算法设计题,2、设二叉树采用二叉链表表示，设计算法求求此二叉树中的结点的个数。,解,int nodenum(bnode *t) int num=0;preorder(t);return(num); ,void preorder(bnode *t) if(t!=null) num+;preorder(t-lchild);preorder(t-rchlid); ,课后思考题,如何求采用二叉链表表示的二叉树的叶子结点的个数？,第4章习题结束,二、判断题,1、哈夫曼树的带权路径长度等于其中所有分支结点中的权值之和。（ ） 2、一棵树中的叶子结点数和其对应的二叉树中的叶子数一定相同。（ ）,