Lucy's Note of Coding

 深度優先搜尋(DFS: Depth-First Search)：
   * 深度優先遍歷，從初始訪問點出發，初始訪問點可能有多個鄰接結點，
   * 深度優先的遍歷的策略是首先訪問第一個鄰接點，
   * 然後再以這個被訪問的鄰接結點作為初始訪問結點，
   * 訪問它的第一個鄰接結點，
   * 即每一次訪問完當前節點都會首先訪問當前節點的第一個鄰節點。類似迷宮回溯算法。
   * 深度是盡可能找下一層的結點

 廣度優先搜尋(Breadth-First Search)：
   * 廣度是盡可能的找同一層的結點

資料結構 Huffman樹：

1、介紹
（1) 給定n 個權值作為n 個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度(wpl)達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree), 還有的書翻譯為霍夫曼樹。
（2) 赫夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近
2、重要概念和舉例說明
（1) 路徑和路徑長度：在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路
中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L 層結點的路徑長度為L-1
（2) 結點的權及帶權路徑長度：若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積
（3) 樹的帶權路徑長度：樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL(weighted path length) ,權值越大的結點離根結點越近的二叉樹才是最優二叉樹。

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

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

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

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

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

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

合併排序：空間換時間

快速排序(QuickSort)
 

希爾排序(ShellSort)