一、為什么說“滿二叉樹也是完全二叉樹”

因為國內早期教材中，滿二叉樹一般指 perfect binary tree，所以會有滿二叉樹是完全二叉樹的一個特例的說法。類似的情況可能還有樹的深度的定義，有的根結點從0開始計數，有的從1開始計數。

滿二叉樹(Full Binary Tree):

一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二叉樹。

一顆樹深度為h，最大層數為k，深度與最大層數相同，k=h;

它的葉子數是： 2^h　　第k層的結點數是： 2^(k-1)　　總結點數是： 2^k-1 (2的k次方減一)　　總節點數一定是奇數。

???????????????????????????????????????????? 0

???????????????????????????????????? /?????????????? \

????????????????????????????????? 1?????????????????? 2

????????????????????????????? /????? \??????????? /?????? \

??????????????????????????? 3??????? 4???????? 5?????????? 6

????????????????????????? /? \??? /?? \???? /??? \?????? /?? \

??????????????????????? 7??? 8? 9???? 10? 11???? 12??? 13???? 14

完全二叉樹(Complete Binary Tree):

完全二叉樹：完全二叉樹的節點數是任意的，從形式上講它是個缺失的的三角形，但所缺失的部分一定是右下角某個連續的部

分，最后那一行可能不是完整的，對于k層的完全二叉樹，節點數的范圍2^ (k – 1) -1 < N< 2^k – 1;

設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，

這就是完全二叉樹。

????????????????????????????????????????????? 0

????????????????????????????? ???????/?????????????? \

????????????????????????????????? 1?????????????????? 2

????????????????????????????? /????? \??????????? /?????? \

??????????????????????????? 3??????? 4???????? 5?????????? 6

????????????????????????? /? \??? /?? \???? /???

??? ????????????????????7??? 8? 9???? 10? 11

延伸閱讀：

二、完全二叉樹判定

1>如果樹為空，則直接返回錯

2>如果樹不為空：層序遍歷二叉樹

2.1>如果一個結點左右孩子都不為空，則pop該節點，將其左右孩子入隊列；

2.1>如果遇到一個結點，左孩子為空，右孩子不為空，則該樹一定不是完全二叉樹；

2.2>如果遇到一個結點，左孩子不為空，右孩子為空；或者左右孩子都為空，且則該節點之后的隊列中的結點都為葉子節點，該樹才是完全二叉樹，否則就不是完全二叉樹。