?
樹(shù)
----------------------
?
一、 基本概念
樹(shù)：是一種遞歸定義的數(shù)據(jù)結(jié)構(gòu)。樹(shù)(Tree)是樹(shù)結(jié)構(gòu)的簡(jiǎn)稱(chēng)，它是一種重要的非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。樹(shù)或者是一個(gè)空樹(shù)，即不含有任何的結(jié)點(diǎn)(元素)，或者是一個(gè)非空樹(shù)，即至少含有一個(gè)結(jié)點(diǎn)。
?
根：在一棵非空樹(shù)中，它有且僅有一個(gè)根節(jié)點(diǎn)。
?
子樹(shù)：在一棵非空樹(shù)中，除根外其余所有結(jié)點(diǎn)分屬于 m 個(gè)(m≥0)不相交的集合。每個(gè)集合又構(gòu)成一棵樹(shù)，稱(chēng)為根結(jié)點(diǎn)的子樹(shù)。
?
結(jié)點(diǎn)(node)：表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支。
?
結(jié)點(diǎn)的度(degree)：樹(shù)中的一個(gè)結(jié)點(diǎn)擁有的子樹(shù)數(shù)稱(chēng)為該結(jié)點(diǎn)的度 (Degree)。
?
葉子(leaf)：度為 0 的結(jié)點(diǎn)。
?
孩子(child)：結(jié)點(diǎn)子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子。
?
雙親(parents)：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的。
?
兄弟(sibling)：同一雙親的孩子。
?
樹(shù)的度：一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù)。
?
結(jié)點(diǎn)的層次(level)：從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……。
?
深度(depth)：樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。
?
有序樹(shù)：子樹(shù)的位置自左向右有次序關(guān)系的稱(chēng)為有序樹(shù)，順序決定了大小，孩子的次序不能改變。
?
無(wú)序樹(shù)：子樹(shù)的位置自左向右無(wú)次序關(guān)系的稱(chēng)為無(wú)序樹(shù)。
?
森林(Forest)：是 m(m≥0) 棵互不相交的樹(shù)的集合。樹(shù)和森林的概念相近。刪去一棵樹(shù)的根，就得到一個(gè)森林；反之，加上一個(gè)結(jié)點(diǎn)作樹(shù)根，森林就變?yōu)橐豢脴?shù)。
?
路徑：若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列 k1 ， k2 ， … ， ki ，使得 ki 是 ki+1 的雙親 (1≤i<j) ，則稱(chēng)該結(jié)點(diǎn)序列是從 k1 到 kj 的一條路徑 (Path) 或道路。
?
路徑的長(zhǎng)度：指路徑所經(jīng)過(guò)的邊 ( 即連接兩個(gè)結(jié)點(diǎn)的線(xiàn)段 ) 的數(shù)目，等于 j-1 。
?
祖先：若樹(shù)中結(jié)點(diǎn) k 到 ks 存在一條路徑，則稱(chēng) k 是 ks 的 祖先 (Ancestor) ， ks 是 k 的 子孫 (Descendant) 。結(jié)點(diǎn) k 的祖先和子孫不包含結(jié)點(diǎn) k 本身。
?
結(jié)點(diǎn)的層數(shù)：(Level)從根起算，根的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加1。雙親在同一層的結(jié)點(diǎn)互為堂兄弟。樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱(chēng)為樹(shù)的高度(Height)或深度(Depth)。很多文獻(xiàn)中將樹(shù)根的層數(shù)定義為 0 。
?
?
二、樹(shù)的其他特性
?
1.數(shù)的遞歸定義：
?
樹(shù)(Tree)是 n(n≥0) 個(gè)結(jié)點(diǎn)的有限集 T ， T 為空時(shí)稱(chēng)為空樹(shù)，否則它滿(mǎn)足如下兩個(gè)條件：
(1) 有且僅有一個(gè)特定的稱(chēng)為根 (Root) 的結(jié)點(diǎn)；
(2) 其余的結(jié)點(diǎn)可分為 m(m≥0) 個(gè)互不相交的子集 Tl,T2,…,Tm ，其中每個(gè)子集本身又是一棵樹(shù)，并稱(chēng)其為根的子樹(shù)(Subree) 。
?
注意：樹(shù)的遞歸定義刻畫(huà)了樹(shù)的固有特性：一棵非空樹(shù)是由若干棵子樹(shù)構(gòu)成的，而子樹(shù)又可由若干棵更小的子樹(shù)構(gòu)成。
?
2.樹(shù)的表示：
?
樹(shù)形圖表示是樹(shù)結(jié)構(gòu)的主要表示方法。其他還有廣義表、集合圖、凹入圖三種表示形式。
?
3.線(xiàn)性結(jié)構(gòu)和樹(shù)型結(jié)構(gòu)之間的區(qū)別：
?
|
|
線(xiàn)性結(jié)構(gòu)
|
樹(shù)型結(jié)構(gòu)
|
|
起點(diǎn)
|
第一個(gè)數(shù)據(jù)元素
(
無(wú)前驅(qū)
)
|
根結(jié)點(diǎn)
(
無(wú)前驅(qū)
)
|
|
終點(diǎn)
|
最后一個(gè)數(shù)據(jù)元素
(
無(wú)后繼
)
|
多個(gè)葉子結(jié)點(diǎn)
(
無(wú)后繼
)
|
|
中間
|
其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)
|
其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)
|
4.樹(shù)形結(jié)構(gòu)的邏輯特征：
?
樹(shù)形結(jié)構(gòu)的邏輯特征可用樹(shù)中結(jié)點(diǎn)之間的父子關(guān)系來(lái)描述：
(1) 樹(shù)中任一結(jié)點(diǎn)都可以有零個(gè)或多個(gè)直接后繼 (即孩子) 結(jié)點(diǎn)，但至多只能有一個(gè)直接前趨 (即雙親) 結(jié)點(diǎn)。
(2) 樹(shù)中只有根結(jié)點(diǎn)無(wú)前趨，它是開(kāi)始結(jié)點(diǎn)；葉結(jié)點(diǎn)無(wú)后繼，它們是終端結(jié)點(diǎn)。
(3) 祖先與子孫的關(guān)系是對(duì)父子關(guān)系的延拓，它定義了樹(shù)中結(jié)點(diǎn)之間的縱向次序。
(4) 有序樹(shù)中，同一組兄弟結(jié)點(diǎn)從左到右有長(zhǎng)幼之分。
對(duì)這一關(guān)系加以延拓，規(guī)定若 k1 和 k2 是兄弟，且 k1 在 k2 的左邊，則 k1 的任一子孫都在 k2 的任一子孫的左邊，那么就定義了樹(shù)中結(jié)點(diǎn)之間的橫向次序。
?
?
三、二叉樹(shù)的概念
?
二叉樹(shù)：指度為 2 的有序樹(shù)。是最簡(jiǎn)單的一種樹(shù)結(jié)構(gòu)，在計(jì)算機(jī)領(lǐng)域有著廣泛的應(yīng)用。
?
二叉樹(shù)的遞歸定義：二叉樹(shù)或者是一棵空樹(shù)，或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的分別稱(chēng)根的左子樹(shù)和右子樹(shù)所組成的非空樹(shù)，左子樹(shù)和右子樹(shù)又同樣都是一棵二叉樹(shù)。
?
二叉樹(shù)的孩子：二叉樹(shù)中，每個(gè)結(jié)點(diǎn)的左子樹(shù)的根結(jié)點(diǎn)被稱(chēng)為該結(jié)點(diǎn)的 左孩子 (left child) , 右子樹(shù)的根結(jié)點(diǎn)被稱(chēng)為 右孩子(left child)。
?
滿(mǎn)二叉樹(shù)：深度為 K 且含有 2K -1 個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)樹(shù)中的每一層都滿(mǎn)時(shí)成為漫二叉樹(shù)。
?
完全二叉樹(shù)：在一棵二叉樹(shù)中，除最后一層外，若其余層都是滿(mǎn)的，并且最后一層或者是滿(mǎn)的，或者在最右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)，則稱(chēng)此樹(shù)為完全二叉樹(shù)。
?
小根堆： 是具有如下特征的一棵完全二叉樹(shù)。
??? (1)若樹(shù)根接點(diǎn)存在左孩子，則根接點(diǎn)的值(或某個(gè)域的值)小于等于左孩子節(jié)點(diǎn)的值(或某個(gè)域的值)；
???
(2)若樹(shù)根接點(diǎn)存在右孩子，則根接點(diǎn)的值(或某個(gè)域的值)小于等于右孩子接點(diǎn)的值(或某個(gè)域的值)；
???
(3)以左、右孩子未跟的子樹(shù)又各是一個(gè)堆。
?
大根堆：定義與上述類(lèi)似，只要把小于等于改為大于等于就可。
?
二叉排序樹(shù)(Binary Sort Tree)：又稱(chēng)二叉查找(搜索)樹(shù)(Binary Search Tree)。
??? 其定義為：二叉排序樹(shù)或者是空樹(shù)，或者是滿(mǎn)足如下性質(zhì)的二叉樹(shù)：
??? (1)若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；
??? (2)若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；
??? (2)左、右子樹(shù)本身又各是一棵二叉排序樹(shù)。
?
注：以上的數(shù)據(jù)結(jié)構(gòu)均比較容易理解，不再畫(huà)圖舉例。
?
?
四、一些有關(guān)樹(shù)的計(jì)算題
?
1、一個(gè)具有767個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其葉子結(jié)點(diǎn)的個(gè)數(shù)為多少個(gè)？
?
因?yàn)槭峭耆鏄?shù)，所以只可能有0個(gè)或1個(gè)度為1的結(jié)點(diǎn)，其余葉子結(jié)點(diǎn)度為0，其他結(jié)點(diǎn)度為2。
又因?yàn)榻Y(jié)點(diǎn)總數(shù)為奇數(shù)，所以不存在度為1的結(jié)點(diǎn)(除根外都是成對(duì)出現(xiàn))。
?
設(shè)葉子結(jié)點(diǎn)有n0個(gè)，其余結(jié)點(diǎn)n2個(gè)，則n=n0+n2
又根據(jù)樹(shù)的邊數(shù)定義，總共有n-1條邊，則n2*2=n-1
?
所以n2=(n-1)/2=383
n0=767-383=384
?
2、一棵哈夫曼樹(shù)共有9個(gè)頂點(diǎn)，則其葉子結(jié)點(diǎn)的個(gè)數(shù)為多少個(gè)？
?
哈夫曼樹(shù)一定不存在度為1的結(jié)點(diǎn)，所以設(shè)葉子結(jié)點(diǎn)有n0個(gè)，其余結(jié)點(diǎn)n2個(gè)
則n=n0+n2
又根據(jù)樹(shù)的邊數(shù)定義，總共有n-1條邊，則n2*2=n-1
?
所以n2=(n-1)/2=4
n0=9-4=5
?
3、在一棵度為3的樹(shù)中，有2個(gè)度為3的結(jié)點(diǎn)，有1個(gè)度為2的結(jié)點(diǎn)，則有幾個(gè)度為0的結(jié)點(diǎn)？
?
設(shè)有n1個(gè)度為1的結(jié)點(diǎn)，n0個(gè)度為0的結(jié)點(diǎn)，則：
點(diǎn)數(shù)公式：n=2+1+n1+n0
邊數(shù)公式：n-1=2*3+1*2+n1*1
則下式減上式得到n0=6
?
?
?
?
***************************************************************************************************
?
圖
----------------------------------------
?
一、圖的基本定義
?
圖：是一種復(fù)雜的非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。
?
圖的二元組定義：
圖 G 由兩個(gè)集合 V 和 E 組成，記為：
G=(V,E)
??? 其中：
V 是頂點(diǎn)的有窮非空集合，
E 是 V 中頂點(diǎn)偶對(duì)(稱(chēng)為邊)的有窮集。
??? 通常，也將圖 G 的頂點(diǎn)集和邊集分別記為 V(G) 和 E(G) 。 E(G) 可以是空集。若 E(G) 為空，則圖 G 只有頂點(diǎn)而沒(méi)有邊。
?
有向圖：若圖 G 中的每條邊都是有方向的，則稱(chēng) G 為有向圖 (Digraph)。
?
無(wú)向圖：若圖 G 中的每條邊都是沒(méi)有方向的，則稱(chēng) G 為無(wú)向圖 (Undigraph)。
?
混合圖：既有有向邊，也有無(wú)向邊的圖
?
完全圖：若無(wú)向圖中的每個(gè)頂點(diǎn)之間存在著一條邊，有向圖中的每?jī)蓚€(gè)定點(diǎn)之間都存在著方向相反的兩條邊，則稱(chēng)此圖為完全圖。
?
注：無(wú)向完全圖n個(gè)頂點(diǎn)會(huì)有n(n-1)/2個(gè)頂點(diǎn)。
?
稠密圖：當(dāng)一個(gè)圖接近完全圖時(shí)，則稱(chēng)它為稠密圖。
?
稀疏圖：當(dāng)一個(gè)圖含有較少的邊數(shù)，即 e << n(n-1)時(shí)，則稱(chēng)它為稀疏圖。
?
?
二、其他圖的定義
?
平凡圖：僅有一個(gè)結(jié)點(diǎn)的圖。
?
零圖：邊集為空集的圖，即僅有結(jié)點(diǎn)的圖。
?
自回路(環(huán))：關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)的邊。
無(wú)向平行邊：聯(lián)結(jié)相同兩個(gè)結(jié)點(diǎn)的多于1條的無(wú)向邊。
?
有向平行邊：聯(lián)結(jié)兩個(gè)結(jié)點(diǎn)之間的多于1條且方向相同的有向邊。
?
簡(jiǎn)單圖：不含平行邊和自回路的圖。
度：
1. 在無(wú)向圖G＝<V,E>中，與結(jié)點(diǎn)v關(guān)聯(lián)的邊數(shù)，即為結(jié)點(diǎn)度數(shù)deg(v)或d(v)。
??? 2. 在有向圖中，結(jié)點(diǎn)v的出度和入度之和為度數(shù)。
??? 3. 在有向圖D＝<V,E>中，以v為起點(diǎn)的邊之條數(shù)為出度deg+(v)；以v為終點(diǎn)的邊之條數(shù)為入度deg-(v)。
?
?
路徑長(zhǎng)度：是指路徑上邊或弧的數(shù)目。
回路：若路徑的第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，則這條路徑是一條回路。
簡(jiǎn)單路徑：若路徑中頂點(diǎn)沒(méi)有重復(fù)出現(xiàn)，則稱(chēng)這條路徑為簡(jiǎn)單路徑。
連通圖：在無(wú)向圖中，如果從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱(chēng)vi和vj連通。如果圖中任意兩個(gè)頂點(diǎn)之間都連通，則稱(chēng)該圖為連通圖，否則，將其中的極大連通子圖稱(chēng)為連通分量。在有向圖中，如果對(duì)于每一對(duì)頂點(diǎn)vi和vj，從vi到vj和從vj到vi都有路徑，則稱(chēng)該圖為強(qiáng)連通圖；否則，將其中的極大連通子圖稱(chēng)為強(qiáng)連通分量。
歐拉通路(回路)：通過(guò)圖G的每條邊一次且僅一次，而且走遍每個(gè)結(jié)點(diǎn)的通路(回路)，就是歐拉通路(回路)。
?
歐拉圖：存在歐拉回路的圖就是歐拉圖。歐拉回路要求邊不能重復(fù)，結(jié)點(diǎn)可以重復(fù)。筆不離開(kāi)紙，不重復(fù)地走完所有的邊且走過(guò)所有結(jié)點(diǎn)，就是所謂的一筆畫(huà)。
哈密爾頓軌：含有圖中所有頂點(diǎn)的軌稱(chēng)作哈密爾頓軌。
?
哈密爾頓環(huán)：閉合的哈密爾頓軌稱(chēng)作哈密爾頓環(huán)。
?
哈密爾頓圖：含有哈密爾頓環(huán)的圖稱(chēng)作哈密爾頓圖。即周游世界問(wèn)題。
?
?
三、圖與樹(shù)的關(guān)系
?
圖的生成樹(shù)：對(duì)于一個(gè)擁有n個(gè)頂點(diǎn)的無(wú)向連通圖，它的邊數(shù)一定多余n-1條。若從中選擇n-1條邊，使得無(wú)向圖仍然連通，則由n個(gè)頂點(diǎn)及這 n-1條邊(弧)組成的圖被稱(chēng)為原無(wú)向圖的生成樹(shù)。顯示了一個(gè)無(wú)向連通圖的生成樹(shù)，雙線(xiàn)圈表示的頂點(diǎn)為生成樹(shù)的根結(jié)點(diǎn)。
?
森林：對(duì)于一個(gè)圖G，可以將其所有邊和頂點(diǎn)劃分成若干個(gè)樹(shù)，則稱(chēng)此圖為一個(gè)森林。(自己寫(xiě)的...)?
最小生成樹(shù)：在一個(gè)圖中，每條邊或弧可以擁有一個(gè)與之相關(guān)的數(shù)值，我們將它稱(chēng)為權(quán)。這些權(quán)可以具有一定的含義，比如，表示一個(gè)頂點(diǎn)到達(dá)另一個(gè)頂點(diǎn)的距離、所花費(fèi)的時(shí)間、線(xiàn)路的造價(jià)等等。這種帶權(quán)的圖通常被稱(chēng)作網(wǎng)。通常我們將權(quán)值總和最小的生成樹(shù)稱(chēng)為最小生成樹(shù)。
?
注：圖或網(wǎng)的生成樹(shù)不是唯一的，從不同的頂點(diǎn)出發(fā)可以生成不同的生成樹(shù)，但n個(gè)結(jié)點(diǎn)的生成樹(shù)一定有n-1條邊
?
例：若一個(gè)具有n個(gè)結(jié)點(diǎn)、k條邊的非聯(lián)通無(wú)向圖是一個(gè)森林(n>k)，則該森林中必有 n
-k 棵樹(shù).
?
??? 原因是假設(shè)有s棵樹(shù)，則每棵樹(shù)的邊和頂點(diǎn)對(duì)應(yīng)關(guān)系分別是ki=ni-1
??? 所以 k=k1+k2+...+ks=(n1-1
)+(n2-1)+...+(ns-1)=n-s
??? 所以 s = n-k
?
?
三、圖的簡(jiǎn)單判斷
?
?
(b)是非簡(jiǎn)單圖，(a)是完全圖，(a)和(b)都是哈密爾頓圖，其中(a)又是歐拉圖，(d)是樹(shù)。
?
?
?
***************************************************************************************************
?
?
?