全國計算機等級考試二級公共基礎之樹與二叉樹

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