6.2樹的定義
之前我們一直在談的是一對一的線性結(jié)構(gòu)，可現(xiàn)實中，還有很多一對多的情況需要處理，所以我們需要研究這種一對多的數(shù)據(jù)結(jié)構(gòu)----"樹"，考慮它的各種特性，來解決我們在編程中碰到的相關(guān)問題。
樹(Tree)是n(n>=0)個結(jié)點的有限集。n=0時稱為空樹。在任意一棵非空樹中:(1)有且僅有一個特定的稱為根(Root)的結(jié)點；(2)當n>1時，其余結(jié)點可分為m(m>O)個互不相交的有限集T1、T2、……、 Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹(SubTree)，如圖6-2-1所示。
樹的定義其實就是我們在講解棧時提到的遞歸的方法。也就是在樹的定義之中還用到了樹的概念，這是一種比較新的定義方法。圖6-2-2的子樹T1和子樹T2就是根結(jié)點A的子樹。當然，D、G、H、I組成的樹又是B為結(jié)點的子樹,E、J組成的樹是C為結(jié)點的子樹。
對于樹的定義還需要強調(diào)兩點:
1.n>0時根結(jié)點是唯一的，不可能存在多個根結(jié)點，別和現(xiàn)實中的大樹混在一起，現(xiàn)實中的樹有很多根須，那是真實的樹，數(shù)據(jù)結(jié)構(gòu)中的樹是只能有一個根結(jié)點。
2.m>0時，子樹的個數(shù)沒有限制，但它們一定是互不相交的。像圖6-2-3中的兩個結(jié)構(gòu)就不符合樹的定義，因為它們都有相交的子樹。
6.2.1 結(jié)點分類
樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點擁有的子樹數(shù)稱為結(jié)點的度(Degree)。度為0的結(jié)點稱為葉結(jié)點(Leaf)或終端結(jié)點;度不為0的結(jié)點稱為非終端結(jié)點或分支結(jié)點。除根結(jié)點之外，分支結(jié)點也稱為內(nèi)部結(jié)點。樹的度是樹內(nèi)各結(jié)點的度的最大值。如圖6-2-4所示，因為這棵樹結(jié)點的度的最大值是結(jié)點D的度，為3，所以樹的度也為3。
6.2.2 結(jié)點間關(guān)系
結(jié)點的子樹的根稱為該結(jié)點的孩子(Child)，相應地，該結(jié)點稱為孩子的雙親(Parent)。恩，為什么不是父或母，叫雙親呢?對于結(jié)點來說其父母同體，唯一的一個，所以只能把它稱為雙親了。同一個雙親的孩子之間互稱兄弟(Sibling)。結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的所有結(jié)點。所以對于H來說，D、B、A都是它的祖先。反之，以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫。B的子孫有D、G、H、I，如圖6-2-5所示。
6.2.3 樹的其他相關(guān)概念
結(jié)點的層次(Level)從根開始定義起，根為第一層，根的孩子為第二層。若某結(jié)點在第l層，則其子樹的根就在第1+1層。其雙親在同一層的結(jié)點直為堂兄弟。顯然圖6-2-6中的D、E、F是堂兄弟，而G、H、I、J也是。樹中結(jié)點的最大層次稱為樹的深度(Depth)或高度，當前樹的深度為4。
如果將樹中結(jié)點的各子樹看成從左至右是有次序的，不能互換的，則稱該樹為有序樹，否則稱為無序樹。
森林(Forest)是m(m>0)棵互不相交的樹的集合。對樹中每個結(jié)點而言，其子樹的集合即為森林。對于圖6-2-1中的樹而言，圖6-2-2中的兩棵子樹其實就可以理解為森林。
對比線性表與樹的結(jié)構(gòu)，它們有很大的不同，如圖6-2-7所示。
6.4樹的存儲結(jié)構(gòu)
說到存儲結(jié)構(gòu)，就會想到我們前面章節(jié)講過的順序存儲和鏈式存儲兩種結(jié)構(gòu)。
先來看看順序存儲結(jié)構(gòu)，用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。這對于線性表來說是很自然的，對于樹這樣一多對的結(jié)構(gòu)呢?
樹中某個結(jié)點的孩子可以有多個，這就意味著，無論按何種順序?qū)渲兴薪Y(jié)點存儲到數(shù)組中，結(jié)點的存儲位置都無法直接反映邏輯關(guān)系，你想想看，數(shù)據(jù)元素挨個的存儲，誰是誰的雙親，誰是誰的孩子呢?簡單的順序存儲結(jié)構(gòu)是不能滿足樹的實現(xiàn)要求的。
不過充分利用順序存儲和鏈式存儲結(jié)構(gòu)的特點，完全可以實現(xiàn)對樹的存儲結(jié)構(gòu)的表示。我們這里要介紹三種不同的表示法:雙親表示法、孩子表示法、孩子兄弟表示法。
6.4.1 雙親表示法
我們?nèi)丝赡芤驗榉N種原因，沒有孩子，但無論是誰都不可能是從石頭里蹦出來的，孫悟空顯然不能算是人，所以是人一定會有父母。樹這種結(jié)構(gòu)也不例外，除了根結(jié)點外，其余每個結(jié)點，它不一定有孩子，但是一定有且僅有一個雙親。
我們假設(shè)以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中，附設(shè)一個指示器指示其雙親結(jié)點到鏈表中的位置。也就是說，每個結(jié)點除了知道自己是誰以外，還知道它的雙親在哪里。它的結(jié)點結(jié)構(gòu)為表6-4-1所示。
其中data是數(shù)據(jù)域，存儲結(jié)點的數(shù)據(jù)信息。而parent是指針域，存儲該結(jié)點的雙親在數(shù)組中的下標。
由于根結(jié)點是沒有雙親的，所以我們約定根結(jié)點的位置域設(shè)置為-1，這也就意味著，我們所有的結(jié)點都存有它雙親的位置。如圖6-4-1中的樹結(jié)構(gòu)和表6-4-2中的樹雙親表示所示。
這樣的存儲結(jié)構(gòu)，我們可以根據(jù)結(jié)點的parent指針很容易找到它的雙親結(jié)點，所用的時間復雜度為O(1)，直到parent為-1時，表示找到了樹結(jié)點的根?？扇绻覀円澜Y(jié)點的孩子是什么，對不起，請遍歷整個結(jié)構(gòu)才行。
這真是麻煩，能不能改進一下呢?
當然可以。我們增加一個結(jié)點最左邊孩子的域，不妨叫它長子域，這樣就可以很容易得到結(jié)點的孩子。如果沒有孩子的結(jié)點，這個長子域就設(shè)置為-1，如表6-4-3所示。（表中下標為0的firstchild應該為1）
對于有0個或1個孩子結(jié)點來說，這樣的結(jié)構(gòu)是解決了要找結(jié)點孩子的問題了。甚至是有2個孩子，知道了長子是誰，另一個當然就是次子了。
另外一個問題場景，我們很關(guān)注各兄弟之間的關(guān)系，雙親表示法無法體現(xiàn)這樣的關(guān)系，那我們怎么辦?嗯，可以增加一個右兄弟域來體現(xiàn)兄弟關(guān)系，也就是說，每一個結(jié)點如果它存在右兄弟，則記錄下右兄弟的下標。同樣的，如果右兄弟不存在，則賦值為-1 ，如表6-4-4所示。
但如果結(jié)點的孩子很多，超過了2個。我們又關(guān)注結(jié)點的雙親、又關(guān)注結(jié)點的孩子、還關(guān)注結(jié)點的兄弟，而且對時間遍歷要求還比較高，那么我們還可以把此結(jié)構(gòu)擴展為有雙親域、長子域、再有右兄弟域。存儲結(jié)構(gòu)的設(shè)計是一個非常靈活的過程。一個存儲結(jié)構(gòu)設(shè)計得是否合理，取決于基于該存儲結(jié)構(gòu)的運算是否適合、是否方便，時間復雜度好不好等。注意也不是越多越好，有需要時再設(shè)計相應的結(jié)構(gòu)。就像再好昕的音樂，不停反復聽上千遍也會膩味，再好看的電影，一段時間反復看上百遍，也會無趣，你們說是吧?
6.4.2 孩子表示法
換一種完全不同的考慮方法 . 由于樹中每個結(jié)點可能有多棵子樹，可以考慮用多重鏈表，即每個結(jié)點有多個指針域，其中每個指針指向一棵子樹的根結(jié)點，我們把這種方法叫做多重鏈表表示法。不過，樹的每個結(jié)點的度，也就是它的孩子個數(shù)是不同的。所以可以設(shè)計兩種方案來解決。
方案一
一種是指針域的個數(shù)就等于樹的度，復習一下，樹的度是樹各個結(jié)點度的最大值。其結(jié)構(gòu)如表6-4-5所示。
其中data是數(shù)據(jù)域。childl到childd是指針域，用來指向該結(jié)點的孩子結(jié)點。
對于圖6-4-1的樹來說，樹的度是3，所以我們的指針域的個數(shù)是3，這種方法實現(xiàn)如圖6-4-2所示。
這種方法對于樹中各結(jié)點的度相差很大時，顯然是很浪費空間的，因為有很多的結(jié)點，它的指針域都是空的。不過如果樹的各結(jié)點度相差很小時，那就意味著開辟的空間被充分利用了，這時存儲結(jié)構(gòu)的缺點反而變成了優(yōu)點。
既然很多指針域都可能為空，為什么不按需分配空間呢。于是我們有了第二種方案。
方案二
第二種方案每個結(jié)點指針域的個數(shù)等于該結(jié)點的度，我們專門取一個位置來存儲結(jié)點指針域的個數(shù)，其結(jié)構(gòu)如表6-4-6所示。
其中data為數(shù)據(jù)域，degree為度域，也就是存儲該結(jié)點的孩子結(jié)點的個數(shù)，child1到childd為指針域，指向該結(jié)點的各個孩子的結(jié)點。
對于圖6-4-2的樹來說，這種方法實現(xiàn)如圖6-4-3所示。
這種方法克服了浪費空間的缺點，對空間利用率是很高了，但是由于各個結(jié)點的鏈表是不相同的結(jié)構(gòu)，加上要維護結(jié)點的度的數(shù)值，在運算上就會帶來時間上的損耗。
能否有更好的方法，既可以減少空指針的浪費又能使結(jié)點結(jié)構(gòu)相同。
仔細觀察，我們?yōu)榱艘闅v整棵樹，把每個結(jié)點放到一個順序存儲結(jié)構(gòu)的數(shù)組中是合理的，但每個結(jié)點的孩子有多少是不確定的，所以我們再對每個結(jié)點的孩子建立一個單鏈表體現(xiàn)它們的關(guān)系 。
這就是我們要講的孩子表示法。具體辦法是，把每個結(jié)點的孩子結(jié)點排列起來，以單鏈表作存儲結(jié)構(gòu)，則n個結(jié)點有n個孩子鏈表，如果是葉子結(jié)點則此單鏈表為空。然后n個頭指針又組成一個線性表，采用順序存儲結(jié)構(gòu)，存放進一個一維數(shù)組中，如圖6-4-4所示。
為此，設(shè)計兩種結(jié)點結(jié)構(gòu)，一個是孩子鏈表的孩子結(jié)點，如表6-4-7所示。
其中child是數(shù)據(jù)域，用來存儲某個結(jié)點在表頭數(shù)組中的下標。next是指針域，用來存儲指向某結(jié)點的下一個孩子結(jié)點的指針。
另一個是表頭數(shù)組的表頭結(jié)點，如表6-4-8所示。
其中data是數(shù)據(jù)域，存儲某結(jié)點的數(shù)據(jù)信息。firstchild是頭指針域，存儲該結(jié)點的孩子鏈表的頭指針。
這樣的結(jié)構(gòu)對于我們要查找某個結(jié)點的某個孩子，或者找某個結(jié)點的兄弟，只需要查找這個結(jié)點的孩子單鏈表即可。對于遍歷整棵樹也是很方便的，對頭結(jié)點的數(shù)組循環(huán)即可。
但是，這也存在著問題，我如何知道某個結(jié)點的雙親是誰呢?比較麻煩，需要整棵樹遍歷才行，難道就不可以把雙親表示法和孩子表示法綜合一下嗎?當然是可以。如圖6-4-5所示。
我們把這種方法稱為雙親孩子表示法，應該算是孩子表示法的改進。
6.4.3 孩子兄弟表示法
剛才我們分別從雙親的角度和從孩子的角度研究樹的存儲結(jié)構(gòu)，如果我們從樹結(jié)點的兄弟的角度又會如何呢? 當然，對于樹這樣的層級結(jié)構(gòu)來說，只研究結(jié)點的兄弟是不行的，我們觀察后發(fā)現(xiàn)，任意一棵樹，它的結(jié)點的第一個孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。 因此，我們設(shè)置兩個指針，分別指向該結(jié)點的第一個孩子和此結(jié)點的右兄弟。結(jié)點結(jié)構(gòu)如表6-4-9所示。
其中data是數(shù)據(jù)域，firstchild為指針域，存儲該結(jié)點的第一個孩子結(jié)點的存儲地址，rightsib是指針域，存儲該結(jié)點的右兄弟結(jié)點的存儲地址。
對于圖6-4-1的樹來說，這種方法實現(xiàn)的示意圖如圖6-4-6所示。
這種表示法，給查找某個結(jié)點的某個孩子帶來了方便，只需要通過firstchild找到此結(jié)點的長子，然后再通過長子結(jié)點的rightsib找到它的二弟，接著一直下去，直到找到具體的孩子。當然，如果想找某個結(jié)點的雙親，這個表示法也是有做陷的，那怎么辦呢?
對，如果真的有必要，完全可以再增加一個parent指針域來解決快速查找雙親的問題，這里就不再細談了。
其實這個表示法的最大好處是它把一棵復雜的樹變成了一棵二叉樹。我們把圖6-4-6變變形就成了圖6-4-7這個樣子。
這樣就可以充分利用二叉樹的特性和算法來處理這棵樹了。嗯?有人間，二叉樹是什么?哈哈，別急，這正是我接下來要重點講的內(nèi)容。
引用《大話數(shù)據(jù)結(jié)構(gòu)》作者：程杰
|
