全國計算機等級考試二級公共根底之樹與二叉樹樹的根本概念顯的層次關(guān)系。用圖形表示樹這種數(shù)據(jù)構(gòu)造時，就象自然界中的倒長的樹，這種構(gòu)造就用“樹〞來命名。如圖：在樹構(gòu)造中，每個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一R〕。在樹構(gòu)造中，每一個結(jié)點可以有多個后件，它們都稱為該結(jié)點的子結(jié)點。沒W，Z，A，L，B，N，O，T，H，X〕。〔如R的度為4，KPQDEC2〕。樹的結(jié)點是層次構(gòu)造，一般按如下分層：根結(jié)點在第1層；同一個層全部結(jié)點的全部子結(jié)點都在下一層。樹的最大層次稱為樹的深度。如上圖中的4。R4KPQDEC在計算機中，可以用樹構(gòu)造表示算術(shù)運算。在算術(shù)運算中，一個運算符可以有假設(shè)干個運算對象。如取正〔+〕與取負〔-〕運算符只有一個運算對象，稱為單目運算符；加〔+〕、減〔-〕、乘〔*〕、除〔/〕、乘冪〔**〕有兩個運算對象，稱為雙目運算符；三元函數(shù)f(x,y,z)為f函數(shù)運算符，有三個運算對象，稱為三目運算符。多元函數(shù)有多個運算對象稱多目運算符。用樹表示算術(shù)表達式是：表達式中的每一個運算符在樹中對應(yīng)一個結(jié)點，稱為運算符結(jié)點運算符的每一個運算對象在樹中為該運算結(jié)點的子樹(在樹中的挨次從左到右)運算對象中的單變量均為葉子結(jié)點依據(jù)上面，可將表達式：a*(b+c/d)+c*h-g*f表示如下的樹。樹在計算機中通常用多重鏈表表示，多重鏈表的每個結(jié)點描繪了樹中對應(yīng)結(jié)點的信息，每個結(jié)點中的鏈域〔指針域〕個數(shù)隨樹中該結(jié)點的度而定。二叉樹及其根本性質(zhì)什么是二叉樹二叉樹是很有用的非線性構(gòu)造。它與樹構(gòu)造很相像，樹構(gòu)造的全部術(shù)語都可用到二叉樹這種構(gòu)造上。二叉樹具有以下兩個特點：〔1〕非空兩叉樹只有一個根結(jié)點〔2〕每個結(jié)點最多有兩棵子樹，且分別稱該結(jié)點的左子樹與右子樹。也就是說，在二叉樹中，每一個結(jié)點的度最大為2，而且全部子樹也均為二叉樹。二叉樹中的每一個結(jié)點可以有左子樹沒有右子樹，也可以有右子樹沒有左子樹，甚至左右子樹都沒有。二叉樹性質(zhì)有：性質(zhì)1：在二叉樹的第K層上，最多有2k-1(k>=1)個結(jié)點2：深度為m2m-1性質(zhì)3：在任意一棵二叉樹中，度為0的結(jié)點〔即葉子結(jié)點〕總比度為2的結(jié)點多一個4n[logn]+1,其中[logn]表2 2logn2滿二叉樹與完全二叉樹〔1滿兩叉樹是除了最終一層外，每一層上的全部結(jié)點都有兩個子結(jié)點。即在滿二叉樹中，每一層上的結(jié)點數(shù)都到達最大值。在滿二叉樹的第k層上有2k-1個m2m-1個結(jié)點。如圖：234〔2完全二叉樹除最終一層外，每一層上的結(jié)點數(shù)均到達最大數(shù)；最終一層只缺少右邊的假設(shè)干結(jié)點。如圖深度為34完全二叉樹具有以下兩共性質(zhì)：性質(zhì)5：具有n個結(jié)點的完全二叉樹的深度為[logn]+126：設(shè)完全[logn]+1n102從根結(jié)點開頭，按層序用自然數(shù)1,2,…n給結(jié)點進展編號，那么對于編號為k(k=1,2,…n)的結(jié)點有以下結(jié)論：〔1〕假設(shè)k=1，那么該結(jié)點為根結(jié)點，它沒有父結(jié)點；假設(shè)k>1，那么該結(jié)點的父結(jié)點編號為INT(k/2DK=4，那么它的父結(jié)點B2〔2〕假設(shè)2k<=n，那么編號為k的結(jié)點的左子結(jié)點編號為2k，否那么該結(jié)點無左子結(jié)點〔也無右子結(jié)點〕，如結(jié)點D的編號K=4，那么8<=10，它的左H8〔3〕假設(shè)2k+1<=n，那么編號為k的結(jié)點的右子結(jié)點編號為2k+1，否那么該結(jié)點無右子結(jié)點。如結(jié)點D的編號K=49<=10，它的右左子結(jié)點H編9二叉樹的存儲構(gòu)造在計算機中，二叉樹通常承受鏈式存儲構(gòu)造。與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點也由兩局部組成：數(shù)據(jù)域與指針域。但在二叉樹中，由于每一個元素可以有兩個后件〔即兩個子結(jié)點〕，因此，用于存儲二叉樹的存儲結(jié)點的指針域有兩個：一個用于指向結(jié)點的左子樹構(gòu)造的存儲地址，稱為左指針域；另一個用于指向右子樹結(jié)點的存儲地址，稱為右指針域。存儲構(gòu)造也稱為二叉鏈表。二叉樹存儲構(gòu)造如圖：二叉樹二叉鏈表的規(guī)律狀態(tài)二叉樹的遍歷二叉樹的遍歷是指不重復(fù)的訪問二叉樹中的全部結(jié)點。。在遍歷二叉樹過程中，當訪問到某個結(jié)點時，再往下訪問可能有兩個分支，應(yīng)訪問哪一個分支呢？對于二叉樹來說需要訪問根結(jié)點、左子樹全部結(jié)點、右子樹全部結(jié)點，在這三者中，應(yīng)訪問哪一個？也就是說，遍歷二叉樹實際是要確定訪問各結(jié)點的挨次。以便不重復(fù)又不能丟掉訪問結(jié)點，直到訪問到全部結(jié)點。在遍歷二叉樹的過程中，一般選遍歷左子樹，然后再遍歷右子樹，在先左后右下依據(jù)訪問結(jié)點次序，二叉樹的遍歷分為三種方法。方法如下：前序遍歷〔DLR〕前序遍歷首先訪問根結(jié)點然后遍歷左子樹，最終遍歷右子樹。在遍歷左、右子樹時，仍舊先訪問根結(jié)點，然后遍歷左子樹，最終遍歷右子樹。即：假設(shè)二叉樹為空那么完畢返回，否那么：〔1〕訪問根結(jié)點〔2〕前序遍歷左子樹〔3〕前序遍歷右子樹留意的是：遍歷左右子樹時仍舊承受前序遍歷方法。例：如圖二叉樹，那么前序遍歷結(jié)果是：ABDECF中序遍歷〔LDR〕中序遍歷首先遍歷左子樹，然后訪問根結(jié)點，最終遍歷右子樹。在遍歷左、右子樹時，仍舊先遍歷左子樹，再訪問根結(jié)點，最終遍歷右子樹。即：假設(shè)二叉樹為空那么完畢返回，否那么：〔1〕中序遍歷左子樹〔2〕訪問根結(jié)點〔3〕中序遍歷右子樹。留意的是：遍歷左右子樹時仍舊承受中序遍歷方法。例：如圖二叉樹，那么中序遍歷結(jié)果是：DBEAFC后序遍歷〔LRD〕后序遍歷首先遍歷左子樹，然后遍歷右子樹，最終訪問根結(jié)點。在遍歷左、右子樹時，仍舊先遍歷