1.6 樹(shù)與二叉樹(shù)
    考點(diǎn)16 樹(shù)的定義
    樹(shù)是由n( n≥0)個(gè)結(jié)點(diǎn)組成的有限集合。若n =0，稱(chēng)為空樹(shù)；若n>0，則：
     　　 (1)有一個(gè)特定的稱(chēng)為根(root)的結(jié)點(diǎn)。它只有直接后件，但沒(méi)有直接前件；
     　　 (2)除根結(jié)點(diǎn)以外的其他結(jié)點(diǎn)可以劃分為m(m≥0)個(gè)互不相交的有限集合T0，T1，…，Tm-1，每個(gè)集合Ti(i=0，1，…，m-l)又是一棵樹(shù)，稱(chēng)為根的子樹(shù)，每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前件，但可以有0個(gè)或多個(gè)直接后件。
    樹(shù)型結(jié)構(gòu)具有如下特點(diǎn)：
     　　 (1)助每個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱(chēng)為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱(chēng)為樹(shù)的根結(jié)點(diǎn)，簡(jiǎn)稱(chēng)為樹(shù)的根；
     　　 (2)每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)；
     　　 (3)一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱(chēng)為樹(shù)的結(jié)點(diǎn)度；
     　　 (4)樹(shù)的層次稱(chēng)為樹(shù)的深度。
    在計(jì)算機(jī)中，可以用樹(shù)結(jié)構(gòu)來(lái)表示算術(shù)表達(dá)式，用樹(shù)來(lái)表示算術(shù)表達(dá)式的原則是：
     　　 (1)表達(dá)式中的每一個(gè)運(yùn)算符在樹(shù)中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱(chēng)為運(yùn)算符結(jié)點(diǎn)；
     　　 (2)運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹(shù)中為該運(yùn)算符結(jié)點(diǎn)的子樹(shù)(在樹(shù)中的順序?yàn)閺淖蟮接?；
     　　 (3)運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)。
    樹(shù)在計(jì)算機(jī)中通常用多重鏈表表示。
    考點(diǎn)17 二叉樹(shù)的定義及其基本性質(zhì)
    1什么是二叉樹(shù)
    二叉樹(shù)(binary tree)是由n(≥0)個(gè)結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹(shù)組成，并且左右子樹(shù)都是二叉樹(shù)。二叉樹(shù)可以是空集合，根可以有空的左子樹(shù)或空的右子樹(shù)。二叉樹(shù)不是樹(shù)的特殊情況，它們是兩個(gè)概念。
    二叉樹(shù)具有如下兩個(gè)特點(diǎn)：
     　　 (1)非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；
     　　 (2)每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。
    二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，或者說(shuō)，在二叉樹(shù)中，不存在度大于2的結(jié)點(diǎn)，并且二叉樹(shù)是有序樹(shù)(樹(shù)為無(wú)序樹(shù))，其子樹(shù)的順序不能顛倒，因此，二叉樹(shù)有5種不同的形態(tài)
     　　在二叉樹(shù)中，一個(gè)結(jié)點(diǎn)可以只有左子樹(shù)而沒(méi)有右子樹(shù)，也可以只有右子樹(shù)而沒(méi)有左子樹(shù)。當(dāng)一個(gè)結(jié)點(diǎn)既沒(méi)有左子樹(shù)也沒(méi)有右子樹(shù)時(shí)，該結(jié)點(diǎn)即是葉子結(jié)點(diǎn))
    2二叉樹(shù)的基本性質(zhì)
    性質(zhì)1：在二叉樹(shù)的第入層上至多有2k-1個(gè)結(jié)點(diǎn)(k≥1)。
    性質(zhì)2：深度為m的二叉樹(shù)至多有2m-1個(gè)結(jié)點(diǎn)。
    深度為m的二叉樹(shù)的的結(jié)點(diǎn)數(shù)是為二叉樹(shù)中每層上的結(jié)點(diǎn)數(shù)之和，由性質(zhì)1得到結(jié)點(diǎn)數(shù)。
    性質(zhì)3：對(duì)任何一棵二叉樹(shù)，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。
    如果葉子結(jié)點(diǎn)n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+l。
    設(shè)二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)為n1，二叉樹(shù)中總結(jié)點(diǎn)數(shù)為N，因?yàn)槎鏄?shù)中所有結(jié)點(diǎn)均小于或等于2，所以有
    N=n0+n1+n (1)
    再看二叉樹(shù)中的分支數(shù)，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有一個(gè)進(jìn)入分支，設(shè)m為二叉樹(shù)中的分支總數(shù)，則有
     N=m+1 (2)
    又由于二叉樹(shù)中這m個(gè)分支是分別由非葉子結(jié)點(diǎn)射出的。其中度為1的每個(gè)結(jié)點(diǎn)射出1個(gè)分支，度為2的每個(gè)結(jié)點(diǎn)射出2個(gè)分支。因此，二叉樹(shù)中所有度為1與度為2的結(jié)點(diǎn)射出的分支總數(shù)為n1+2n2 ，而在二叉樹(shù)中，總的射出分支數(shù)應(yīng)與總的進(jìn)入分支數(shù)相等，即
     m=n1+2n2 (3)
     將(3)代入(2)式有
    N=n1+2n2+1
     比較(1)和(4)并化簡(jiǎn)得
     n0=n2+1
    性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度至少為[log2n]+ 1，其中[log2n]表示log2n的整數(shù)部分。
    3滿二叉樹(shù)與完全二叉樹(shù)
    (l)滿二叉樹(shù)
    滿二叉樹(shù)是指這樣的一種二叉樹(shù)：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。深度為k的二叉樹(shù)具有2k-1個(gè)結(jié)點(diǎn)。即在滿二叉樹(shù)的第k層上有2k-1個(gè)結(jié)點(diǎn)。
    從上面滿二叉樹(shù)定義可知，必須是二叉樹(shù)的每一層上的結(jié)點(diǎn)數(shù)都達(dá)到，否則就不是滿二叉樹(shù)。深度為m的滿二叉樹(shù)有2m-1個(gè)結(jié)點(diǎn)。
    (2)完全二叉樹(shù)
    完全二叉樹(shù)是指這樣的二叉樹(shù)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。