一、為什么說“滿二叉樹也是完全二叉樹”
因為國內早期教材中,滿二叉樹一般指 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>如果遇到一個結點,左孩子不為空,右孩子為空;或者左右孩子都為空,且則該節點之后的隊列中的結點都為葉子節點,該樹才是完全二叉樹,否則就不是完全二叉樹。