什么樣的是完全二叉樹(shù)呢？與滿(mǎn)二叉樹(shù)有什么聯(lián)系和區(qū)別？完全二叉樹(shù)(Complete Binary Tree) 　　若設(shè)二叉樹(shù)的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，

什么樣的是完全二叉樹(shù)呢？與滿(mǎn)二叉樹(shù)有什么聯(lián)系和區(qū)別？

完全二叉樹(shù)(Complete Binary Tree) 　　若設(shè)二叉樹(shù)的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)。

　　完全二叉樹(shù)是由滿(mǎn)二叉樹(shù)而引出來(lái)的。對(duì)于深度為K的，有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱(chēng)之為完全二叉樹(shù)。　　若一棵二叉樹(shù)至多只有最下面的兩層上的結(jié)點(diǎn)的度數(shù)可以小于2，并且最下層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹(shù)成為完全二叉樹(shù)。完全二叉樹(shù)的定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)為完全二叉樹(shù)。特點(diǎn)：葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；對(duì)任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l 或l 1 滿(mǎn)二叉樹(shù)：一棵深度為k，且有2的(k)次方－1個(gè)節(jié)點(diǎn)的二叉樹(shù) 特點(diǎn)：每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù) 希望可以幫到你