iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 11
0

接續昨天的樹。二元樹 (Binary Tree) 的特點就是每個節點最多有兩個兒子,或者是說每個節點最多有兩棵子樹。

二元樹中還有兩種特殊的種類:

  • 滿二元樹
  • 完全二元樹

滿二元樹

若二元樹中的每個節點都有兩個兒子(子節點),就稱滿二元樹。或者說滿二元樹的所有葉節點都有同樣的深度。較嚴格的定義為 一棵深度為 h 且有 https://chart.googleapis.com/chart?cht=tx&chl=2%5Eh%20-1 個節點的二元樹
https://ithelp.ithome.com.tw/upload/images/20181026/20111557gGTvu5MaCY.jpg

完全二元樹

若二元樹的高度(深度)為 h,除第 h 層外,其他各層(1 ~ h-1)的節點數都達到最大個樹,而第 h 層從右向左連續缺幾個節點,則這個二元樹就稱 完全二元樹
https://ithelp.ithome.com.tw/upload/images/20181026/20111557pTpj1ywA01.jpg
https://ithelp.ithome.com.tw/upload/images/20181026/20111557NH0EwtEQbD.jpg
https://ithelp.ithome.com.tw/upload/images/20181026/20111557oOKnTfDaPD.jpg
其實完全二元樹很類似這樣的形狀。
https://ithelp.ithome.com.tw/upload/images/20181026/20111557UMhO6rjLBH.jpg

在瞭解了完全二元樹的定義之後,那要怎麼把完全二元樹的資料儲存起來?答案是一個一維陣列就可以搞定。

首先將完全二元樹進行編號,從上到下,從左到右。
https://ithelp.ithome.com.tw/upload/images/20181026/20111557uia6DGHnmk.jpg

[1, 2, 3, 4, 5, 6]

如果仔細觀察就可以發現編號和一維陣列儲存的規律。

  • 父節點編號為 k
  • 左兒子的編號為 2*k
  • 右兒子的編號為 2*k+1
  • 如果兒子編號為 x ,父節點的編號就為 x/2 取整數的商。
  • 如果有 N 個節點,則完全二元樹的高度(深度)為https://chart.googleapis.com/chart?cht=tx&chl=log2(N)

上一篇
[資料結構] 樹 (Tree)
下一篇
[資料結構] 二元樹走訪 (Binary Tree Traversal)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言