已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn),3個(gè)度為2的結(jié)點(diǎn),4個(gè)度3的結(jié)點(diǎn),則該樹有幾個(gè)葉子結(jié)點(diǎn)?

其他人氣：926 ℃時(shí)間：2020-06-09 13:17:07

優(yōu)質(zhì)解答

設(shè)該樹中的葉子數(shù)為n0個(gè).該樹中的總結(jié)點(diǎn)數(shù)為n個(gè),則有：
n=n0+n1+n2+…+nm (1)
又有除根結(jié)點(diǎn)外,樹中其他結(jié)點(diǎn)都有雙親結(jié)點(diǎn),且是唯一的(由樹中的分支表示),所以,有雙親的結(jié)點(diǎn)數(shù)為：
n-1=0*n0+1*n1+2*n2+…+m*nm (2)
聯(lián)立(1)(2)方程組可得：
葉子數(shù)為：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm