一、為什么說“滿二叉樹也是完全二叉樹”
因為國內(nèi)早期教材中,滿二叉樹一般指 perfect binary tree,所以會有滿二叉樹是完全二叉樹的一個特例的說法。類似的情況可能還有樹的深度的定義,有的根結(jié)點從0開始計數(shù),有的從1開始計數(shù)。
滿二叉樹(Full Binary Tree):
一個二叉樹,如果每一個層的結(jié)點數(shù)都達到最大值,則這個二叉樹就是滿二叉樹。也就是說,如果一個二叉樹的層數(shù)為K,且結(jié)點總數(shù)是(2^k) -1 ,則它就是滿二叉樹。
一顆樹深度為h,最大層數(shù)為k,深度與最大層數(shù)相同,k=h;
它的葉子數(shù)是: 2^h 第k層的結(jié)點數(shù)是: 2^(k-1) 總結(jié)點數(shù)是: 2^k-1 (2的k次方減一) 總節(jié)點數(shù)一定是奇數(shù)。
???????????????????????????????????????????? 0
???????????????????????????????????? /?????????????? \
????????????????????????????????? 1?????????????????? 2
????????????????????????????? /????? \??????????? /?????? \
??????????????????????????? 3??????? 4???????? 5?????????? 6
????????????????????????? /? \??? /?? \???? /??? \?????? /?? \
??????????????????????? 7??? 8? 9???? 10? 11???? 12??? 13???? 14
完全二叉樹(Complete Binary Tree):
完全二叉樹:完全二叉樹的節(jié)點數(shù)是任意的,從形式上講它是個缺失的的三角形,但所缺失的部分一定是右下角某個連續(xù)的部
分,最后那一行可能不是完整的,對于k層的完全二叉樹,節(jié)點數(shù)的范圍2^ (k – 1) -1 < N< 2^k – 1;
設二叉樹的深度為h,除第 h 層外,其它各層 (1~h-1) 的結(jié)點數(shù)都達到最大個數(shù),第 h 層所有的結(jié)點都連續(xù)集中在最左邊,
這就是完全二叉樹。
????????????????????????????????????????????? 0
????????????????????????????? ???????/?????????????? \
????????????????????????????????? 1?????????????????? 2
????????????????????????????? /????? \??????????? /?????? \
??????????????????????????? 3??????? 4???????? 5?????????? 6
????????????????????????? /? \??? /?? \???? /???
??? ????????????????????7??? 8? 9???? 10? 11
延伸閱讀:
二、完全二叉樹判定
1>如果樹為空,則直接返回錯
2>如果樹不為空:層序遍歷二叉樹
2.1>如果一個結(jié)點左右孩子都不為空,則pop該節(jié)點,將其左右孩子入隊列;
2.1>如果遇到一個結(jié)點,左孩子為空,右孩子不為空,則該樹一定不是完全二叉樹;
2.2>如果遇到一個結(jié)點,左孩子不為空,右孩子為空;或者左右孩子都為空,且則該節(jié)點之后的隊列中的結(jié)點都為葉子節(jié)點,該樹才是完全二叉樹,否則就不是完全二叉樹。