[JAVA]圖(Graph)的深度優先搜尋(DFS)vs.廣度優先搜尋(BFS)

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

[JAVA]自平衡二元搜尋樹(AVL樹)

AVL樹的原理與BST原理大致相同,主要目的是讓樹的左右子樹達到平衡;
兩邊的高度差不超過1(平衡),即為AVL樹。

平衡左右子樹的時機,在新增結點後,需檢查樹是否平衡,
不平衡,即進行左旋轉或右旋轉。

資料來源:尚硅谷算法youtube
...繼續閱讀 »

[JAVA]Huffman Tree:實現文件壓縮與解壓(編碼encode到decode)

  1. 透過建立的huffman tree,以遞迴的方式從根結點走向葉子結點;
    藉由紀錄走訪過程向左為0、向右為1,恰巧符合二進制,
    走過的路徑就成了葉子結點編碼(encode),而有了encode編碼表。
  2. 將1.取得的二進制字串轉成byte(8 bits一個單位)進行減少體積 => 壓縮
  3. 最後在進行解壓縮的一系列過程。
...繼續閱讀 »

[JAVA]Huffman Tree : 建立樹並取得帶權路徑長度/前序遍歷

資料結構 Huffman樹

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

...繼續閱讀 »