---
# System prepended metadata

title: Tree
tags: [109_FDCS]

---

---
tags: 109_FDCS
---

# Tree

## 什麼是樹

:::spoiler {state=open} Binary tree
![](https://imgur.com/ppv7zVD.png =300x) ![](https://imgur.com/uKzwdD3.png =300x)
:::

---

## 性質

如果一張圖被稱作樹
那它一定符合以下性質

1. 必連通
2. 兩點之間有唯一一條路徑
3. 任兩點之間加上一條路徑即會形成環
4. 去掉任一條邊就不再連通
5. 若共有 $n$ 個點，則有 $n-1$ 個邊
6. 是一個DAG(Directed Acyclic Graph / 有向無環圖)

所以也可以說，沒有環的連通圖就是樹

---

## [next -> LCA](/@konchin/ryhgIlhMu)