第 5 章 树和二叉树 1970-01-01 第 5 章 树和二叉树 课后习题讲解 1. 填空题 ⑴ 树是 n（n≥ 0）结点的有限集合，在一棵非空树中，有（ ）个根结点，其余的结点分成 m（m＞0）个（ ）的集合，每个集合都是根结点的子树。 【解答】有且仅有一个，互不相交 ⑵ 树中某结点的子树的个数称为该结点的（ ），子树的根结点称为该结点的（ ），该结点称为其子树根结点的（ ）。 【解答】度，孩子，双亲 ⑶ 一棵二叉树的第i（i≥ 1）层最多有（ ）个结点；一棵有 n（n>0）个结点的满二叉树共有（ ）个叶子结点和（ ）个非终端结点。 【解答】2i-1，(n+1)/2，(n-1)/2 【分析】设满二叉树中叶子结点的个数为 n0，度为 2 的结点个数为 n2，由于满二叉树中不存在度为 1 的结点，所以 n=n0+n2；由二叉树的性质 n0=n2+1，得 n0=(n+1)/2，n2=(n-1)/2。 ⑷ 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，该二叉树的结点数可能达到的最大值是（ ），最小值是（ ）。 【解答】2h -1，2h-1 【分析】最小结点个数的情况是第1 层有 1 个结点，其他层上都只有 2 个结点。 ⑸ 深度为 k 的二叉树中，所含叶子的个数最多为（ ）。 【解答】2k-1 【分析】在满二叉树中叶子结点的个数达到最多。 ⑹ 具有 100 个结点的完全二叉树的叶子结点数为（ ）。 【解答】50 【分析】100 个结点的完全二叉树中最后一个结点的编号为 100，其双亲即最后一个分支结点的编号为 50，也就是说，从编号51 开始均为叶子。 ⑺ 已知一棵度为3 的树有2 个度为1 的结点，3 个度为2 的结点，4 个度为3 的结点。则该树中有（ ）个叶子结点。 【解答】12 【分析】根据二叉树性质3 的证明过程，有n0=n2+2n3+1（n0、n2、n3 分别为叶子结点、度为2 的结点和度为3 的结点的个数）。 ⑻ 某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（ ）。 【解答】CDBGFEA 【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。 ⑼ 在具有n个结点的二叉链表中，共有（ ）个指针域，其中（ ）个指针域用于指向其左右孩子，剩下的（ ）个指针域则是空的。 【解答】2n，n-1，n+1 ⑽ 在有n个叶子的哈夫曼树中，叶子结点总数为（ ），分支结点总数为（ ）。 【解答】n，n-1 【分析】n-1 个分支结点是经过n-1 次合并后得到的。 2. 选择题 ⑴ 如果结点A 有3 ...
