--- 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)