昨天提到了資料結構，我想深入了解其中幾樣，雖然艱深難懂，但我相信十分重要，今天先從 Tree 開始。

Tree 的基本概念

我們先來了解一下基本名詞

• Node - 節點 : Tree是由節點組成，每一個節點包含一個或多個數據元素。節點是 Tree的基本結構，可以表示各種類型的數據。
• Root Node - 根節點 : Tree 的最上層稱為根節點，他沒有父節點是 Tree 的起始點。
• Leaf Node - 葉節點 : 沒有子節點稱為葉節點，位於 Tree 的末端。
• Parent and Child Nodes - 父節點和子節點 : 節點之間的關係由父節點與子節點定義。一個節點可以由多個子節點組成，但通常只會有一個父節點。
• Edge - 邊 : 邊是樹中連接節點的線段，表示節點之間的關係。
• Level - 層次 : 樹中每個節點都位於一個層次，表示節點距離根節點的深度。根節點為0，他的子節點為1，以此類推。
• Subtree - 子樹 : 一個 tree 的一部份也可以稱為 tree，這便是子樹。
• Height - 樹的高度 : 表示樹中從根節點到葉節點的最長路徑層數。他影響到樹的性能。

Binary Tree - 二叉樹

這是一種常見的樹狀結構，他由節點組成，每個節點最多有兩個子節點，分為左節點、右節點。

一棵有9個節點且深度為3的二元樹，其根節點的值為2，它既不平衡亦未經過排序 wiki

以下透過 Ruby，展示如何建立、遍歷二叉樹

class TreeNode
  attr_accessor :value, :left, :right

  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

# 前序遍歷
def preorder_traversal(node)
  return [] if node.nil?

  result = []
  result << node.value
  result += preorder_traversal(node.left)
  result += preorder_traversal(node.right)
  result
end

# 中序遍歷
def inorder_traversal(node)
  return [] if node.nil?

  result = []
  result += inorder_traversal(node.left)
  result << node.value
  result += inorder_traversal(node.right)
  result
end

# 後序遍歷
def postorder_traversal(node)
  return [] if node.nil?

  result = []
  result += postorder_traversal(node.left)
  result += postorder_traversal(node.right)
  result << node.value
  result
end

# 創建二叉樹
root = TreeNode.new(10)
root.left = TreeNode.new(5)
root.right = TreeNode.new(15)
root.left.left = TreeNode.new(3)
root.left.right = TreeNode.new(7)

# 執行遍歷
puts "前序遍歷结果：#{preorder_traversal(root).join(', ')}" # 10, 5, 3, 7, 15
puts "中序遍歷结果：#{inorder_traversal(root).join(', ')}" # 3, 5, 7, 10, 15
puts "后序遍歷结果：#{postorder_traversal(root).join(', ')}" # 3, 7, 5, 15, 10

以上示範了三種遍歷方式

1. Preorder Traversal 前序遍歷 : 用於複製二叉樹、打印表達式樹。
2. In-order Traversal 中序遍歷 : 適用於排序二叉樹、計算表達式樹。
3. Postorder Traversal 後序遍歷 : 適用於釋放二叉樹的內存、表達式樹後綴表達式。

我們來做個簡單的 leet code吧!
94. Binary Tree Inorder Traversal
透過題目就可以知道要使用 Inorder 的方式去做排序。

def inorder_traversal(root)
    return [] if root.nil?

    result = []
    result += inorder_traversal(root.left)
    result << root.val
    result += inorder_traversal(root.right)
    result
end

簡單的 Tree code 介紹，讓我們一起進步吧!