二叉樹(shù)基本概念1二叉樹(shù)定義二叉樹(shù)（BINARYTREE）是個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱(chēng)為根ROOT的元素及兩個(gè)不相交的、被分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。當(dāng)集合為空時(shí)，稱(chēng)該二叉樹(shù)為空二叉樹(shù)。在二叉樹(shù)中，一個(gè)元素也稱(chēng)作一個(gè)結(jié)點(diǎn)。二叉樹(shù)是有序的，即若將其左、右子樹(shù)顛倒，就成為另一棵不同的二叉樹(shù)。即使樹(shù)中結(jié)點(diǎn)只有一棵子樹(shù)，也要區(qū)分它是左子樹(shù)還是右子樹(shù)。因此二叉樹(shù)具有五種基本形態(tài)，如圖61所示。2二叉樹(shù)的相關(guān)概念（1）結(jié)點(diǎn)的度。結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。（2）葉結(jié)點(diǎn)。度為0的結(jié)點(diǎn)稱(chēng)為葉結(jié)點(diǎn)，或者稱(chēng)為終端結(jié)點(diǎn)。（3）分枝結(jié)點(diǎn)。度不為0的結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)，或者稱(chēng)為非終端結(jié)點(diǎn)。一棵樹(shù)的結(jié)點(diǎn)除葉結(jié)點(diǎn)外，其余的都是分支結(jié)點(diǎn)。（4）左孩子、右孩子、雙親。樹(shù)中一個(gè)結(jié)點(diǎn)的子樹(shù)的根結(jié)點(diǎn)稱(chēng)為這個(gè)結(jié)點(diǎn)的孩子。這個(gè)結(jié)點(diǎn)稱(chēng)為它孩子結(jié)點(diǎn)的雙親。具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱(chēng)為兄弟。（5）路徑、路徑長(zhǎng)度。如果一棵樹(shù)的一串結(jié)點(diǎn)N1,N2,NK有如下關(guān)系結(jié)點(diǎn)NI是NI1的父結(jié)點(diǎn)（1I1。性質(zhì)深度為K的二叉樹(shù)至多有2的K次方減1個(gè)結(jié)點(diǎn)K1。性質(zhì)對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為N0,度為2的結(jié)點(diǎn)數(shù)為N2,則N0N21。性質(zhì)具有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為|LOG2N|1性質(zhì)如果對(duì)一棵有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)I11,則雙親PARENTI是結(jié)點(diǎn)I/22如果2IN,則結(jié)點(diǎn)I無(wú)左孩子結(jié)點(diǎn)I為葉子結(jié)點(diǎn)否則其左孩子LCHILDI是結(jié)點(diǎn)2I3如