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

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

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

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

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

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