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