數(shù)據(jù)結(jié)構(gòu)問題：一棵完全二叉樹有100個結(jié)點,度為一的結(jié)點有幾個,葉子結(jié)點有幾個?

數(shù)學(xué)人氣：737 ℃時間：2020-06-18 02:36:21

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

根據(jù)二叉樹的性質(zhì):對于一棵非空的二叉樹,如果葉子節(jié)點數(shù)為n0,度為2的結(jié)點數(shù)為n2,則no=n2+1.
根據(jù)完全二叉樹的定義可得:在完全二叉樹中度為1的結(jié)點n1只能取兩種情況,要么為0,要么為1. 所以:n0+n1+n2=100 又n0=n2+1; 2n2=99-n1; 因為結(jié)點數(shù)為整數(shù),所以n1=1,n2=49,n0=50
所以度為1的結(jié)點有一個,葉子結(jié)點有50個