Zi 字媒體

資料結構 - 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) # 執行結果      如果覺得對你有幫助的話. 請幫小弟按個讚吧～   資料結構相關文章：       氣泡排序法 - 使用Python (Bubble Sort)       插入排序法 - 使用Python(Insertion Sort)       合併排序法 - 使用Python(Merge sort)