在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。

一棵深度為k，且有2^k-1個(gè)結(jié)點(diǎn)的二叉樹，稱為滿二叉樹。這種樹的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。而在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且或者最后一層是滿的，或者是在右邊缺少連續(xù)若干結(jié)點(diǎn)，則此二叉樹為完全二叉樹。具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個(gè)葉子結(jié)點(diǎn)，至多有2k-1個(gè)結(jié)點(diǎn)。

某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹葉子結(jié)點(diǎn)數(shù)是？

二叉樹中的葉子結(jié)點(diǎn)數(shù)與度為2的結(jié)點(diǎn)數(shù)的關(guān)系是：度為2的結(jié)點(diǎn)數(shù)=葉子結(jié)點(diǎn)數(shù)-1；

所以，葉子結(jié)點(diǎn)數(shù)=度為2的結(jié)點(diǎn)數(shù)+1=6。

拓展：

二叉樹是遞歸定義的，其結(jié)點(diǎn)有左右子樹之分，邏輯上二叉樹有五種基本形態(tài)：

1. 空二叉樹——如圖(a)；

2. 只有一個(gè)根結(jié)點(diǎn)的二叉樹——如圖(b)；

3. 只有左子樹——如圖(c)；

4. 只有右子樹——如圖(d)；

5. 完全二叉樹——如圖(e)。

注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。

類型

(1)完全二叉樹——若設(shè)二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹。

(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區(qū)別于AVL算法），它是一棵二叉排序樹，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。