数据结构习题题目及答案_树和二叉树_参考答案VIP专享VIP免费

一、基础知识题666666666666666666666666666 6.1 设树T 的度为4，其中度为1，2，3 和4 的结点个数分别为4，2，1，1，求树T 中的叶子数。 【解答】 设度为m 的树中度为0,1,2,…,m 的结点数分别为n0, n1, n2,…, nm，结点总数为n，分枝数为B，则下面二式成立 n= n0+n1+n2+ …+nm (1) n=B+1= n1+2n2 +…+mnm+1 (2) 由(1)和(2)得叶子结点数n0=1+ 即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=8 6.2 一棵完全二叉树上有 1001 个结点，求叶子结点的个数。 【解答】因为在任意二叉树中度为2 的结点数n2 和叶子结点数n0 有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1 的结点数为n1，则 n= n0+ n1+ n2 n=2n0+n1-1 1002=2n0+n1 由于在完全二叉树中，度为1 的结点数n1 至多为1，叶子数n0 是整数。本题中度为1 的结点数n1 只能是 0，故叶子结点的个数n0 为501. 注：解本题时要使用以上公式，不要先判断完全二叉树高 10，前 9 层是满二叉树，第 10 层都是叶子，……。虽然解法也对，但步骤多且复杂，极易出错。 6.3 一棵 124 个叶结点的完全二叉树，最多有多少个结点。 【解答】由公式 n=2n0+n1-1,当 n1 为1 时，结点数达到最多 248 个。 6.4．一棵完全二叉树有 500 个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1 的结点？有多少个度为2 的结点？如果完全二叉树有 501 个结点，结果如何？请写出推导过程。 【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1 的结点数只能为1，故叶子数为250，度为2 的结点数是249。 若完全二叉树有501 个结点，则叶子数251，度为2 的结点数是250，度为1的结点数为0。 6.5 某二叉树有20 个叶子结点，有30 个结点仅有一个孩子，则该二叉树的总结点数是多少。 【解答】由公式n=2n0+n1-1，得该二叉树的总结点数是69。 6.6 求一棵具有1025 个结点的二叉树的高h。 【解答】该二叉树最高为1025（只有一个叶子结点），最低高为11。因为210-1<1025<211-1，故1025个结点的二叉树最低高为11。 6.7 一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有多少结点。 【解答】第一层只一个根结点，其余各层都两个结点，这棵二叉树最少结点数是2h-1。 6.8 将有关二叉树的概念推广到三叉树，则一棵有244 个结点的完全三叉树的高度是多少。 【解答】设含n 个结点的完全三叉树的高度为h...