例题1：深度为6的满二叉树第5层有（ 16 ）节点； 解析：深度为N的满二叉树第M层节点数为2(k-1); 2(5-1)=24=16个节点
例题2：一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ 501 ）；
解析：如果一棵完全二叉树的结点总数为n，那么叶子结点等于n/2（当n为偶数时）或者(n+1)/2（当n为奇数时）
（1001+1）/2=501
例题3：高度为5的完全二叉树中最少有（16 ）个结点；
解析：完全二叉树第5层最少1个结点才是最少。深度为N的满二叉树共有2n-1个节点。 先算深度4层的总结点：24-1=15；加上第5层的1个结点，15+1=16。
例题4：高度为5的完全二叉树中最多有（ 31 ）个结点；
解析：最多的情况就是最后一层全满。深度为N的满二叉树共有2n-1个结点。 25-1=31
例题5：设一棵完全二叉树有128个结点，则该完全二叉树的深度为（ 8 ） 解析：包含n个结点的二叉树的高度至少为(log2n)+1
深度为7的完全二叉树最多有27-1=127个节点，128>127所以是深度为8的完全二叉树且第八行即最后一行只有一个叶子结点。
例题6：设一棵树的度为3，其中度为3，2，1的结点个数分别为4，1，3。则该树中的叶子结点树(10) 解析：因为节点总数等于总分支数+1， 设叶子节点数为n0
可得下列关系式n0+4+1+3=4*3+2*1+1*3+1 解得 n0=10
例题7：若一颗二叉树有126个结点，在第7层至多有（ C ）个结点。 A.32 B.64 C.63 D.不存在第7层
解析：性质1：二叉树第i层上的结点数目最多为2i-1(i>=1)；性质2：深度为k的二叉树至多有2k-1个结点（k>=1）
深度为7的结点最多是27-1=127，127-126=1，说明第7层少一个结点。 第7层结点最多是2i-1=27-1=26=64，减去1个结点，就是64-1=63。
例题8：某二叉树中度为2的结点有18个，则该二叉树中有（19）个叶子结点。 解析：n0＝n2＋1
n0＝18+1=19
例题9：一颗二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（219） 解析：n0＝n2＋1，先算n2的结点数为70-1=69。 n=n0+n1+n2=70+80+69=219
例题10：已知一颗二叉树的叶子结点的个数为250，总结点的个数为500，则该二叉树度为1的分支结点有（ 1 ）个
解析：n0＝n2＋1，先算n2的结点数为250-1=245。 n=n0+n1+n2 ；
n1=n-n0-n2=500-250-245=1
例题11：已知一颗满二叉树的总结点个数为255，则该满二叉树的叶子结点有（128）个 解析：28-1=255，说明二叉树有8层。 二叉树第i层上的结点数目最多为2i-1； 28-1=27=128
例题12：若一棵二叉树有2013个结点，且无度为1的结点，则叶结点的个数为（1007 ） 解析：n0＝n2＋1；n=n0+n1+n2 ；题目n1=0 n=n2＋1+n2 ；2013=2*n2+1； n2=2012/2=1006 n0=1006+1=1007
例题13：已知一棵完全二叉树的第8层有8个结点，则其叶子结点数是（68）
解析：第7层满二叉树，叶子结点有27-1=64；第8层有8个结点说明父结点是8/2=4； 第7层的叶子结点就是64-4=60；再加上第8层的叶子结点60+8=68。
例题14：如果哈夫曼树有67个结点，则可知叶结点总数为（34）
解析：由于哈夫曼树中没有度为1得结点。 只有度为0和度为2得结点。根据n2=n0-1, 则一棵有n0个叶子结点得哈夫曼树共有n=n0+n2=n0+ n0-1=2n0-1个结点 故哈夫曼树有67个结点，67=2n0-1则可知叶结点总数为34
例题15：将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1，编号49的结点X的双亲的编号为（ 24 ） 解析：深度为4的满二叉树结点有 2^4- 1 = 15
深度为5的满二叉树结点有 2^5- 1 = 31
49在深度6层上，49-31(5层总结点)=18，第6层上有18个结点，18/2=9，有9个父结点在第5层上，结点都是从左往右排，49的父结点就是深度4的结点数+第5层的父结点，也就是15+9=24
02142数据结构导论计算题 - 图文
