# Tree & Binary & Traversal
###### tags: `資料結構`

### Tree
* 由一個或多個節點組成的有限**集合**，不能是空的
* 不連接圖不是一個樹

### Binary Tree
* 可以是空的
* 含root節點或有 left subtree or right subtree
* n個節點可以有`1/(n+1)(C2n取n種)`binary tree
* i 層最多會有`2的i次方`節點(root：i=0)
* h 高度tree最多有`2的h次方-1`節點(root：h=1)

---

*圖片來源：https://medium.com/swlh/understanding-data-structures-binary-search-trees-a6612daf00dd*

* full binary tree：全滿狀態
* complete binary tree：只能最下層的最右邊節點缺少，該index與full binary tree一樣
* skewed tree：右傾左傾樹
* Degenerate/Pathological Tree：It is a type of BST in which each node has only one child node.

---
## Traversal
*圖片來源：https://www.faceprep.in/data-structures/tree-traversals-inorder-preorder-and-postorder/*

### inorder (左中右)
algorithm Inorder(tree)
1. Traverse the left subtree, **Inorder(root.left)**
2. Visit the root.
3. Traverse the right subtree, **Inorder(root.right)**

上圖所示
**inorder**： 7 9 4 2 5 1 3 6 8

---

### preorder (中左右)
algorithm preorder(tree)
1. Visit the root.
2. Traverse the left subtree, **Preorder(root.left)**
3. Traverse the right subtree, **Preorder(root.right)**

上圖所示
**preorder**： 1 2 4 7 9 5 3 6 8

---

### postorder (左右中)
algorithm postorder(tree)
1. Traverse the left subtree, **Postrder(root.left)**
2. Traverse the right subtree, **Postorder(root.right)**
3. Visit the root.

上圖所示
**postorder**： 9 7 4 5 2 8 6 3 1

---
#### 一個 inorder 與 preorder / postorder 才可以決定唯一的binary tree