站長(zhǎng)資訊網(wǎng)在計(jì)算機(jī)科學(xué)中，二叉樹(shù)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。通常子樹(shù)被稱作“左子樹(shù)”（left subtree）和“右子樹(shù)”（right subtree）。二叉樹(shù)常被用于實(shí)現(xiàn)二叉查找樹(shù)和二叉堆。
一棵深度為k，且有2^k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)，稱為滿二叉樹(shù)。這種樹(shù)的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)。而在一棵二叉樹(shù)中，除最后一層外，若其余層都是滿的，并且或者最后一層是滿的，或者是在右邊缺少連續(xù)若干結(jié)點(diǎn)，則此二叉樹(shù)為完全二叉樹(shù)。具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為floor(log2n)+1。深度為k的完全二叉樹(shù)，至少有2k-1個(gè)葉子結(jié)點(diǎn)，至多有2k-1個(gè)結(jié)點(diǎn)。
某二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)葉子結(jié)點(diǎn)數(shù)是？
二叉樹(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。
拓展：
二叉樹(shù)是遞歸定義的，其結(jié)點(diǎn)有左右子樹(shù)之分，邏輯上二叉樹(shù)有五種基本形態(tài)：
-
空二叉樹(shù)——如圖(a)；
-
只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)——如圖(b)；
-
只有左子樹(shù)——如圖(c)；
-
只有右子樹(shù)——如圖(d)；
-
完全二叉樹(shù)——如圖(e)。
注意：盡管二叉樹(shù)與樹(shù)有許多相似之處，但二叉樹(shù)不是樹(shù)的特殊情形。
類型
(1)完全二叉樹(shù)——若設(shè)二叉樹(shù)的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布，這就是完全二叉樹(shù)。
(2)滿二叉樹(shù)——除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹(shù)。
(3)平衡二叉樹(shù)——平衡二叉樹(shù)又被稱為AVL樹(shù)（區(qū)別于AVL算法），它是一棵二叉排序樹(shù)，且具有以下性質(zhì)：它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。
