Binary Tree

每個internal node只有一或兩個小孩（若每個node剛好兩個小孩，稱proper binary tree），且左右節點有order。

• Example : Decision Tree
  internal node : 問題和yes/nod
  external node : decision

  -->為proper binary tree(每個node一定都有兩個小孩)

• Properties of binary tree
  **1. 1 ≤ ne ≤ 2^h

  1. h ≤ ni ≤ 2^h - 1
  2. h+1 ≤ n ≤ 2^(h+1) - 1
  3. log(n+1) - 1 ≤ h ≤ n-1**

• Properties of PROPER binary tree
  **1. h+1 ≤ ne ≤ 2^h

  1. h ≤ ni ≤ 2^h - 1
  2. 2h+1 ≤ n ≤ 2^(h+1) - 1
  3. log(n+1) - 1 ≤ h ≤ (n-1)/2
  4. ne = ni+1**
     -->證明：歸納法

• Link Structure for Trees
  把children串起來，比較好之後再走一遍

• Link Structure for Binary Tree

• Vector Representation for Binary Trees
  用level order來做
  好處：找左右子樹、parents很快

          --> root :  
               **若v為parents\(v\)的左子點 : f\(v\) = 2\*f\(parents\(v\)\)  
               若v為parents\(v\)的右子點 : f\(v\) = 2\*f\(parents\(v\)\) + 1**  
               此處f\(\)為其的level number  
  

  缺點：浪費記憶體空間

          -->O\(N\)，若worse case : O\(2^n\)
  

• Post-order Traversal in Evaluation Arithmetic Expression
  與postfix類似

• Example
  若要從post-order、pre-order、in-order找出tree，一定要有兩個，且一定要有inorder，才能找出唯一一棵樹

• General trees to Binary trees
  Left-child right-sibling