樹的基本概念(定義、基本術語、性質)

樹的基本概念

• • 樹的定義
  • 樹的特點
  • 基本術語
  • 樹的性質

樹的定義

樹是n（n >=0）個節點的有限集。n = 0時，為空樹。

任意一棵非空樹應滿足：

①、有且僅有一個特定的成為根的結點。

②、當n>1時，其餘結點可分為m（m>0）個互不相交的有限集，其中每個集合本身又是一棵樹，并成為根的子樹。

樹的特點

1、樹的根結點沒有前驅，除根結點外所有的結點有且隻有一個前驅。

2、樹中所有結點可以有零個或多個後繼。

樹時一種遞歸的資料結構，是邏輯結構，也是分層結構。

n個結點的樹中有n-1條邊。

基本術語

看結點Q：從A到Q的唯一路徑上任意節點，成為Q的祖先。

E是Q的祖先，Q是E的子孫，J是Q的雙親，P和Q是兄弟

結點的度：一個結點的孩子的個數就是結點的度

樹的度：樹中結點最大的度稱為樹的度

分支結點：度大于0的結點稱分支節點（又稱非終端結點）

葉子結點：度為0的結點稱葉子結點（又稱終端結點）

結點的層次：從樹根開始定義，根節點為第一層，它的子節點為第二層，以此類推。

結點的深度：從根節點開始自定向下逐層累加。

結點的高度：從葉節點開始自底向上逐層累加。

樹的高度（或深度）：書中結點的最大層數。

有序樹：樹中結點的各子樹從左到右是有次序的，不能互換

無序樹：樹中結點的各子樹沒有次序，可以互換

路徑：兩結點之間所經過的結點序列構成路徑

路徑長度：是路徑上所經過的邊的個數

森林：m（m>=0）棵互不相交樹的集合。

樹的性質

1、樹中的結點數 = 所有結點的度數 （邊數）+ 1；

2、度為m的樹中第i層上最多有 mi-1 個結點；

m叉樹第i層至多有mi-1 個結點；

3、度為m的樹至少有一個結點的度 = m，至少有m + 1個結點

m叉樹允許所有結點的度<m，可以是空樹

4、高度為h的m叉樹至多有（mh - 1 ）/（m - 1）個結點

高度為h的m叉樹至少有n個結點

高度為h，度為m的 樹至少 h+m-1個結點

5、具有n個結點的m叉樹的最小高度為 logm(n(m-1)+1)