Zi 字媒體

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

2021/12/25

newaurorapixnetnetblog

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

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. 任意兩點中，只有一條相連的路徑且無法循環(如下圖)。

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)

# 執行結果