2021年12月計(jì)算機(jī)二級(jí)MS office備考|二叉樹

2021年12月計(jì)算機(jī)二級(jí)MS office備考|二叉樹

(1)二叉樹的定義：二叉樹是一種非線性結(jié)構(gòu)，是有限的節(jié)點(diǎn)集合，該集合為空(空二叉樹)或由一個(gè)根節(jié)點(diǎn)及兩棵互不相交的左右二叉子樹組成?？煞譃闈M二叉樹和完全二叉樹，其中滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。二叉樹具有如下兩個(gè)特點(diǎn)：

•二叉樹可為空，空的二叉樹無節(jié)點(diǎn)，非空二叉樹有且只有一個(gè)根結(jié)點(diǎn);

•每個(gè)節(jié)點(diǎn)最多可有兩棵子樹，稱為左子樹和右子樹。

(2)二叉樹的基本性質(zhì)。

性質(zhì)1：在二叉樹的第k層上至多有2k-1個(gè)結(jié)點(diǎn)(k≥1)。

性質(zhì)2：深度為m的二叉樹至多有2m-1個(gè)結(jié)點(diǎn)。

性質(zhì)3：對(duì)任何一棵二叉樹，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度至少為[log2n]+1，其中[log2n]表示log2n的整數(shù)部分。

滿二叉樹與完全二叉樹

(1)滿二叉樹：滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。滿二叉樹在其第i層上有2i-1個(gè)結(jié)點(diǎn)。

從上面滿二叉樹定義可知，二叉樹的每一層上的結(jié)點(diǎn)數(shù)必須都達(dá)到最大，否則就不是滿二叉樹。深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)。

(2)完全二叉樹：完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值;在最后一層上只缺少右邊的若干結(jié)點(diǎn)。

如果—棵具有n個(gè)結(jié)點(diǎn)的深度為k的二叉樹，它的每—個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)為1～n的結(jié)點(diǎn)——對(duì)應(yīng)。

二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)節(jié)點(diǎn)由數(shù)據(jù)域和指針域(左指針域和右指針域)組成。二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱二叉鏈表，對(duì)滿二叉樹和完全二叉樹可按層次進(jìn)行順序存儲(chǔ)。

以上就是“2021年12月計(jì)算機(jī)二級(jí)MS office備考|二叉樹”及其相關(guān)內(nèi)容，想及時(shí)獲知下次成績(jī)查詢時(shí)間，大家可通過點(diǎn)擊使用環(huán)球網(wǎng)校“ 免費(fèi)預(yù)約短信提醒”，即可及時(shí)獲得時(shí)間提醒。環(huán)球網(wǎng)校友情提示：為方便小伙伴們更好地備考，環(huán)球網(wǎng)校特地為大家準(zhǔn)備了計(jì)算機(jī)二級(jí)復(fù)習(xí)資料，如有需要請(qǐng)點(diǎn)擊文章下方“免費(fèi)下載>>>2021年計(jì)算機(jī)二級(jí)考試真題及備考資料”下載學(xué)習(xí)。