> For the complete documentation index, see [llms.txt](https://lochiwei.gitbook.io/ios/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lochiwei.gitbook.io/ios/data-structures/graph/tree.md).

# Tree

[Data Structures](/ios/data-structures.md) ⟩ [Graph](/ios/data-structures/graph.md) ⟩ Tree

{% tabs %}
{% tab title="🔸 定義" %}
{% hint style="success" %}

* <mark style="color:purple;">**tree**</mark>: an (**undirected**) <mark style="color:purple;">**connected graph**</mark> in that <mark style="color:yellow;">**any pair of vertices**</mark> has a <mark style="color:red;">**unique route**</mark> between them.
* <mark style="color:purple;">**leaf**</mark>: vertex of [<mark style="color:red;">**degree 1**</mark>](/ios/data-structures/graph.md) (<mark style="color:orange;">**has only one edge**</mark>) in a tree.
  {% endhint %}
  {% endtab %}

{% tab title="⭐️ 重點" %}
{% hint style="success" %}
Let $$\mathbb{G}$$ be a [<mark style="color:purple;">**connected graph**</mark>](/ios/data-structures/graph.md) with $$n$$ <mark style="color:yellow;">**vertices**</mark>, then\
$$\mathbb{G}$$ is a <mark style="color:purple;">**tree**</mark> $$\Longleftrightarrow$$ $$\mathbb{G}$$ has exactly $$n-1$$ <mark style="color:orange;">**edges**</mark>
{% endhint %}

{% hint style="success" %}
Every <mark style="color:purple;">**tree**</mark> with <mark style="color:red;">**at least 2 vertices**</mark> has a <mark style="color:purple;">**leaf**</mark>. (<mark style="color:orange;">**at least 2 leaves**</mark>, actually)
{% endhint %}

{% hint style="info" %}
General **algorithm** on a **tree T**:

```swift
// while T is not a trivial tree (with only one vertex)
while T.numberOfVertices > 1 {

    let leaf = T.getLeaf()    // T must have a leaf by theorem
    process(leaf)             // process the leaf
    T.removeLeaf(leaf)        // remove processed leaf with its edge
    
    // ⭐️ after removing the leaf and its edge,
    //    T is still connected and #(edges) = #(vertices) - 1,
    //    so, by theorem, T is still a tree.
}

// finally, T is a trivial tree with only one vertex.
let vertex = T.lastVertex
process(vertex)
```

{% endhint %}

👉 [First Course in Algorithms Through Puzzles](https://www.academia.edu/41215050/First_Course_in_Algorithms_Through_Puzzles), Sec. 1.6, Graph
{% endtab %}

{% tab title="📗 參考" %}

* [ ] objc.io ⟩ [Drawing Trees in SwiftUI](https://www.objc.io/blog/2019/12/16/drawing-trees/) ⭐️
  {% endtab %}
  {% endtabs %}