→ awpadam:用數學歸納法 對內部節點n做歸納證明 03/22 15:56
→ awpadam:當n=k時成立 考慮n=k+1時 然後畫一顆樹 分成左右兩顆子樹 03/22 15:56
→ awpadam:另nL為左子樹的內部節點數 nR為右子樹的內部節點數 03/22 15:57
→ awpadam:IL為左子樹的內部路徑長 IR為右子樹的內部路徑長 03/22 15:58
→ awpadam:EL為左子樹的外部路徑長 ER為右子樹的外部路徑長 03/22 15:58
→ awpadam:可知 EL = IL + 2*nL 且 ER = IR + 2*2nR 03/22 15:59
→ awpadam:且 n = nL + nR + 1 03/22 15:59
→ awpadam:且E = EL + (nL+1) + ER + (nR+1) 03/22 16:00
→ awpadam:且 I = IL + nL + IR + nR 03/22 16:01
→ awpadam:由以上幾式推出 E = I + 2*n 得證 03/22 16:01