完全二叉樹 完全二叉樹與滿二叉樹的區(qū)別?
完全二叉樹與滿二叉樹的區(qū)別?區(qū)別在于最后一層。根據(jù)全二叉樹的定義,除最后一層外,每層中的所有節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)。也就是說倒數(shù)第二層的每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn),所以最后一層的節(jié)點(diǎn)數(shù)必須是倒數(shù)第二層的兩倍,
完全二叉樹與滿二叉樹的區(qū)別?
區(qū)別在于最后一層。根據(jù)全二叉樹的定義,除最后一層外,每層中的所有節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)。也就是說倒數(shù)第二層的每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn),所以最后一層的節(jié)點(diǎn)數(shù)必須是倒數(shù)第二層的兩倍,所以最后一層不缺一個(gè)節(jié)點(diǎn)。一個(gè)完整的二叉樹的最后一層的節(jié)點(diǎn)數(shù)可以是倒數(shù)第二層的兩倍(一個(gè)完整的二叉樹必須是一個(gè)完整的二叉樹),也可以是一個(gè)或兩個(gè)。但是,這些丟失的節(jié)點(diǎn)只能是最右邊的節(jié)點(diǎn)。