主题：[请帮忙看一下]求叶子结点
endeavor0123
[专家分：0] 发布于 2007-12-05 08:57:00
若一棵树有n1个度为1的结点,n2个度为2的结点........nm个度为m的结点,试问:该树一共有多少个叶结点?
[size=1][帮忙解一下,请给出具体解法.谢谢!][/size]
回复列表 （共8个回复）
沙发
fly999 [专家分：150] 发布于 2007-12-05 09:37:00
很简单 有个公式
板凳
justforfun626 [专家分：18460] 发布于 2007-12-05 12:12:00
[quote]很简单 有个公式[/quote]
Yes, there must be one.
Can you provide your 公式?
Thanks!
3 楼
34353520 [专家分：60] 发布于 2007-12-06 11:13:00
好像是
∑nm*m+1。
原因很简单嘛，就是父节点的度等于子节点的个数嘛，因此用父节点的度代表子节点的个数，不包括度为零的节点的度，即叶子接点的度嘛，建立起一种父接点的度=子接点的个数的对应关系，最后考虑根接点和叶子接点，根接点没有父接点，应加上的，叶子接点已经包含在内了，
哈哈哈哈哈哈[em5][em5][em5][em5][em5]
欢迎加QQ:347291524.
4 楼
endeavor0123 [专家分：0] 发布于 2007-12-06 21:01:00
各位，我提出一个解题思路请大家批评指正。
【解】设该树有N个结点，其中叶子结点为n0个。
因为树的结点包括叶子结点，度为1的结点，度为2的结点，。。。，度为m的的结点，所以有n0+n1+n2+...+nm=N (1)
在看树中的分支数，除根结点外，其余结点都有一个分支进入，设B为分支总数，则N=B+1,而这些分支是由度为1,2,...,m的结点射出，所以有
N=1*n1+2*n2+...+m*nm+1(2)
综合(1)(2)得 n0=1*n1+2*n2+...+m*nm+1-n1-n2-...-nm=n2+2*n3+...+(m-1)nm+1
即为所求树的叶子结点个数。
5 楼
justforfun626 [专家分：18460] 发布于 2007-12-07 03:09:00
To endeavor0123:
I think your formula is correct, you can prove it by induction.
Thanks!
6 楼
bpttc [专家分：8790] 发布于 2007-12-07 12:40:00
关键点是整棵树边的总数
有两个方法从节点数计算得
1.向上想： 除根节点外，每个节点到其父节点都有一条边
所以 边数 = N0 + N1 + .... + Nm - 1 (1)
2.向下想： 每个节点到其子节点都有一条边
所以 边数 = 0 * N0 + 1 * N1 + 2 * N2 + ... + m * Nm (2)
最后联立(1)(2)
N0 = Sigma[i=1...m](i * Ni) - Sigma[i=1...m](Ni) + 1
= Sigma[i=1...m]( (i-1) * Ni ) + 1
7 楼
34353520 [专家分：60] 发布于 2007-12-07 15:25:00
大家都是高手啊!
我也是这么想的呢！
一个式子考虑到了n0~nm,一个式子考虑到了n1~nm,所以得到了n0的值。
关键就在于这棵树的所有的节点的总数是多少啊！
(1)∑nm*m
(2)∑m
8 楼
harderock [专家分：0] 发布于 2007-12-08 15:49:00
楼主说得没错
其实就是根据离散数学里的两个公式：
1. |V| = |E| + 1; ( |V| 代表节点个数，|E| 代表边的条数)
２. 树的总度数 D = 2 * |E|；
然后结合已知条件就可得出结果
要注意的是：上面说的总度数包括了入度，即叶子节点的度数是１
其他除根节点外总度数都要+１
在本题中：设叶子节点为n0 ，则根据上面所说可列出等式
D = 2 * ( n0 +n1+ ...+ nm -1)
根据题意，可列出另一等式
D = n0 + 2*n1 + 3*n2 + ... + (m+1)*nm - 1 (最后-１是减掉多算的根节点的入度)
由上面两等式可解出n0
与楼主结果一致
我来回复
您所在位置：