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