三、數組
線性表（包括棧和隊列）都是線性結構，結構中的每個元素只是無結構的數據元素。我們對線性表作進一步的推廣，使結構中的元素本身也可以是具有某種結構（如向量）的數據，從而引出了數組這一種新的數據結構。
（1）數組的定義和運算
類似于線性表，一個二維數組（或稱矩陣）可以看成是由m個行向量所組成的向量，也可以看成是由n個列向量所組成的向量。
對于數組的運算，主要有檢索或存取數組中某個元素。
（2）數組的順序存儲結構
由于對數組一般不作插入或刪除運算，因此，一旦數組被建立，則結構中的元素個數和元素之間的關系就不再發生變動。對這種情況采用順序存儲結構表示數組是比較恰當的。
由于計算機存儲單元是一維的結構，而數組是多維的結構，因此就必須把多維結構映射為一維的結構，即把多維結構按一定次序排列成一維的。
四、樹型結構
線性表、棧和隊列等數據結構所表達和處理的數據以線性結構為組織形式。然而，在計算機科學和計算機應用的各個領域中，存在著大量需要用更復雜的邏輯結構加以表示的問題。因此必須研究更復雜的邏輯結構及相應的數據結構。樹形結構就是這些更復雜的結構中最重要的一類。
1.樹的基本概念
樹是一類重要的樹形結構，其定義如下:樹是n（n>0）個結點的有窮集合，滿足:
（1）有且僅有一個稱為根的結點;
（2）其余結點分為m（m≥0）個互不相交的非空集合，T 1 ，T 2 ，…，T m ，這些集合中的每一個都是一棵樹，稱為根的子樹。
在樹上，根結點沒有直接前趨。對樹上任一結點X來說，X是它的任一子樹的根結點惟一的直接前趨。為了討論方便，我們引入樹的若干習慣術語。樹上任一結點所擁有的子樹的數目稱為該結點的度。度為0的結點稱為葉子或終端結點。度大于0的結點稱為非終端結點或分支點。一棵樹中所有結點的度的最大值稱為該樹的度。若樹中結點A是結點B的直接前趨，則稱A為B的雙親或父結點，稱B為A的孩子（即“子女”）或子結點。易知任何結點A的孩子B也就是A的一棵子樹的根結點，父結點相同的結點互稱為兄弟。一棵樹上的任何結點（不包括根本身）稱為根的子孫。反之若B是A的子孫，則稱A是B的祖先，結點的層數（或深度）從根開始算起:根的層數為1，其余結點的層數為其雙親的層數加1。一棵樹中所有結點層數的最大值稱為該樹的高度或深度。
樹（及一切樹形結構）是一種“分支層次”結構。所謂“分支”是指樹中任一結點的子孫可以按它們所在的子樹的不同而劃分成不同的“分支”;所謂“層次”是指樹上所有結點可以按它們的層數劃分不同的“層次”。在實際應用中，樹中的一個結點可用來存儲實際問題中的一個數據元素，而結點間的邏輯關系（即父結點與子結點之間的鄰接關系）往往用來表示數據元素之間的某種重要的、必須加以表達的關系。
用圖示法表示任何樹形結構時，箭頭的方向總是從上到下，即從父結點指向子結點，因此，可以簡單地用連線代替箭頭。
2.樹的基本運算包括:
①求根ROOT（T），引用型運算，其結果是結點X在樹T的根結點。
②求雙親PARENT（T，X），引用型運算，其結果是結點X在樹T上的雙親結點;若X是樹T的根或X不在T上，則結果為一特殊標志。
③求孩子CHILD（T，X，i），引用型運算，其結果是樹T上的結點X的第i個孩子;若X不在T上或X沒有第i個孩子，則結果為一特殊標志。
④建樹CREATE（X，T 1 ，…，T k ）k≥1，加工型運算，其作用是建立一棵以X為根，以T 1 ，…，T k 為第1，…k棵子樹的樹。
⑤剪枝DELETE（T，X，i），加工型運算，其作用是刪除樹T上結點X的第i棵子樹;若T無第i棵子樹，則為空操作。
3.二叉樹
（1）二叉樹的基本概念
二叉樹是結點的有窮集合，它或者是空集，或者同時滿足下述兩個條件:（1）有且僅有一個稱為根的結點:
（2）其余結點分為兩個互不相交的集合T 1 、T 2 ，T 1 與T 2 都是二叉樹，并且T 1 與T 2 有順序關系（T 1 在T 2 之前），它們分別稱為根的左子樹和右子樹。
二叉樹是一類與樹不同的樹形結構。它們的區別是:第一，二叉樹可以是空集，這種二叉樹稱為空二叉樹。第二，二叉樹的任一結點都有兩棵子樹（當然，它們中的任何一個可以是空子樹），并且這兩棵子樹之間有次序關系，也就是說，它們的位置不能交換。相應地，二叉樹上任一結點左、右子樹的根分別稱為該結點的左孩子和右孩子。另外，二叉樹上任一結點的度定義為該結點的孩子數（即非空子樹數）。除這個幾個術語之外，樹的其它術語也適用于二叉樹。
特別值得注意的是，由于二叉樹上任一結點的子樹有左、右之分，因此即使一結點只有一棵非空子樹，仍須區別它是該結點的左子樹還是右子樹，這是與樹不同的。
（2）二叉樹的性質
在某些情況下，了解二叉樹的下列性質是有幫助的。
4.二叉樹的存儲結構
二叉樹通常有兩類存儲結構，順序存儲結構和鏈式存儲結構。
（1）二叉樹的鏈式存儲結構
二叉樹有不同的鏈式存儲結構，其中最常用的是二叉樹鏈表與三叉鏈表。
其中，data域稱為數據域，用于存儲二叉樹結點中的數據元素;lchild域稱為左孩子指針域，用于存放指向本結點左孩子的指針（這個指針及指針域有時簡稱為左指針）。類似地，rchild域稱為右孩子指針域，用于存放指向本結點右孩子的指針（簡稱右指針）。二叉鏈表中的所有存儲結點通過它們的左、右指針的鏈接而形成一個整體。此外，每個二叉鏈表還必須有一個指向根結點的指針，該指針稱為根指針。根指針具有標識二叉鏈表的作用，對二叉鏈表的訪問只能從根指針開始。值得注意的是，二叉鏈表中每個存儲結點的每個指針域必須有一個值，這個值或者是指向該結點的一個孩子的指針，或者是空指針NULL。
若二叉樹為空，則root=NULL。若某結點的某個孩子不存在，則相應的指針為空。具有n個結點的二叉樹中，一共有2n個指針域，其中只有n-1個用來指向結點的左右孩子，其余的n+1個指針域為NULL。
二叉樹的鏈式存儲結構操作方便，表達簡明（二叉樹的邏輯關系———結點間的父子關系———在二叉鏈表和三叉鏈表中被直接表達成對應存儲結點之間的指針），因而成為二叉樹最常用的存儲結構。然而在某些情況下，二叉樹的順序存儲結構也很有用。
（2）二叉樹的順序存儲結構
二叉樹的順序存儲結構由一個一維數組構成，二叉樹上的結點按某種次序分別存入該數組的各個單元。顯然，這里的關鍵在于結點的存儲次序，這種次序應能反映結點之間的邏輯關系（父子關系），否則二叉樹的基本運算就難以實現。
由二叉樹的性質5可知，若對任一完全二叉樹上的所有結點按層編號，則結點編號之間的數值關系可以準確地反映結點之間的邏輯關系。因此，對于任何完全二叉樹來說，可以采用“以編號為地址”的策略將結點存入作為順序存儲結構的一維數組。具體地說就是:將編號為i的結點存入一維數組的第i個單元。
在這一存儲結構中，由于一結點的存儲位置（即下標）也就是它的編號，故結點間的邏輯關系可通過它們下標間的數值關系確定。
5.二叉樹的遍歷
由于二叉樹的基本運算在鏈式存儲結構上的實現比較簡單，無需詳加討論。下面研究二叉樹的一種較為復雜的重要運算———遍歷及其在二叉鏈表上的實現。
遍歷一棵二叉樹就是按某種次序系統地“訪問”二叉樹上的所有結點，使每個結點恰好被“訪問”一次。所謂“訪問”一個結點，是指對該結點的數據域進行某種處理，處理的內容依具體問題而定，通常比較簡單。遍歷運算的關鍵在于訪問結點的“次序”，這種次序應保證二叉樹上的每個結點均被訪問一次且僅一次。
由定義可知，一棵二叉樹由三部分組成:根、左子樹和右子樹。因此對二叉樹的遍歷也可相應地分解成三項“子任務”:
①訪問根根點;
②遍歷左子樹（即依次訪問左子樹上的全部結點）;③遍歷右子樹（即依次訪問右子樹上的全部結點）。
因為左、右子樹都是二叉樹（可以是空二叉樹），對它們的遍歷可以按上述方法繼續分解，直到每棵子樹均為空二叉樹為止。由此可見，上述三項子任務之間的次序決定了遍歷的次序。若以D、L、R分別表示這三項子任務，則人有六種可能的次序:DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”，即子任務②在子任務③之前完成，這樣就只剩下前三種次序，按這三種次序進行的遍歷分別稱為先根遍歷（或前序遍歷）、中根（或中序）遍歷、后根（或后序）遍歷。三種遍歷方法的定義如下:
先根遍歷 若需遍歷的二叉樹為空，執行空操作;否則，依次執行下列操作:
①訪問根結點;
②先根遍歷左子樹;
③先根遍歷右子樹。
中根遍歷 若需遍歷的二叉樹為空，執行空操作，否則，依次執行下列操作:
①中根遍歷左子樹;②訪問根結點;③中根遍右子樹。
后根遍歷 若需遍歷的二叉樹為空，執行空操作，否則，依次執行下列操作:
①后根遍歷左子樹。②后根遍歷右子樹。③訪問根結點。
顯然，上述三種遍歷方法的區別在于執行子任務“訪問根結點”的“時機”不同;最先（最后、在中間）執行此子任務，則為先根（后根、中根）遍歷。
按某種遍歷方法遍歷一棵二叉樹，將得到該二叉樹上所有結點的訪問序列。
希望與更多計算機等級考試的網友交流，請進入計算機等級考試論壇
更多信息請訪問：考試吧計算機等級考試欄目
