信息學(xué)數(shù)據(jù)結(jié)構(gòu)趣談樹

1、數(shù)據(jù)結(jié)構(gòu)趣談樹樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹中稱為結(jié)點(diǎn)）按分支關(guān)系組織起來的結(jié)構(gòu)，很象自然界中的樹那樣。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹形象表示。樹在計(jì)算機(jī)領(lǐng)域中也得到廣泛應(yīng)用。一、樹的概述樹結(jié)構(gòu)的特點(diǎn)是：它的每一個(gè)結(jié)點(diǎn)都可以有不止一個(gè)直接后繼，除根結(jié)點(diǎn)外的所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨。（一）樹的定義樹是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合，其中：必有一個(gè)特定的稱為根(ROOT)的結(jié)點(diǎn)；剩下的結(jié)點(diǎn)被分成=0 個(gè)互不相交的集合 T1、T2、Tn，而且，這些集合的每一個(gè)又都是樹。樹 T1、T2、Tn 被稱作根的(Subtree)。樹中每

2、個(gè)分叉點(diǎn)稱為結(jié)點(diǎn)，起始結(jié)點(diǎn)稱為樹根，任意兩個(gè)結(jié)點(diǎn)間的連接關(guān)系稱為樹枝，結(jié)點(diǎn)下面不再有分枝稱為樹葉。結(jié)點(diǎn)的前趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的“雙親”，結(jié)點(diǎn)的后趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的“”或“孩子”，同一結(jié)點(diǎn)的“”之間互稱“兄弟”。（二）樹的表示樹中每個(gè)結(jié)點(diǎn)的內(nèi)容分兩部分表示：結(jié)點(diǎn)的性質(zhì)；結(jié)點(diǎn)的指針域。結(jié)點(diǎn)的性質(zhì)：描述結(jié)點(diǎn)的必要數(shù)據(jù)。結(jié)點(diǎn)的指針域：指向結(jié)點(diǎn)的每一個(gè)孩子。指針域采用多重鏈表，又分為不定長度結(jié)點(diǎn)的多重鏈表與固定長度結(jié)點(diǎn)的多重鏈表。不定長度結(jié)點(diǎn)的多重鏈表表示樹時(shí)，每個(gè)結(jié)點(diǎn)的指針域個(gè)數(shù)等于該結(jié)點(diǎn)的孩子的個(gè)數(shù)，其形式如下：每個(gè)指針域指向一個(gè)孩子，這樣雖然不浪費(fèi)空間，但由于結(jié)點(diǎn)長度不等，將給分配造成，給各種運(yùn)算帶

3、來極大不便。固定長度結(jié)點(diǎn)的多重鏈表表示樹時(shí)，樹中每個(gè)結(jié)點(diǎn)的指針域個(gè)數(shù)都相等于樹中結(jié)點(diǎn)的最大度數(shù)，也就是說，不論結(jié)點(diǎn)的孩子多少，其長度均取最大長度。這樣長度劃一，處理問題簡單方便，但對(duì)空間浪費(fèi)很大。一種稱之為二叉樹為了尋求一種恰當(dāng)?shù)臉涞牡臉湫徒Y(jié)構(gòu)。表示方法，DHILD1CHILD2CHILDn二、二叉樹二叉樹是一種十分重要的樹型結(jié)構(gòu)。它的特點(diǎn)是，樹中的每個(gè)結(jié)點(diǎn)最多只有兩棵，即樹中任何結(jié)點(diǎn)的度數(shù)不大于。二叉樹的有左右之分，而且，的左右次序是重要的，即使在只有一棵的情況下，也應(yīng)分清是樹還是右。（一）定義二叉樹是結(jié)點(diǎn)的有限集合，這個(gè)集合或是空的，或是由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的稱之為樹和右的二叉樹組成

