Deja Vu

An extended binary tree has N internal nodes.

The External path length is E and the Internal path length is I.

Prove E = I + 2N         ( 中央資管97 資結 )

 

數學歸納法 對內部節點n做歸納證明                     

當n=k時成立 考慮n=k+1時 然後畫一顆樹 分成左右兩顆子樹  
另nL為左子樹的內部節點數 nR為右子樹的內部節點數        

IL為左子樹的內部路徑長 IR為右子樹的內部路徑長         

EL為左子樹的外部路徑長 ER為右子樹的外部路徑長          

可知 EL = IL + 2*nL 且 ER = IR + 2*2nR                 

且 n = nL + nR + 1                                     

且E = EL + (nL+1) + ER + (nR+1)                        
且 I = IL + nL + IR + nR                               
由以上幾式推出 E = I + 2*n 得證

這題感謝PTT awpadam 大大解答