全國計(jì)算機(jī)等級考試二級公共基礎(chǔ)之樹與二叉樹

1、全國計(jì)算機(jī)等級考試二級公共基礎(chǔ)之樹與二叉樹1.6樹與二叉樹樹的基本概念樹是一種簡單的非線性結(jié)構(gòu)。在樹這種結(jié)構(gòu)中，所有元素之間的關(guān)系具有明顯的層次關(guān)系。用圖形表示樹這種數(shù)據(jù)結(jié)構(gòu)時(shí)，就象自然界中的倒長的樹，這種結(jié)構(gòu)就用“樹”來命名。如圖：在樹結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡稱為樹的根（如R）o在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)（如WZ,A,L,B,N,QT,H,X）。在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)擁有的后件個(gè)數(shù)稱為結(jié)點(diǎn)的度（如R的度為4,KPQDEC結(jié)點(diǎn)度均為2）。樹的結(jié)點(diǎn)是層次結(jié)構(gòu)，一般按如下原則分

2、層：根結(jié)點(diǎn)在第1層；同一個(gè)層所有結(jié)點(diǎn)的所有子結(jié)點(diǎn)都在下一層。樹的最大層次稱為樹的深度。如上圖中的樹深度為4。R結(jié)點(diǎn)有4棵子樹，KPQDEC占各有兩棵子樹；葉子沒有子樹。在計(jì)算機(jī)中，可以用樹結(jié)構(gòu)表示算術(shù)運(yùn)算。在算術(shù)運(yùn)算中，一個(gè)運(yùn)算符可以有若干個(gè)運(yùn)算對象。如取正（+）與取負(fù)（-）運(yùn)算符只有一個(gè)運(yùn)算對象，稱為單目運(yùn)算符；力口（+）、減（-）、乘（*）、除（/）、乘嘉（*）有兩個(gè)運(yùn)算對象，稱為雙目運(yùn)算符；三元函數(shù)f（x,y,z）為f函數(shù)運(yùn)算符，有三個(gè)運(yùn)算對象，稱為三目運(yùn)算符。多元函數(shù)有多個(gè)運(yùn)算對象稱多目運(yùn)算符。用樹表示算術(shù)表達(dá)式原則是：（1）表達(dá)式中的每一個(gè)運(yùn)算符在樹中對應(yīng)一個(gè)結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)(2

3、)運(yùn)算符的每一個(gè)運(yùn)算對象在樹中為該運(yùn)算結(jié)點(diǎn)的子樹(在樹中的順序從左到右)(3)運(yùn)算對象中的單變量均為葉子結(jié)點(diǎn)根據(jù)上面原則，可將表達(dá)式：a*(b+c/d)+c*h-g*f表示如下的樹。樹在計(jì)算機(jī)中通常用多重鏈表表示，多重鏈表的每個(gè)結(jié)點(diǎn)描述了樹中對應(yīng)結(jié)點(diǎn)的信息，每個(gè)結(jié)點(diǎn)中的鏈域(指針域)個(gè)數(shù)隨樹中該結(jié)點(diǎn)的度而定。二叉樹及其基本性質(zhì).什么是二叉樹二叉樹是很有用的非線性結(jié)構(gòu)。它與樹結(jié)構(gòu)很相似，樹結(jié)構(gòu)的所有術(shù)語都可用到二叉樹這種結(jié)構(gòu)上。二叉樹具有以下兩個(gè)特點(diǎn)：(1)非空兩叉樹只有一個(gè)根結(jié)點(diǎn)(2)每個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱該結(jié)點(diǎn)的左子樹與右子樹。也就是說，在二叉樹中，每一個(gè)結(jié)點(diǎn)的度最大為2,而且所有

4、子樹也均為二叉樹。二叉樹中的每一個(gè)結(jié)點(diǎn)可以有左子樹沒有右子樹，也可以有右子樹沒有左子樹，甚至左右子樹都沒有。2.二叉樹的基本性質(zhì)二叉樹性質(zhì)有:性質(zhì)性質(zhì)1:在二叉樹的第K層上，最多有2k-1(k=1)個(gè)結(jié)點(diǎn)2:深度為m的二叉樹最多有221個(gè)結(jié)點(diǎn)性質(zhì)3:在任意一棵二叉樹中，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總比度為2的結(jié)點(diǎn)多一個(gè)性質(zhì)4：具有n個(gè)結(jié)占的二叉樹，其深度至少為log2n+1,其中l(wèi)og2n表示取log2n的整數(shù)部分。3.滿二叉樹與完全二叉樹0 即在(1)滿二叉樹滿兩叉樹是除了最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值。在滿二叉樹的第k層上有2k-1個(gè)結(jié)點(diǎn)

