使用該工具。

對稱矩陣中的元素關於主對角線對稱，因此，讓每一對對稱元素

aij

和

a激(i≠j)分配一個

儲存空間，則

n2

個元素壓縮儲存到

n(n+1)\/2

個儲存空間，能節約近一半的儲存空間。假設

按“行優先順序”儲存下三角形(包括對角線)中的元素。設用一維陣列(向量)sa[0…n(n+1)\/2]存

儲

n

階對稱矩陣，如圖所示。為了便於訪問，必須找出矩陣

a

中的元素的下標值（i,j）和向

量

sa[k]的下標值

k

之間的對應關係。

樹型結構是一類非常重要的非線性結構。樹型結構:

分支關係

一對多

層次結構

本章將詳細討論樹和二叉樹資料結構，主要介紹樹和二叉樹的概念、術語，二叉樹的遍

歷演算法。樹和二叉樹的各種存結構以及建立在各種儲存結構上的操作及應用等。

1.樹的定義

樹(tree)是

n(n≧0)個結點的有限集合

t，若

n=0

時稱為空樹，否則：

1

有且只有一個特殊的稱為樹的根(root)結點；

2

若

n＞1

時，其餘的結點被分為

m(m＞0)個互不相交的子集

t1,

t2,

t3…tm，其中每個

子集本身又是一棵樹，稱其為根的子樹。這是樹的遞迴定義，即用樹來定義樹，而只有一個

結點的樹必定僅由根組成，如圖所示。

2.樹的基本術語

(1)

結點(node)：一個資料元素及其若干指向其子樹的分支。

(2)

結點的度(degree)

、樹的度：結點所擁有的子樹的棵數稱為結點的度。樹中結點度的最

大值稱為樹的度。

圖(b)中結點

a

的度是

3

，結點

b

的度是

2

，結點

m

的度是

0，樹的度是

3

(3)孩子結點、雙親結點、兄弟結點

一個結點的子樹的根稱為該結點的孩子結點(child)或子結點；相應地，該結點是其孩子

結點的雙親結點(parent)或父結點。

如圖

b

中結點

b

、c、d

是結點

a

的子結點，而結點

a

是結點

b

、c、d

的父結點；

結點

e

、f

是結點

b

的子結點，結點

b

是結點

e

、f

的父結點。

同一雙親結點的所有子結點互稱為兄弟結點。

如圖

b

中結點

b

、c、d

是兄弟結點；

結點

e

、f

是兄弟結點。

(4)

層次、堂兄弟結點

規定樹中根結點的層次為

1，其餘結點的層次等於其雙親結點的層次加

1。

若某結點在第

l(l≧1)層，則其子結點在第

l+1

層。

雙親結點在同一層上的所有結點互稱為堂兄弟結點。