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