第七章樹
樹形結構是一類十分重要的非線性結構，它可以很好地描述客觀世界中廣泛存在的具有分支關係或層次特性的物件，因此在計算機領域裡有著廣泛應用，如作業系統中的檔案管理、編譯程式中的語法結構和資料庫系統中資訊組織形式等。在現實生活中，同樣存在很多可用樹形結構描述的物件，如行政組織機構和族譜等。本章將詳細討論這種資料結構，特別是二叉樹結構。
樹是由n（n＞0）個結點組成的有限集合（記為t）。在一棵樹中滿足如下兩個條件：
1．有且僅有乙個特定的結點，稱為根結點；
2．其餘的結點可分為m（m≥0）個互不相交的有限集合t0，t1，…，tm-1。其中每個集合又都是一棵樹，稱這些集合為根結點的子樹。
1．樹的定義是遞迴的，在樹的定義中又用到樹的概念。它刻化了樹的固有特性，即一棵樹由若干棵子樹構成，而子樹又由更小的若干棵子樹構成，… 。
2．一棵樹至少有乙個結點，因為在定義中，結點數n大於0；（有的教材n可以為0，當n＝0時，稱t為空樹）。
3．樹是一種非線性資料結構，具有以下特點：它的的每一結點都可以有不止乙個直接後繼；除根外的所有結點，都有且只有乙個直接前趨；這些資料結點按分支關係組織起來，清晰地反映了資料元素之間的層次關係。可以看出，資料元素之間存在的關係是一對多，或者多對一的關係，與前面討論的線性表、棧隊和陣列線性結構有很大差別。
圖7.1.1是一棵有14個結點的樹，其中a是根結點，其餘結點分成三個互不相交的子集；t1＝｛b，e，f，g，l｝，t2＝｛c，h，i｝，t3＝｛d，j，k，m，n｝；t1、t2和t3都是根a的子樹，且本身也是一棵樹。
對於子樹t1，其根為b，其餘結點分為三個互不相交的子集；t11＝｛e｝，t12＝｛f，l｝，t13＝｛g｝，t11、t12和t13都是b的子樹。而t11中的e是根，其餘結點為空，沒有子樹；t12的根是e，其餘結點成為唯一的子集｛l｝；t13中的g是根，沒有子樹。
從圖中還可以看到，樹根結點a沒有直接前趨結點，其它13個結點都有乙個唯一直接前趨結點，如b，c和d的直接前趨結點為a；e，f和g的直接前趨結點為b等等。每一結點可以有多個直接後繼，如a的直接後繼有b，c和d三個結點，d的直接後繼有j和k兩個結點，而e、l、g、h、i、j、m和n沒有直接後繼結點。
圖中清晰地反映了資料元素之間的層次關係，a在第一層，b、c、d同處在a的下一層。
圖7.1.1 樹的例項
樹的許多術語借用了家族樹中的一些慣用名詞。
1．結點的度與樹的度由樹的定義可知，樹的結點包含乙個資料元素及若干指向其子樹的分支。某個結點的子樹的個數稱為該結點的度。樹中各結點之度的最大值稱為樹的度，通常稱度為m的樹為m次樹。
例如，在圖7.1.1所表示的樹中，a和b的度為3；c、d和k的度為2；f的度為1；其它結點的度為零。
因結點的最大度數為3，所以樹的度為3，我們稱該樹為3次樹。
2．分支結點與葉結點度不為零的結點稱為非終端結點，又叫分支結點。度為零的結點稱為葉結點或終端結點。在分支結點中，每個結點的分支數就是該結點的度數。
如對於度為1的結點，其分支數為1，被稱之為單分支結點；對於度為2的結點，其分支數為2，被稱之為雙分支結點，其餘類推。如在圖7.1.
1所表示的樹中，e、g、h、i、j、l，m和n都是葉子結點，a、b、c、d、f和k都是分支結點，其中f為單分支結點，c、d和k為雙分支結點，a和b為三分支結點。
3．路徑與路徑長度對於任意兩個結點ki和kj，若樹中存在乙個結點序列ki，ki1，ki2，… ，kin，kj，使得序列中除ki外的任一結點都是其在序列中的前乙個結點的後繼，則稱該結點序列為由ki到kj的一條路徑，用路徑所通過的結點序列（ki，ki1，ki2，… ，kj）表示這條路徑。路徑的長度等於路徑所通過的結點數目減1（即路徑上分支數目）。可見路徑就是從ki出發「自上而下」到達kj所通過的樹中結點序列。
顯然，從樹的根結點到樹中其餘結點均存在一條路徑。例如在圖7.1.
1所示的樹中，結點a到l有一條路徑（a，b，f，l），長度為3；d到m有一條路徑（d，k，m），長度為2。結點b到d之間不存在任何路徑。
4．孩子結點、雙親結點和兄弟結點為了形象描繪樹的結構中結點的關係，我們常借用家族關係的稱呼來作為樹的描述性術語。在一棵樹中，每個結點的各子樹的根，或者說每個結點的後繼，被稱作該結點的孩子（或兒子，或子女），相應地，該結點被稱作孩子結點的雙親（或父親，或父母）。具有同一雙親的孩子互為兄弟。
進一步推廣這些關係，可以把每個結點的所有子樹中的結點被稱作該結點的子孫，從樹根結點到達該結點的路徑上經過的所有結點被稱作該結點的祖先。如在圖7.1.
1所表示的樹中，e、f、g是b的三棵子樹的根，則e、f、g就是b的孩子，而b為e、f，g的雙親；e、f，g互為兄弟；d結點的子孫為j、k、m、n結點；m結點的祖先為k、d、a結點。
由孩子結點和雙親結點的定義可知：在一棵樹中，根結點沒有雙親結點，葉子結點沒有孩子結點，其餘結點既有雙親結點也有孩子結點。
5．結點的層數和樹的深度樹既是一種遞迴結構，也是一種層次結構，樹中的每個結點都處在一定的層數上。結點的層數從樹根開始定義，根結點為第一層（有的教材從第0層開始），它的孩子結點為第二層，以此類推，乙個結點所在的層次為其父結點所在的層次加1。樹中結點的最大層數稱為樹的深度（或高度）。
如在圖7.1.1所表示的樹中，a結點處於第一層；b、c、d在第二層；e、f、g、h、i、j、k在第三層；l、m、n第四層。
樹了中結點的最大層數為4，所以該樹的深度為4。
6．有序樹和無序樹若樹中各結點的子樹是按照一定的次序從左向右安排的，相對次序不能隨意變換的，則稱之為有序樹，否則稱之為無序樹。如對於圖7.1.
2中的兩棵樹，若看作為無序樹，它們表示同一棵樹；按照有序樹的概念，它們表示兩棵不同的樹，因為根結點a的兩棵子樹的次序不同，乙個是b子樹在前，c子樹在後，而另乙個則相反。
圖7.1. 2 兩棵不同的有序樹
7．森林 n（n＞0）個互不相交的樹的集合。森林的概念與樹的概念十分相近，因為只要把樹的根結點刪掉就成了森林。如在圖7.
1.1所表示的樹中，若刪除根結點a，就可得到乙個由b、c和d三棵樹組成的森林。反之，只要給n棵獨立的樹加上乙個結點，並把這n棵樹作為該結點的子樹，則森林就變成了樹。
樹的邏輯表示方法有多種，但不管採用哪種表示方法，都應該能夠正確表達出樹中資料元素之間的層次關係。下面是幾種常見的邏輯表示方法。
用乙個圓圈表示乙個結點，圓圈內的符號代表該結點的資料資訊，結點之間的關係通過連線表示。雖然每條連線上都不帶有箭頭（即方向），但它仍然是有向的，其方向隱含著從上向下，即連線的上方結點是下方結點的前驅，下方結點是上方結點的後繼。它的直觀形象是一棵倒置的樹（樹根在上。
樹葉在下），如圖7.1.1所示。
這種表示方法的特點是形象、直觀。因此在資料結構的書中都採用這種方法。
用有序對＜d，r＞表示一棵樹，其中d為樹的所有結點構成的集合，r為d上的乙個二元關係（即d中結點組成的二元組的集合）。r中的每個二元組（關係）表示d中二個結點之間的關係（對應樹形表示法的一條連線），即二元組中第乙個結點是第二個結點的前驅，第二個結點是第乙個結點的後繼。如圖7.
1.1所示的樹，若用二元組表示，則d和r分別為：
d＝｛a，b，c，d，e，f，g，h，i，j，k，l，m，n｝
r＝｛〈a，b〉，〈a，c〉，〈a，d〉，〈b，e〉，〈b，f〉，〈b，g〉，〈f，l〉，〈c，h〉，〈c，i〉，〈d，j〉，〈d，k〉，〈k，m〉，〈k，n〉｝
這種表示法可以對樹進行形式化的描述，但不如樹形表示法一目了然。
每棵樹對應乙個圓形，圓內包含根結點和子樹的圓形，同乙個根結點下的各子樹對應的圓形是不能相交的。這種方法表示的樹中，結點之間的關係是通過圓形的包含來表示的。以圖7.
1.1所示的樹為例，其文氏圖表示如圖7.1.
3所示。
每棵樹的根對應著一條形，子樹的根對應著乙個較短的條形，且樹根在上，子樹的根在下，同乙個根下的各子樹的根對應的條形長度是一樣的。這種方法表示的樹中，結點之間的關係是通過條形的長度和位置表示的，以圖7.1.
1所示的樹為例，其凹入表示如圖7.1.4所示。
圖7.1.3 樹的文氏圖表示例項圖7.1.4 樹的凹入表示例項
每棵樹對應乙個由根作為名字的表，表名放在表的左邊，表是在乙個括號裡的各子樹對應的表組成的，之間用逗號分開。這種方法表示的樹中，結點之間的關係是通過括號的巢狀表示的。如圖7.
1.1所示的樹，用巢狀括號表示如下：
a（b（e，f（l），g），c（h，i），d（j，k（m，n）））
巢狀括號表示是樹的一種樹的線性表示，它可以用乙個字串來給出，在實現樹的儲存結構中，可作為輸入資料。
證明：根據樹的定義，在一棵樹中，除樹根結點外，每個結點有且僅有乙個前驅結點，也就是說，每個結點與指向它的乙個分支一一對應，所以除樹根之外的結點數等於所有結點的分支數（度數），從而可得樹中的結點數等於所有結點的度數加1。
用數學歸納法證明：
對於第一層，因為樹中的第一層上只有乙個結點，即整個樹的根結點，而由i＝1代入mi-1，得mi-1＝m1-1＝m0＝1，也同樣得到只有乙個結點，顯然結論成立。
假設對於第(i－1)層(i＞1)命題成立，即度為m的樹中第(i－1)層上至多有mi-2個結點，則根據樹的度的定義，度為m的樹中每個結點至多有m個孩子，所以第i層上的結點數至多為第(i－1)層上結點數的m倍，即至多為mi-2×m＝mi-1個，這與命題相同，故命題成立。
證明：由性質2可知，第i層上最多結點數為mi-1（i＝1，2，…，h），顯然當深度為h的m叉樹(即度為m的樹)上每一層都達到最多結點數時，整個m叉樹具有最多結點數，因此有：
整個樹的最多結點數＝每一層最多結點數之和
＝m0＋m1＋m2＋…＋mh-1
＝當一棵m叉樹上的結點數等於（mh-1－1)/(m－1）時，則稱該樹為滿m叉樹。例如，對於一棵深度為5的滿二叉樹，則結點數為25-1，即31；對於一棵深度為5的滿三叉樹，則結點數為（35-1)/(3-1），即121。
資料結構第2章
第2章 線性表 1.理解線性表的定義和邏輯結構特性 填空題 1 線性表中結點的集合是有限的，結點間的關係是一對一的。2 線性表的儲存方式分為順序儲存和鏈式儲存 判斷題 1 線性表的每個結點只能是乙個簡單型別，而鍊錶每個結點可以是乙個複雜型別。錯，混淆了邏輯結構與物理結構，鍊錶也是線性表！且即使是順序...
資料結構第2章答案
一 填空題 01 當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度訪問線性表中的元素時，應採用順序儲存結構。02 線性表l a1,a2,an 用陣列表示，假定刪除表中任一元素的概率相同，則刪除乙個元素平均需要移動元素的個數是 n 1 2。03 在有n個元素的順序表中插入乙個新...
資料結構第1章概論
二 單項選擇題 1.非線性結構是資料元素之間存在一種 a 一對多關係 b 多對多關係 c 多對一關係 d 一對一關係 2.資料結構中，與所使用的計算機無關的是資料的結構 a 儲存 b 物理 c 邏輯d 物理和儲存 3.演算法分析的目的是 a 找出資料結構的合理性 b 研究演算法中的輸入和輸出的關係 ...