為什麼說「滿二叉樹也是完全二叉樹」？

01-30

完全二叉樹的定義是最後一層只缺少右邊的若干結點，這和滿二叉樹分明就不一致啊？

不知道這句話的出處是哪裡，不過如果這邊說的滿二叉樹是指 full binary tree 而完全二叉樹是指 complete binary tree，那麼這個結論是錯誤的。滿二叉樹並不一定是完全二叉樹，完全二叉樹也不一定是滿二叉樹。這個 pdf 鏈接中的第一頁給出了 full binary tree 與 complete binary tree 的定義，並且舉了一個是滿二叉樹而不是完全二叉樹的例子：http://courses.cs.vt.edu/~cs3114/Spring10/Notes/T03a.BinaryTreeTheorems.pdf

除非句子中的滿二叉樹指的是 perfect binary tree 這個結論才成立。

結合羅晟的資料，相關書籍資料，以及維基百科Binary tree，總結如下：
二叉樹的相關類型術語並不是嚴格統一和規範的，不同的文獻描述略有不同
[術語]
1.根二叉樹(Rooted Binary Tree)：
有一個根結點，每個結點至多有兩個孩子。
2.滿二叉樹(Full Binary Tree)：
要麼是葉子結點(結點的度為0)，要麼結點同時具有左右子樹(結點的度為2)。
3.完全二叉樹(Complete Binary Tree)：
每層結點都完全填滿，在最後一層上如果不是滿的，則只缺少右邊的若干結點。
4.完美二叉樹(Perfect Binary Tree)
所有的非葉子結點都有兩個孩子，所有的葉子結點都在同一層。即每層結點都完全填滿。
5.無限完全二叉樹(Infinite Complete Binary Tree)：
每個結點都有兩個孩子，結點的層數是無限的。
6.平衡二叉樹(Balanced Binary Tree)：
也稱為AVL樹，它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。

[個人理解]

1.可能由於計算機理論研究的發展，導致相關的術語隨之而演化和變遷，目前並沒有嚴格統一的描述，而國內的教材基本都是翻譯自國外的資料，所以會出現不同的說法，類似的情況可能還有樹的深度的定義，有的根結點從0開始計數，有的從1開始計數。

2.國內早期教材中，滿二叉樹一般指 perfect binary tree，所以會有滿二叉樹是完全二叉樹的一個特例的說法。

3.下面這四種情況都有可能出現，具體可參考羅晟的資料

·既是Full Binary Tree 又是 Complete Binary Tree

·既不是 Bull Binary Tree 又不是 Complete Binary Tree

·是 Full Binary Tree 不是 Complete Binary Tree

·不是 Full Binary Tree 是 Complete Binary Tree

《演算法導論》第3版P690有定義如下：

滿二叉樹：每個節點是葉節點或者度為2.

完全二叉樹：所有葉節點深度相同，且所有內部節點度為2. （樹的節點總數達到最大）

我發現，不同的書籍對「滿二叉樹」，「完全二叉樹」定義不一樣啊

中文維基定義：

英文維基定義：

此為完美二叉樹定義：

歧義解釋：

國內做法：

所以你可以這麼想，我們讀的是GB23333標準的二叉樹定義，脫了褲子放屁自討沒趣，或者是有中國特色的二叉樹定義。也沒準是把滿二叉樹和完美二叉樹弄混了，為了不打「老前輩」的臉沿用了..

嗯就這樣！你應該能懂了（逃......

最近看了一本書，如果根據樓主的提問邏輯來分析，我覺得這本書上的定義比較符合。

滿二叉樹：二叉樹中的每個結點恰好有兩個孩子結點切所有葉子結點都在同一層。

按照如上定義來推滿二叉樹是完全二叉樹。

大概是不同教材的對於滿二叉樹和完全二叉樹的定義不同吧

我手頭的這個版本里對於完全二叉樹的定義是：

如果一棵二叉樹扣除其最大層次那層後即成為一棵滿二叉樹，且最後一層的所有結點均向左靠齊，則稱該二叉樹為完全二叉樹。

從這個定義出發的話，就可以有以下說法：

滿二叉樹一定為完全二叉樹，但完全二叉樹不一定為滿二叉樹。

國內張孝乃2002年編寫的老教材--《演算法與數據結構-C語言描述》

裡面是這樣定義的：

1.滿二叉樹：任何結點或者是樹葉或者有兩棵非空子樹

2.完全二叉樹：從左到右依次填充

定義與國外相同

滿二叉樹通俗理解如下：一個結點要麼是葉結點，要麼是有兩個子結點的中間結點。

完全二叉樹通俗理解如下：從根結點開始，依次從左到右填充樹結點。由此可見，滿二叉樹和完全二叉樹沒有特別的關係。