4、。圖 2 列出了二叉樹的五種基本形態(tài)。圖 2(a)為空二叉樹；(b)只有一個(gè)結(jié)點(diǎn)的二叉樹；(c)只有樹的二叉樹；(d)只有右的二叉樹；(e)左右完全的二叉樹。（二）滿二叉樹一棵深度為 K 的滿二叉樹，是有 2K-1 個(gè)結(jié)點(diǎn)的深度為 K 的二叉樹。2K-1個(gè)結(jié)點(diǎn)是二叉樹所能具有的最大結(jié)點(diǎn)個(gè)數(shù)。圖 3 所示為一棵深度為的滿二叉樹。圖 3圖 4（三）完全二叉樹對(duì)滿二叉樹，從第一層的結(jié)點(diǎn)(即根)開始，由下而上，由右，按順序結(jié)點(diǎn)，便得到滿二叉樹的一個(gè)順序表示。據(jù)此，完全二叉樹定義如下：一棵具有個(gè)結(jié)點(diǎn)，深度為 K 的二叉樹，當(dāng)且僅當(dāng)所有結(jié)點(diǎn)對(duì)應(yīng)于深度為 K 的滿二叉樹中由至的那些結(jié)點(diǎn)時(shí)，該二叉樹便是完全二

5、叉樹。圖 4 是一棵完全二叉樹。（四）二叉樹的二叉樹一般采重鏈表作為其結(jié)構(gòu)，表中每個(gè)結(jié)點(diǎn)都有三個(gè)域：數(shù)據(jù)域 DATA、左指針域 LCHILD 和右指針域 RCHILD。其中指針域 LCHILD 和RCHILD 分別指向其左孩子和右孩子。如圖 5 所示。圖 5二叉樹結(jié)點(diǎn)的結(jié)構(gòu)形式三、二叉樹的遍歷遍歷是對(duì)樹的一種最基本的運(yùn)算，所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被一次，而且只被一次。由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實(shí)質(zhì)上是將二叉樹的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來表示。設(shè) L、D、R 分別表示遍歷樹、根結(jié)點(diǎn)和遍歷右， 則對(duì)一棵二叉樹的遍歷有三種情況：DLR

6、（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD （稱為后根次序遍歷）。（一）先根次序遍歷的遞歸定義若二叉樹為空，則返回；否則，依次執(zhí)行以下操作：根結(jié)點(diǎn)；按先根次序遍歷樹；按先根次序遍歷右；返回。例：圖 6 為表示表達(dá)式 （）/的二叉樹。圖 6根結(jié)點(diǎn)，得到字符。繼而先序遍歷此樹時(shí)，首先樹，按遞歸定義，先結(jié)點(diǎn)的的根結(jié)點(diǎn)，得到字符。類推結(jié)點(diǎn)的樹，此時(shí)只有葉子。得到葉子后，葉子父結(jié)點(diǎn)的右，得到右的根結(jié)點(diǎn)字符。再字符父結(jié)點(diǎn)的右結(jié)點(diǎn)的樹，得到葉子字符后，得到右根結(jié)點(diǎn)字符，。先序遍歷完整棵樹，得到序列為：這就是表達(dá)式的前綴表示或稱波蘭表示。/ （二）中根次序遍歷的遞歸定義若二叉樹為空，則返回；否則，作如下操作：按中根次序遍歷樹；根結(jié)點(diǎn)；按中根次序遍歷右返回。；中序遍歷圖 6 二叉樹時(shí)，引入棧，先將根結(jié)點(diǎn)字符入棧，按定義訪問根結(jié)點(diǎn)的樹，遇到的根結(jié)點(diǎn)字符入棧，結(jié)點(diǎn)的樹，到達(dá)葉子字符，則字符為第一個(gè)的結(jié)點(diǎn)。接著，將棧頂字符出棧，根結(jié)點(diǎn)字符。繼而其右，方法同上，根結(jié)點(diǎn)入棧，。這樣，中序遍歷完整棵樹后，得到的序列為： / 這就是表達(dá)式的中綴表示。（三）后根次序遍歷的遞歸定義若二叉樹為空，則返回；否則，作如下操作：按后根次序遍歷樹；按后根次序遍歷右；根結(jié)點(diǎn)；返回。對(duì)圖 6 二叉樹，后序遍歷后得到