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

2022-07-01 置頂文章

資料結構 Huffman樹：

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

在這裡插入圖片描述 — 參考來源：https://blog.csdn.net/qq_41853002/article/details/106382239

package utitled;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/** Huffman樹 */
public class HuffmanTreeDemo {
  public static void main(String[] args) {
    int[] arr = {13, 7, 8, 3, 29, 6, 1};
    Node root = HuffmanTree.buildHuffmanTree(arr);
    // root的no即 樹的帶權路徑長度：樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和
    System.out.println("root = " + root);

    // 前序遍歷
    HuffmanTree.preOrder(root);

  }
}

class HuffmanTree {

  /**
   * 前序遍歷huffman tree
   * @param root
   */
  public static void preOrder(Node root) {
    if (root != null) {
      root.preOrder();
    }
  }

  /**
   * 創建Huffman tree
   * @param arr
   * @return 回傳huffman tree根結點
   */
  public static Node buildHuffmanTree(int[] arr) {
    // 創建一個ArrayList<Node>存放從小排到大的Nodes
    List<Node> nodeList = new ArrayList<>();

    for (int i : arr) {
      // 創建所有二元樹，每個節點就是一個最簡單的二元樹
      nodeList.add(new Node(i));
    }

    while (nodeList.size() > 1) {
      // 整個huffman tree創建完成的時機是當nodeList只剩一個node，而此node的權重就是樹的帶權路徑長度

      // 將有實作Comparable<Node> interface做從小到大排序
      Collections.sort(nodeList);

      // 取出最小跟次小二元樹(結點)來創建新的二元樹，新二元樹的權重為被取出兩個二元樹的權重之和
      Node minNode = nodeList.get(0);
      Node secondNode = nodeList.get(1);
      Node newNodeTree = new Node(minNode.getNo() + secondNode.getNo());
      // 設定newNodeTree的左右子結點
      newNodeTree.setLeft(minNode);
      newNodeTree.setRight(secondNode);
      // 前面取出過的二元樹，使用完後，從list移除
      nodeList.remove(minNode);
      nodeList.remove(secondNode);
      // 將新生成的二元樹加入list
      nodeList.add(newNodeTree);
    }
    return nodeList.get(0);
  }
}

/**
 * 為了讓自定義Node物件從小排到大，讓它實作Comparable<Node>的compareTo()
 * 之後才能使用Collections.sort進行排序
 */
class Node implements Comparable<Node>{
  private int no;
  private Node right;
  private Node left;

  public Node(int no) {
    this.no = no;
  }

  public int getNo() {
    return no;
  }

  public Node getRight() {
    return right;
  }

  public void setRight(Node right) {
    this.right = right;
  }

  public Node getLeft() {
    return left;
  }

  public void setLeft(Node left) {
    this.left = left;
  }

  @Override
  public String toString() {
    final StringBuilder sb = new StringBuilder("Node{");
    sb.append("no=").append(no);
    sb.append('}');
    return sb.toString();
  }

  /**
   * 回傳從小排到大排列的Nodes
   * @param node
   * @return
   */
  @Override
  public int compareTo(Node node) {
    return this.no - node.no;
  }

  /**
   * 前序遍歷huffman tree(遞迴)
   */
  public void preOrder() {
    // 輸出自己
    System.out.print(" " + this);

    // 向左子樹繼續遞迴
    if (this.getLeft() != null) {
      this.getLeft().preOrder();
    }
    // 向右子樹繼續遞迴遍歷
    if (this.getRight() != null) {
      this.getRight().preOrder();
    }
  }
}

如有敘述錯誤，還請不吝嗇留言指教，thanks!

huffman tree

回首頁