樹與圖形

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

樹—定義

帶有節點的樹狀圖。

以節點為基礎的資料結構
每個節點可有連到多個節點的連結。

樹—術語

帶有節點的樹狀圖。根節點以黃色標示。

樹—術語

帶有節點的樹狀圖。根節點以黃色標示。一個父節點以橘色標示。

樹—術語

帶有節點的樹狀圖。根節點以黃色標示。一個父節點以橘色標示，其子節點以綠色標示。

樹—術語

帶有節點的樹狀圖。

樹—術語

帶有不同層級的節點之樹狀圖。

樹—二元樹

二元樹的圖示。

每個節點可能有：
- 0 個子節點
- 1 個子節點
- 2 個子節點

樹—二元樹實作

class TreeNode:

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

帶有節點的樹狀圖。

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)

樹—實際應用

儲存階層關係
- 電腦的檔案系統
- HTML 文件結構
西洋棋：對手可能走法
搜尋與排序演算法

圖形（Graphs）

帶有節點的圖形。

由以下組成：
- 節點／頂點
- 連結／邊
樹是圖的一種

圖形—種類

有向圖：
- 具有特定方向

有向圖示意圖。

圖形—種類

無向圖：
- 邊沒有方向
- 關係是互相的

無向圖示意圖。

圖形—種類

加權圖：
- 邊帶有數值權重
- 可為有向或無向

無向圖示意圖，包含城市名稱與其間距離。

圖與樹的比較

樹

不能有環
所有節點都須相連

帶有節點的樹狀圖。

圖

可以有環
可能有未相連的節點

帶有節點的圖形。

圖與樹的比較

樹

不能有環
所有節點都須相連

帶有節點的樹狀圖。

圖

可以有環
可能有未相連的節點

帶有節點的圖形。其中一個節點未與其他節點相連。

圖形—實務應用案例

社群網路中的使用者關係
- 好友
- 追蹤
- 按讚
- 等等
地點與距離
- 路徑最佳化
圖形資料庫
搜尋與排序演算法

圖形—實作

class Graph:
  def__init(self):
    self.vertices = {}

  def add_vertex(self, vertex):
    self.vertices[vertex] = []

  def add_edge(self, source, target):    
    self.vertices[source].append(target)

有向圖示意圖。

my_graph = Graph()
my_graph.add_vertex('David')
my_graph.add_vertex('Miriam')
my_graph.add_vertex('Martin')

my_graph.add_edge('David', 'Miriam')
my_graph.add_edge('David', 'Martin')
my_graph.add_edge('Miriam', 'Martin')

print(my_graph.vertices)

{
  'David' : ['Miriam','Martin'],
  'Miriam' : ['Martin'],
  'Martin' : []
}

一起來練習吧！

Data Structures and Algorithms in Python