两道关于树的小计算真题
1.在一棵度数为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数为（）
A.41B.82C.D.
答案B
提示：树的结点个数=边数+1；（举例如果一个树只有一个节点。边的个数肯定是0，满足树的节点个数=边数+1）
树的结点个数=所有度的节点个数之和=N0+N1+N2+N3+....+Nn(N0是表示节点度为0的个数，N1节点度为1的个数.....)
建立等式边数+1=N0+N1+N2+N3+...+Nn
记住一定是一边是边数，一边是节点个数。
解析：设数中度（指的是子数根节点的分支数）为i（i=0,1,2,3,4）的结点数为Ni，树中总结点个数为N，则树中各结点的度之和等于=N-1，即有N1*1+N2*2+N3*3+N4*4=N-1=N0+N1+N2+N3+N4-1代入题设10*1+1*2+10*3+20*4=N0+10+1+10+20-1，解得N0=82即叶结点个数为82。
赞赏