ADUNIT000

資料結構 - Tree 的介紹(使用Python)

Tree(樹)是一種相當常見的資料結構,用途也相當廣泛,Tree(樹)同時也表示了資料的階層關係,首先認識一下樹的幾個比較重要的名詞和特徵

Tree 結構示意圖(圖一)

Tree_示意圖

Tree 相關名詞解釋

1. Node(節點):每一個被Tree所連接到的點,都可被稱作這棵樹的Node(節點)。

2. Root(根節點):每一個Tree最初(或最上層)的節點,每個Tree都只有一個Root(根節點),如圖一節點A。

3. Parent Node(父節點):除了Root以外,每一個Node都會有一個Parent(父節點),如圖一節點B是節點D的Parent Node。

4. Child Node(子節點):每一個Parent都會有Child(子節點),如圖一節點L是節點E的Child Node。

5. Leaf Node(葉):每一個沒有子節點的節點都是Leaf Node,如圖一節點G、H、J、K、L、M都是Leaf Node。

6. Depth(深度):指Tree總共有幾個階層(又或稱Height、Level),依圖一的範例,則Tree的深度為 4。

 

Tree 的特徵

1. 任意兩點中,只有一條相連的路徑且無法循環(如下圖)。

tree_nocycle

2. 每一個點只會有一個父節點。

3. 每個Tree都會有一個Root,但是Root沒有父節點。

4. 子樹之間沒有交集。

 

下面附上Tree的範例程式(使用Python撰寫)

class treeNode:
     def __init__(self, val):

         # 初始化節點
         self.val = val
         self.left = None
         self.right = None

    def insertLeft(self, val):
         # 如果要新增左邊節點,先檢查是否已存在,若左節點不存在則放入左節點
         if self.left == None:
             self.left = treeNode(val)

         # 如果左節點已經存在,則放入左節點的下一層左節點,這邊用遞迴的方式進行搜尋,直到可以讓入左節點為止
         else:
             self.left.insertLeft(val)
    
     def insertRight(self, val):

         # 新增右邊節點的方式則和新增左節點的方式相同
         if self.right == None:
             self.right = treeNode(val)
         else:
             self.right.insertRight(val)

# 執行方式
sampleTree = treeNode(5)
sampleTree.insertRight(7)
sampleTree.insertRight(8)
sampleTree.insertLeft(3)
sampleTree.insertLeft(2)
sampleTree.right.insertLeft(6)
sampleTree.left.insertRight(4)

# 執行結果

image

 

   如果覺得對你有幫助的話. 請幫小弟按個讚吧~

 

資料結構相關文章:

      氣泡排序法 - 使用Python (Bubble Sort)

      插入排序法 - 使用Python(Insertion Sort)

      合併排序法 - 使用Python(Merge sort)

 

創作者介紹
創作者 newaurora 的頭像
newaurora

史丹利愛碎念

newaurora 發表在 痞客邦 留言(1) 人氣()


留言列表 (1)

發表留言
  • 光
  • 請問一下,一般的 資料夾、檔案 結構,適合用 tree 來做嗎?