1.什么是樹

樹是數(shù)據(jù)結構中的一種，其屬于非線性數(shù)據(jù)結構結構的一種，我們前文所提到的數(shù)據(jù)結構多數(shù)都是線性的，這也是較為簡單的數(shù)據(jù)結構，而接下來的樹與圖均屬于非線性數(shù)據(jù)結構，也是概念極多的一類。

樹是由結點或頂點和邊組成的(可能是非線性的)且不存在著任何環(huán)的一種數(shù)據(jù)結構。沒有結點的樹稱為空(null或empty)樹。一棵非空的樹包括一個根結點，還(很可能)有多個附加結點，所有結點構成一個多級分層結構。

樹的定義：n個節(jié)點組成的有限集合。n=0，空樹；n>0,1個根節(jié)點，m個互不相交的有限集，每個子集為根的子樹。

如圖所示，圖為一顆樹：

2.樹的基本術語

l  節(jié)點的度：樹中某個節(jié)點的子樹的個數(shù)。

l  樹的度：樹中各節(jié)點的度的最大值。

l  分支節(jié)點：度不為零的節(jié)點。

l  葉子節(jié)點：度為零的節(jié)點。

l  路徑：i->j；路徑長度：路徑經(jīng)過節(jié)點數(shù)目減1。

l  孩子節(jié)點：某節(jié)點的后繼節(jié)點；雙親節(jié)點：該節(jié)點為其孩子節(jié)點的雙親節(jié)點（父母節(jié)點）；兄弟節(jié)點：同一雙親的孩子節(jié)點；子孫節(jié)點：某節(jié)點所有子樹中的節(jié)點；祖先節(jié)點：從樹節(jié)點到該節(jié)點的路徑上的節(jié)點。

l  節(jié)點的層次：根節(jié)點為第一層（以此類推）；樹的高度：樹中節(jié)點的最大層次。

l  有序樹：樹中節(jié)點子樹按次序從左向右安排，次序不能改變；無序樹：與之相反

l  森林：互不相交的樹的集合。

3.樹的性值

l  樹的節(jié)點樹為所有節(jié)點度數(shù)加1（加根節(jié)點）。

l  度為m的樹中第i層最多有m^(i-1)個節(jié)點。

l  高度為h的m次樹至多(m^h-1)/(m-1)個節(jié)點。

l  具有n個節(jié)點的m次樹的最小高度為logm( n(m-1) + 1 )  向上取整。

4. 課后問題：

請利用樹的基本術語求出圖示中的參數(shù)內容，如這顆樹結點的度，樹的度等，也請自己額外找一些圖片求這些術語表示的內容，這對熟悉樹的基本概念十分有幫助。