已知一棵度为m的树中有:n1个度为1的结点,n2个度为2的结点,……,nm个度为m的结点,计算该树中共有多少叶子结点?有多少非终端结点?
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/12 14:40:33
![已知一棵度为m的树中有:n1个度为1的结点,n2个度为2的结点,……,nm个度为m的结点,计算该树中共有多少叶子结点?有多少非终端结点?](/uploads/image/z/8552512-64-2.jpg?t=%E5%B7%B2%E7%9F%A5%E4%B8%80%E6%A3%B5%E5%BA%A6%E4%B8%BAm%E7%9A%84%E6%A0%91%E4%B8%AD%E6%9C%89%EF%BC%9An1%E4%B8%AA%E5%BA%A6%E4%B8%BA1%E7%9A%84%E7%BB%93%E7%82%B9%2Cn2%E4%B8%AA%E5%BA%A6%E4%B8%BA2%E7%9A%84%E7%BB%93%E7%82%B9%2C%E2%80%A6%E2%80%A6%2Cnm%E4%B8%AA%E5%BA%A6%E4%B8%BAm%E7%9A%84%E7%BB%93%E7%82%B9%2C%E8%AE%A1%E7%AE%97%E8%AF%A5%E6%A0%91%E4%B8%AD%E5%85%B1%E6%9C%89%E5%A4%9A%E5%B0%91%E5%8F%B6%E5%AD%90%E7%BB%93%E7%82%B9%3F%E6%9C%89%E5%A4%9A%E5%B0%91%E9%9D%9E%E7%BB%88%E7%AB%AF%E7%BB%93%E7%82%B9%3F)
xՒ[N@
^XwBt B "x &j*"3-x0i97̦O;oyV+R$$$VYΖV՟<2BQ=4aOL' 1*$mU方:{΄nDz?1J T^'}70ZS^j N]Y+`"=N<3slr&TA hN
R$J(!EQ i,/v/ p2ݜ&v[ý6OL/ER#̖E&)i{L
KЩHSF/ggܗྍ+k"'F)~ٿ%
已知一棵度为m的树中有:n1个度为1的结点,n2个度为2的结点,……,nm个度为m的结点,计算该树中共有多少叶子结点?有多少非终端结点?
已知一棵度为m的树中有:n1个度为1的结点,n2个度为2的结点,……,nm个度为m的结点,计算该树中共有多少叶子结点?有多少非终端结点?
已知一棵度为m的树中有:n1个度为1的结点,n2个度为2的结点,……,nm个度为m的结点,计算该树中共有多少叶子结点?有多少非终端结点?
不知道我有没有记错,非终端结点应该是指至少拥有一个孩子的结点,那么显然的,非终端结点的个数S:
S = n1+n2+n3+...+nm
叶子结点就是没有任何孩子的结点,那么其度为0,假设叶子结点数为n0,并假设树的结点数为N,那么:
N = n0+n1+n2+...+nm
并且N除了根节点,其他都有父结点,这些父节点都是有其他结点的出度构成,则:
N = n1+2*n2+3*n3+...+m*nm+1
这样得到n0+n1+n2+...+nm = 1+n1+2*n2+3*n3+...+m*nm
即得:n0 = n2+2*n3+3*n4+...+(m-1)*nm+1