5、，且深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)。如圖：深度為2的滿二叉樹(2)完全二叉樹深度為3的滿二叉樹寸飛百11ft小上深度為4的滿二叉樹完全二叉樹除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大數(shù)；最后一層只缺少右邊的若干結(jié)點(diǎn)。如圖深度為3的完全二叉樹性質(zhì)5:具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log 2n+1深度為4的完全二叉樹完全二叉樹具有以下兩個(gè)性質(zhì):性質(zhì)6:設(shè)完全log2n+1有n個(gè)結(jié)點(diǎn)(如右圖10個(gè)結(jié)點(diǎn),編號如圖)。如果從根結(jié)點(diǎn)開始，按層序用自然數(shù)1,2,n給結(jié)點(diǎn)進(jìn)行編號，則對于編號為k(k=1,2,口)的結(jié)點(diǎn)有以下結(jié)論：(1)若k=1,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k1,則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號

6、為INT(k/2)。如結(jié)點(diǎn)D的編號K=4,則它的父結(jié)點(diǎn)B的編號為2(2)若2k=n,則編號為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號為2k,否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)(也無右子結(jié)點(diǎn))，如結(jié)點(diǎn)D的編號K=4,則8=10,它的左子結(jié)點(diǎn)H編號為8(3)若2k+1=n,則編號為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號為2k+1,否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。如結(jié)點(diǎn)D的編號K=4,則9=10,它的右左子結(jié)點(diǎn)H編號為9二叉樹的存儲結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點(diǎn)也由兩部分組成：數(shù)據(jù)域與指針域。但在二叉樹中，由于每一個(gè)元素可以有兩個(gè)后件(即兩個(gè)子結(jié)點(diǎn))，因此，用于存儲二叉樹的存儲結(jié)點(diǎn)的指針域有兩個(gè)

7、：一個(gè)用于指向結(jié)點(diǎn)的左子樹結(jié)構(gòu)的存儲地址，稱為左指針域；另一個(gè)用于指向右子樹結(jié)點(diǎn)的存儲地址，稱為右指針域。由于二叉樹的存儲結(jié)構(gòu)中每一個(gè)存儲結(jié)點(diǎn)有兩個(gè)指針域，因此二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)也稱為二叉鏈表。二叉樹存儲結(jié)構(gòu)如圖：二叉樹4I/二叉鏈表的邏輯狀態(tài)二叉樹的遍歷二叉樹的遍歷是指不重復(fù)的訪問二叉樹中的所有結(jié)點(diǎn)。由于二叉樹是一種非線性結(jié)構(gòu)，因此對二叉樹的遍歷要比遍歷線性表復(fù)雜很多。在遍歷二叉樹過程中，當(dāng)訪問到某個(gè)結(jié)點(diǎn)時(shí)，再往下訪問可能有兩個(gè)分支，應(yīng)訪問哪一個(gè)分支呢？對于二叉樹來說需要訪問根結(jié)點(diǎn)、左子樹所有結(jié)點(diǎn)、右子樹所有結(jié)點(diǎn)，在這三者中，應(yīng)訪問哪一個(gè)？也就是說，遍歷二叉樹實(shí)際是要確定訪問各結(jié)點(diǎn)的順序。

8、以便不重復(fù)又不能丟掉訪問結(jié)點(diǎn)，直到訪問到所有結(jié)點(diǎn)。在遍歷二叉樹的過程中，一般選遍歷左子樹，然后再遍歷右子樹，在先左后右原則下根據(jù)訪問結(jié)點(diǎn)次序，二叉樹的遍歷分為三種方法。方法如下：.前序遍D(DLR前序遍歷首先訪問根結(jié)點(diǎn)然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。即：若二叉樹為空則結(jié)束返回，否則：(1)訪問根結(jié)點(diǎn)(2)前序遍歷左子樹(3)前序遍歷右子樹注意的是：遍歷左右子樹時(shí)仍然采用前序遍歷方法。例：如圖二叉樹，則前序遍歷結(jié)果是：ABDECF.中序遍歷(LDR在遍歷左、中序遍歷首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹右子樹時(shí)，仍然先遍歷左子樹，再訪問根結(jié)點(diǎn)，最后遍歷右子樹。若二叉樹為空則結(jié)束返回，否則：(1)中序遍歷左子樹(2)訪問根結(jié)點(diǎn)(3)中序遍歷右子樹。注意的是：遍歷左右子樹時(shí)仍然采用中序遍歷方法。例：如圖二叉樹，了DC可伺I也則中序遍歷結(jié)果是：DBEAFC.后序遍歷(LRD在遍歷左、即：后序遍歷首先遍歷左子樹，然后遍