CSP真題——二叉樹(shù)

高大力

CCF推出CSP認(rèn)證（Certified Softwmare Professional， 軟件能力認(rèn)證），以評(píng)價(jià)計(jì)算機(jī)專(zhuān)業(yè)人士或準(zhǔn)專(zhuān)業(yè)人士計(jì)算機(jī)科學(xué)的基礎(chǔ)能力——算法和編程能力。CSP已成為一些企業(yè)及許多大學(xué)評(píng)價(jià)計(jì)算機(jī)專(zhuān)業(yè)大學(xué)生專(zhuān)業(yè)能力的重要工具。

這是CSP2021初賽的一道選擇題，涉及知識(shí)點(diǎn)為二叉樹(shù)形態(tài)。

如果一棵二叉樹(shù)只有根結(jié)點(diǎn)，那么這棵二叉樹(shù)高度為1。請(qǐng)問(wèn)高度為5的完全二叉樹(shù)有（）種不同的形態(tài)？

A. 16

B. 15

C. 17

D. 32

二叉樹(shù)（Binary tree）是樹(shù)形結(jié)構(gòu)的一個(gè)重要類(lèi)型。二叉樹(shù)特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只能有兩棵子樹(shù)，通常子樹(shù)被稱(chēng)作“左子樹(shù)”（left subtree）和“右子樹(shù)”（right subtree），且左右次序不能顛倒。二叉樹(shù)的第i層至多有2^（i-1）個(gè)結(jié)點(diǎn);深度為k的二叉樹(shù)至多有2^k-1個(gè)結(jié)點(diǎn);深度為k，有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中，序號(hào)為1至n的節(jié)點(diǎn)對(duì)應(yīng)時(shí)，稱(chēng)之為完全二叉樹(shù)。

滿二叉樹(shù)的特點(diǎn)在于“滿”，即每層的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。

完全二叉樹(shù)是相對(duì)于滿二叉樹(shù)來(lái)說(shuō)的。二叉樹(shù)是有序樹(shù)，對(duì)一棵滿二叉樹(shù)和一棵完全二叉樹(shù)按“自上向下，自左向右”的順序進(jìn)行編號(hào)。完全二叉樹(shù)中的所有結(jié)點(diǎn)的編號(hào)必須和滿二叉樹(shù)的相同編號(hào)的結(jié)點(diǎn)在位置上完全相同。換句話說(shuō)，完全二叉樹(shù)的結(jié)點(diǎn)按“自上向下，自左向右”的順序不能中斷。T3 的結(jié)點(diǎn)C 沒(méi)有左葉子，顯然按那個(gè)順序是中斷的。

回到本題，高度為5的完全二叉樹(shù)，在第5層至多有2^（5-1）=16個(gè)節(jié)點(diǎn)，從1個(gè)節(jié)點(diǎn)到16個(gè)節(jié)點(diǎn)，可以至多有16種形態(tài)。