CSP真題——二叉樹

高大力

CCF推出CSP認證（Certified Softwmare Professional， 軟件能力認證），以評價計算機專業(yè)人士或準專業(yè)人士計算機科學的基礎能力——算法和編程能力。CSP已成為一些企業(yè)及許多大學評價計算機專業(yè)大學生專業(yè)能力的重要工具。

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

如果一棵二叉樹只有根結點，那么這棵二叉樹高度為1。請問高度為5的完全二叉樹有（）種不同的形態(tài)？

A. 16

B. 15

C. 17

D. 32

二叉樹（Binary tree）是樹形結構的一個重要類型。二叉樹特點是每個節(jié)點最多只能有兩棵子樹，通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree），且左右次序不能顛倒。二叉樹的第i層至多有2^（i-1）個結點;深度為k的二叉樹至多有2^k-1個結點;深度為k，有n個節(jié)點的二叉樹，當且僅當其每一個節(jié)點都與深度為k的滿二叉樹中，序號為1至n的節(jié)點對應時，稱之為完全二叉樹。

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

完全二叉樹是相對于滿二叉樹來說的。二叉樹是有序樹，對一棵滿二叉樹和一棵完全二叉樹按“自上向下，自左向右”的順序進行編號。完全二叉樹中的所有結點的編號必須和滿二叉樹的相同編號的結點在位置上完全相同。換句話說，完全二叉樹的結點按“自上向下，自左向右”的順序不能中斷。T3 的結點C 沒有左葉子，顯然按那個順序是中斷的。

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