前言

昨天談完二元樹的結構、三大定理、種類，今天要進入的部分就是我們要使用甚麼資料結構去實作這個 ADT，以及使用這些資料結構的優缺點再進入 Traversal 的演算法撰寫部分

實作二元樹

在實作二元樹的部分，主要我們可以區分為使用 Array 或是 LinkedList 去實作，而利用這兩種資料結構去實作，都會有各自不同的優缺點，以下我們先談實作方法，再談優缺點

1. 使用 Array 實作二元樹：
   讓 Node 數 = n，高度為 k 的二元樹，建立 Array A[1...]
   並依照 Node 編號依序放入 Array 之中
2. 使用 LinkedList 實作二元樹：
   使　Node 之結構為 leftLink data RightLink 形式，依照二元樹的長相，去牽起連線即可

優缺點

1. Array：
   • 優點：當樹的種類為 Complete, full BT 時不會浪費到任何空間，此外也可以直接使用某點 index*2 取得左子點、index * 2+1 取得右子點，[index/2] 取得父點，相比 Linkedlist，Array 取得父點的難易度低非常多
   • 缺點：若樹的種類為 Skewed 的話，會造成非常多的空間浪費
2. LinkedList
   • 優點：很容易增刪節點、對於 Skewed 的二元樹不會造成太多空間浪費
   • 缺點：難以取得父點、並且一定會浪費 n+1 的 link space (可以看到 Day03-Tree 的 LinkList 建置部分，將m=2代入，即得)

BT Traversal Algo

在寫 BT Traversal 前，要先知道 preorder 的順序為 DLR、inorder 的順序為 LDR、Postorder 的順序為 LRD
(Tips) D 放在某種序的相對應位置即可 e.g 前序 D 就放最前面

preorder(t){ //DLR	
	print(t->data);
	preorder(t->lchild);
	preorder(t->rchild);
}

inorder(t){ //LDR
	inorder(t->lchild);
	print(t->data);
	inorder(t->rchild);
}

postorder(t){ //LRD
	postorder(t->lchild);
	postorder(t->rchild);
	print(t->data);
}