---
title: 'Tree Transformation'
disqus: hackmd
---
[TOC]

---

# Tree Transformation

* 此章節的內容是將以下三種樹做彼此之間的轉換，並無任何程式相關的東西，不需要的可略過此節

* **Tree**
* **LC-RS Binary Tree**
* **Forest**

---

## Tree to LC-RS Binary Tree
* LC-RS 為 Left-child Right-sibling 的縮寫，是將 K-ary(K元) Tree 轉換成 Binary Tree 的一種方法，轉換的過程又稱作 [Knuth](https://en.wikipedia.org/wiki/Donald_Knuth) Transform

* 依照中文的字面意思就是，**左兒子、右兄弟** 此也是我們轉換的核心所在


### Left-child Right-sibling
---

* **Left-child**
* 當我們拿到一顆 K-ary Tree 時，我們將每顆子樹的 Leftmost 的父子 Link 保留起來


* **Right-sibling**
* 並且我們將彼此是兄弟關係的 Node 連結起來

* **再來將其餘的父子關係 Link 移除**

* **最後將兄弟間的 Link 順時針轉 45度**

## LC-RS Binary Tree to Tree
* 將上述步驟倒回去做即可

* **將 Link 逆時針轉 45度**

* **連接父子關係**

* **移除兄弟關係**


---

## Forest to Binary Tree
* Forest 是由一群 k-nary 樹所組成，Forest 可以為空
* 執行步驟跟 Tree to LC-RS Binary Tree 幾乎一樣，唯一不同的地方在於森林的 Root 可能不只有一個，於是我們會將 Root Node 之間採用兄弟關係連接起來

digraph graphname{
1[color=red]
7[color=red]
10[color=red]
   1->2
   1->3
   1->4
   3->5
   3->6
   
   7->8
   8->9
   10->11
   10->12
}

* 將各顆 Tree 各自轉換成 Binary Tree (先不要旋轉)

* 再將 Root 間同樣以 **兄弟關係** 連結 Link

* 接著將水平或垂直的 Link 順時針旋轉 45 度


---

## Binary Tree to Forest

* 若 LC-RS Binary Tree to Tree 沒問題的話這邊也不會有問題

* **將 Link 逆時針轉 45度**

* **連接父子關係**

* **移除兄弟關係**

###### tags: `Data Structure`