二叉树习题answer

v1.0 可编辑可修改 一、下面是有关二叉树的叙述，请判断正误（）一、下面是有关二叉树的叙述，请判断正误（） （ ）. 若二叉树用二叉链表作存贮结构，则在若二叉树用二叉链表作存贮结构，则在 n n 个结点的二叉树链表中只有个结点的二叉树链表中只有 n n——1 1 个非空指针域。个非空指针域。 （ ）.二叉树中每个结点的两棵子树的高度差等于二叉树中每个结点的两棵子树的高度差等于 1 1。。 （ ）.二叉树中每个结点的两棵子树是有序的。二叉树中每个结点的两棵子树是有序的。 （ ）.二叉树中每个结点有两棵非空子树或有两棵空子树。二叉树中每个结点有两棵非空子树或有两棵空子树。 （ ）二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右 非空子树（若存在的话）所有结点的关键字值。非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点） （ ）.二叉树中所有结点个数是二叉树中所有结点个数是 2 2 -1-1，其中，其中 k k 是树的深度。是树的深度。 （应 2 2 -1-1） （ ）.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ ）.对于一棵非空二叉树，它的根结点作为第一层，则它的第对于一棵非空二叉树，它的根结点作为第一层，则它的第 i i 层上最多能有层上最多能有 2 2 ——1 1 个结点。个结点。 （应 2 2 ） （ ）用二叉链表法（用二叉链表法（link-rlinklink-rlink）存储包含）存储包含 n n 个结点的二叉树，结点的个结点的二叉树，结点的2n2n 个指针区域中有个指针区域中有 n+1n+1 个为空指个为空指 针。针。 （正确。用二叉链表存储包含n 个结点的二叉树，结点共有2n 个链域。由于二叉树中，除根结点外，每一 个结点有且仅有一个双亲， 所以只有 n-1 个结点的链域存放指向非空子女结点的指针， 还有 n+1 个空指针。 ） 即有后继链接的指针仅 n-1 个。 （ √√ ）10.具有 12 个结点的完全二叉树有 5 个度为 2 的结点。 最快方法：用叶子数＝[n/2]＝6，再求 n2=n0-1=5 i ii-1i-1 k-1k-1i i 二、填空（）二、填空（） 1 1．． 由３个结点所构成的二叉树有由３个结点所构成的二叉树有5 5种形态。种形态。 2.2.一棵深度为一棵深度为 6 6 的满二叉树有的满二叉树有 n n1 1+n+n2 2=0+ n=0+ n2 2= n= n0 0-1=31-1=31个分支结点和个分支结点和 2 2 =32 =32个叶子。个叶子。 注：满二叉树没有度为注：满二叉树没有度为 1 1 的结点，所以分支结点数就是二度结点数。的结点，所以分支结点数就是二度结点数。 3 3．． 一棵具有２５７个结点的完全二叉树，它的深度为一棵具有２５７个结点的完全二叉树，它的深度为9 9。。 （（ 注：用注：用 log2(n)+1=+1=9=9 6-16-1 4. 设一棵完全二叉树有 700 个结点，则共有350个个叶子结点。 答：最快方法：用叶子数＝[n/2]＝350 11 v1.0 可编辑可修改 5. 设一棵完全二叉树具有设一棵完全二叉树具有 10001000 个结点，则此完全二叉树有个结点，则此完全二叉树有 500个叶子结点，有个叶子结点，有499个度为个度为 2 2 的结的结 点，有点，有1 1个结点只有非空左子树，有个结点只有非空左子树，有0 0个结点只有非空右子树。个结点只有非空右子树。 答：最快方法：用叶子数＝ [n/2]＝500 ，n2=n0-1=499。 另外，最后一结点为2i 属于左叶子，右叶子是空 的，所以有 1 个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝非空右子树数＝0.0. 6. 一棵含有一棵含有 n n 个结点的个结点的 k k 叉树，可能达到的最大深度为叉树，可能达到的最大深度为n，最小深度为，最小深度为 2 2 。。 答：当答：当 k=1(k=1(单叉树单叉树) )时应该最深，深度＝时应该最深，深度＝n n（层）（层） ；当；当k=n-1k=n-1（（n-1n-1 叉树）时应该最浅，深度＝叉树）时应该最浅，深度＝2 2（层）（层） ，但不，但不 包括包括 n=0n=0 或或 1 1 时的特例情况。教材答案是“完全时的特例情况。教材答案是“完全 k k 叉树”叉树” ，未定量。，未定量。) ) 7.7.二叉树的基本组成部分是：根（二叉树的基本组成部分是：根（N N）） 、左子树（、左子树（L L）和右子树（）和右子树（R R）） 。因而二叉树的遍历次序有六种。最。因而二叉树的遍历次序有六种。最 常用的是三种：前序法（即按常用的是三种：前序法（即按 N L RN L R 次序）次序） ，后序法（即按，后序法（即按L R NL R N次序）和中序法（也称对称序次序）和中序法（也称对称序 法，即按法，即按 L N RL N R 次序）次序） 。这三种方法相互之间有关联。若已知一棵二叉。这三种方法相互之间有关联。若已知一棵二叉 树的前序序列是树的前序序列是 BEFCGDHBEFCGDH，中序序列是，中序序列是 FEBGCHDFEBGCHD，则它的后序序列必是，则它的后序序列必是 F E G H D C BF E G H D C B。。 解：法解：法 1 1：先由已知条件画图，再后序遍历得到结果；：先由已知条件画图，再后序遍历得到结果； 法法 2 2：：不画图也能快速得出后序序列， 只要找到根的位置特征。由前 序先确定 root，由中序先确定左子树。例如，前序遍历BEFCGDHBEFCGDH 中，根中，根 结点在最前面，是结点在最前面，是 B B；则后序遍历中；则后序遍历中 B B 一定在最后面。一定在最后面。 法法 3 3：递归计算。如：递归计算。如 B B 在前序序列中第一，中序中在中间（可知左右子树上有哪些元素）在前序序列中第一，中序中在中间（可知左右子树上有哪些元素） ，则在后序中，则在后序中 必为最后。如法对必为最后。如法对 B B 的左右子树同样处理，则问题得解。的左右子树同样处理，则问题得解。 8.中序遍历的递归算法平均空间复杂度为 O(n)。。 答：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度k+1，包括叶子的空域也递归了一次。 9. 用 5 个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 33。 解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出 WPLWPL＝（＝（4 4＋＋5 5＋＋3 3）×）×2 2＋（＋（1 1＋＋2 2）×）×3=333=33 (15) (15) (9) (6)(9) (6)（注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）（注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一） 4 5 3 (3) 4