第1次必定是2個葉子組成二叉樹,產(chǎn)生1新結(jié)點,接下來有2種情況：
1.此新結(jié)點與原剩下的葉子再組成二叉樹又產(chǎn)生1新結(jié)點,這樣就只有第1次時由2個葉子產(chǎn)生1新結(jié)點,以后每次由1葉子與新結(jié)點產(chǎn)生新結(jié)點,故n個葉子共有2n-1個結(jié)點.
2.剩下的葉子中又有2個葉子(比第1次產(chǎn)生的新結(jié)點權(quán)小)結(jié)合產(chǎn)生新結(jié)點,其它類似,那么必然會由2個都是新結(jié)點再產(chǎn)生新結(jié)點,所以實際上數(shù)量與第1種一樣,共有2n-1個.
具體證明用一個構(gòu)造哈夫曼樹的算法.