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

因?yàn)閲鴥?nèi)早期教材中，滿二叉樹一般指 perfect binary tree，所以會(huì)有滿二叉樹是完全二叉樹的一個(gè)特例的說法。類似的情況可能還有樹的深度的定義，有的根結(jié)點(diǎn)從0開始計(jì)數(shù)，有的從1開始計(jì)數(shù)。

滿二叉樹(Full Binary Tree):

一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。也就是說，如果一個(gè)二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是(2^k) -1 ，則它就是滿二叉樹。

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

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

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

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

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

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

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

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

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

完全二叉樹(Complete Binary Tree):

完全二叉樹：完全二叉樹的節(jié)點(diǎn)數(shù)是任意的，從形式上講它是個(gè)缺失的的三角形，但所缺失的部分一定是右下角某個(gè)連續(xù)的部

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

設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，

這就是完全二叉樹。

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

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

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

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

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

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

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

延伸閱讀：

二、完全二叉樹判定

1>如果樹為空，則直接返回錯(cuò)

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

2.1>如果一個(gè)結(jié)點(diǎn)左右孩子都不為空，則pop該節(jié)點(diǎn)，將其左右孩子入隊(duì)列；

2.1>如果遇到一個(gè)結(jié)點(diǎn)，左孩子為空，右孩子不為空，則該樹一定不是完全二叉樹；

2.2>如果遇到一個(gè)結(jié)點(diǎn)，左孩子不為空，右孩子為空；或者左右孩子都為空，且則該節(jié)點(diǎn)之后的隊(duì)列中的結(jié)點(diǎn)都為葉子節(jié)點(diǎn)，該樹才是完全二叉樹，否則就不是完全二叉樹。