樹(一)結構與關系概念


一、樹定義 一個數據





  • -A.B.C……J都表示一個結點(結點由一個數據元素和若幹個指向其子樹的分支)

  • -樹:n(n>=0)個結點的有限集,n=0稱為空樹

  • -n>0為非空樹:隻有一個根的結點,即A,n>1時,其餘結點可分為m個互不相交的有限集(本身也為一棵樹)稱根的子樹



T1 T2 本身為樹,也稱根的子樹




二、樹定義註意點


n>0時根結點是唯一的!,數據結構中的樹隻有一個根結點

m為m棵子樹,m>0時,子樹的個數是無限制但它們一定互不相交(根下均子樹)


錯誤演示




三、結點間輩分關系





  • -B是A的孩子

  • -A是B的雙親(父母同體)

  • -B與C是兄弟

  • -H的祖先是D.B.A





四、結點的層次





  • -從根開始定義,根為第一層,根的孩子為第二層





五、度與深度(高度)的區別


度的結構圖深度(高度)結構圖


1. 度:該結點擁有的子樹數(A的度:2,B:1,D:3,C:2,E:1)

- 樹的度是結點裡度最大的那個即樹的度為3

- 終端結點(葉結點):度為0的結點

- 非終端結點(分支結點):度不為0的結點

2. 深度(高度):樹中結點的最大層次稱為樹的深度

- 當前樹的深度為4(有4層)


六、有序樹、無序樹、森林


1. 有序樹:樹中結點的各子樹看成從左往右是有次序的,不能互換

2. 無序樹:反之

3. 森林:是m(m>=0)棵互不相交的樹的集合,對樹中每個結點而言,其子樹即為森林


七、線性結構與樹結構區別


1.線性結構(一對一)

- 第一個數據元素:無前驅

- 最後一個數據元素:無後繼

- 中間元素:一個前驅,一個後繼

2. 樹結構(一對多)

- 根結點:無雙親

- 葉結點:無孩子,可以多個

- 中間結點:一個雙親,多個孩子

0 個評論

要回覆文章請先登錄註冊