二叉樹歸納證明

Question

現在我正在研究算法設計教科書中的一個問題，並且我碰到了一堵磚牆。

的問題是：

二進制樹是有根樹，其中每個節點最多有兩個孩子 。通過歸納顯示，在任何二叉樹中，有兩個孩子的 節點的數量恰好小於樹葉的數量。

我相當確定如何做到這一點：基本情況有一個單一的節點，這意味着樹有一個葉和零節點與兩個孩子。但是，我並不十分確定歸納步驟會帶來什麼。

Answer 1

具有單個節點且沒有子節點的樹（顯然）具有一個葉子。有兩個孩子（0）的節點數量恰好比樹葉數量（1）少一個。

將節點添加到沒有子節點的現有節點不會更改具有兩個子節點的節點數，也不會更改樹葉數。

添加到有一個孩子現有的節點，一個節點增加1節點有兩個孩子的數量，也由1

增加葉片的數量不能在節點添加到現有的節點與任何其他數量的孩子。

由於具有兩個子節點的節點的數量剛好小於樹葉的數量一個，並且向該樹添加一個節點要麼不更改數字，要麼兩者都增加一個，那麼它們之間的差異總是正好一個。

Answer 2

隨着感應上的節點的數量與2個孩子：

基 - 帶2個孩子的節點0 - 1個葉（假設根不計爲一個）。 Step - 假設T是一棵有n + 1> 0個節點並有2個子節點的樹

=>有一個節點a有2個子節點a1，a2並且在以a1或a2爲根節點的子樹中沒有節點2兒童。我們可以認爲它是植根於a1的子樹。

=>刪除以a1爲根的子樹，我們得到了一個具有n個節點並有2個子節點的樹T'。

=> T'有n + 1葉。

=>將以a1爲根的子樹添加到T' - 我們添加了一個葉子和一個包含2個子節點的節點。

你需要完成一些漏洞，但它工作正常。 對不起，我的英語不好。