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