Lucy's Note of Coding

完滿(Full)二元樹vs 完全(Complete)二元樹vs 完美(Perfect)二元樹

以下此圖為二元樹，本篇會以三種方式進行遍歷與搜尋

1. 前序遍歷(Preorder Traversal)
2. 中序遍歷(Inorder Traversal)
3. 後序遍歷(Postorder Traversal)

另外刪除指定結點之前後，再以前序/中序/後續 遍歷。

圖片來源：https://blog.csdn.net/weixin_44441009/article/details/115333213

  // 進行FibonacciSearch前提，先準備好有序陣列
  // 透過斐波那契數列取得變動的中間索引
  // f[k]會配合待排序陣列之長度

  // 進行InterpolationSeach前提，先準備好有序陣列
  // 優勢：適合用於陣列值為較連續的、值的差距不大、資料量大
  // 唯有取得中間值公式與二分搜尋不同，剩餘作法一致

  // 進行BinarySeach前提，先準備好有序陣列
  // 若目標值小於中間值，則向左遞歸查找
  // 若目標值大於中間值，則向右遞歸查找
  // 若目標值等於中間值，則直接回傳中間值索引
  // 若查找不到目標值，例如left > right，即退出遞歸

演算法 => 線性搜索(Sequence search)

需要二維陣列：第一維用來表示第幾個桶，第二維用來儲存符合x位數基數的值
需要一維陣列：用來表示二維陣列的每個桶，儲存幾個值
每個桶的空間：以待排序陣列長度為基準
步驟：1. 先找出最大值，並得出最大值位數 => 基數排序進行的次數，假設最大值為百位數，那基數排序會排序3次
2. 求出個位數基數，將值依序放入二維陣列中
3. 紀錄每個桶放入幾個數 => 入一維陣列
4. 取出二維陣列的值放回原待排序陣列，並清空二維陣列、一維陣列做為下一次排序使用

合併排序：空間換時間