[科普中國]-非空二叉樹

基本形態(tài)

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

(1)只有一個根結(jié)點的二叉樹

(2)只有左子樹

(3)只有右子樹

(4)完全二叉樹

類型非空二叉樹主要有以下三種類型：

滿二叉樹——一棵深度為k的且有個結(jié)點的二叉樹叫滿二叉樹。

特點：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)。

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

完全二叉樹——深度為k，有n個結(jié)點的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。

特點：葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)。 對任一結(jié)點，若其右分支下子孫的最大層次為L，則其左分支下子孫的最大層次必為L或L+1。

性質(zhì)在非空二叉樹中，第i層的結(jié)點總數(shù)不超過, i>=1；

對任何非空二叉樹T，若n0 表示葉結(jié)點的個數(shù)、n2 表示度為2 的非葉結(jié)點的個數(shù)，那么兩者滿足關(guān)系n0 = n2 + 1。