【原】赫夫曼樹

貪挽懶月 2022-06-20 發(fā)布于廣東

展開全文

1. 基本介紹：

路徑：從一個(gè)節(jié)點(diǎn)到達(dá)其后輩節(jié)點(diǎn)的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長(zhǎng)度。上面這棵二叉樹，黃色的線就是50這個(gè)節(jié)點(diǎn)到15這個(gè)節(jié)點(diǎn)的路徑，路徑長(zhǎng)度為3。樹有n層，那么根節(jié)點(diǎn)到第n層節(jié)點(diǎn)的路徑長(zhǎng)度為(n-1)。
帶權(quán)路徑長(zhǎng)度：就是路徑長(zhǎng)度乘以該節(jié)點(diǎn)的值。比如50到15的帶權(quán)路徑長(zhǎng)度就是 3 * 15 = 45。
樹的帶權(quán)路徑長(zhǎng)度：所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記作wpl。
赫夫曼樹：樹的帶權(quán)路徑長(zhǎng)度最小的的樹稱為最優(yōu)二叉樹，也稱為赫夫曼樹。也就說，**wpl最小的樹就叫做赫夫曼樹。**從樹的帶權(quán)路徑長(zhǎng)度的定義可以知道，要想該值最小，離根節(jié)點(diǎn)越近的值應(yīng)該越大，才能使帶權(quán)路徑長(zhǎng)度最小。

給定13, 7, 8, 3這四個(gè)數(shù)作為葉子結(jié)點(diǎn)，構(gòu)建成二叉樹，部分情況如下：

這種情況，權(quán)值為 2 * 13 + 2 * 7 + 2 * 8 + 2 * 3 = 62。

這種情況，權(quán)值為1 * 13 + 2 * 8 + 3 * 7 + 3 * 3 = 59。

顯然第二種情況權(quán)值更小，確保沒有更小的情況下，這棵二叉樹就叫做赫夫曼樹。

2. 構(gòu)建赫夫曼樹：

假如現(xiàn)在要將13, 7, 8, 3, 29, 6, 1構(gòu)建成赫夫曼樹，步驟如下：

首先將數(shù)組升序排序；結(jié)果就是1, 3, 6, 7, 8,13, 29。
取出排序后的前兩個(gè)數(shù)，構(gòu)建成一棵二叉樹，根節(jié)點(diǎn)為兩個(gè)子節(jié)點(diǎn)之和；即取出1和3，構(gòu)建出如下二叉樹：

此時(shí)數(shù)組中的1和3就已經(jīng)用掉了，將上一步構(gòu)建的二叉樹的根節(jié)點(diǎn)4放入數(shù)組中排序，結(jié)果就是：4, 6, 7, 8, 13, 29。
再?gòu)男蛄兄腥〕鰞蓚€(gè)數(shù)，即4和6，構(gòu)建成一棵二叉樹，如下圖：

再將10放到序列中，此時(shí)的序列就是這樣的：7, 8, 10, 13, 29。
再?gòu)男蛄兄腥〕?code style="font-size: 14px;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(239, 112, 96);">7和8，構(gòu)建二叉樹，如下：

將15放到序列中，此時(shí)序列就變成了：10, 13, 15, 29，并且此時(shí)構(gòu)建出了兩棵二叉樹，還沒關(guān)聯(lián)起來，先不用急。
取出10和13，構(gòu)建成二叉樹，此時(shí)二叉樹就變成了：

將23放到序列中，序列就變成了：15, 23, 29。
取出15和23，構(gòu)建成二叉樹，15和23是兩棵樹的根節(jié)點(diǎn)，經(jīng)過這一步，兩棵樹就合并了：

現(xiàn)在序列中就剩下29和38了，所以將29加到這棵樹上就好了，如下圖：

經(jīng)過上面的步驟，就將給定的這個(gè)序列構(gòu)建成了赫夫曼樹。

3. 代碼實(shí)現(xiàn)：

/**
 * 赫夫曼樹
 * @author zhu
 *
 */
public class HuffmanTree {
 
 /**
  * 構(gòu)建赫夫曼樹
  * @param arr
  * @return
  */
 public static Node buildHufmanTree(int[] arr) {
  // 將數(shù)組轉(zhuǎn)成集合，方便增刪元素
  List<Node> nodes = new ArrayList<>();
  for (int i=0; i<arr.length; i++) {
   nodes.add(new Node(arr[i]));
  }
  // 對(duì)集合進(jìn)行排序
  Collections.sort(nodes);
  // 循環(huán)構(gòu)建
  while (nodes.size() > 1) {
   // 取出前兩個(gè)節(jié)點(diǎn)，構(gòu)建二叉樹
   Node leftNode = nodes.get(0);
   Node rightNode = nodes.get(1);
   Node parentNode = new Node(leftNode.getValue() + rightNode.getValue());
   parentNode.setLeft(leftNode);
   parentNode.setRight(rightNode);
   // 移除用掉了的元素，將parent的值添加進(jìn)集合
   nodes.remove(leftNode);
   nodes.remove(rightNode);
   nodes.add(parentNode);
   // 重新排序
   Collections.sort(nodes);
  }
  // 返回赫夫曼樹的根節(jié)點(diǎn)
  return nodes.get(0);
 }
 
 /**
  * 前序遍歷
  * 
  * @param root
  */
 public static void preOrder(Node root) {
  // 先輸出當(dāng)前節(jié)點(diǎn)
  System.out.println(root.getValue());
  // 判斷左子節(jié)點(diǎn)是否為空，不為空就遞歸
  if (root.getLeft() != null) {
   preOrder(root.getLeft());
  }
  // 判斷右子節(jié)點(diǎn)是否為空，不為空就遞歸
  if (root.getRight() != null) {
   preOrder(root.getRight());
  }
 }
 
 /**
  * 節(jié)點(diǎn)內(nèi)部類，實(shí)現(xiàn)compareble接口，方便對(duì)node排序
  * @author zhu
  *
  */
 static class Node implements Comparable<Node>{
  private int value;
  private Node left;
  private Node right;
  public Node(int val) {
   this.value = val;
  }
  public int getValue() {
   return value;
  }
  public void setValue(int value) {
   this.value = value;
  }
  public Node getLeft() {
   return left;
  }
  public void setLeft(Node left) {
   this.left = left;
  }
  public Node getRight() {
   return right;
  }
  public void setRight(Node right) {
   this.right = right;
  }
  @Override
  public String toString() {
   return "Node [value=" + value + "]";
  }
  @Override
  public int compareTo(Node o) {
   // 升序
   return this.value - o.value;
  }
 }
 
 public static void main(String[] args) {
  int[] arr = {13, 7, 8, 3, 29, 6, 1};
  Node node = buildHufmanTree(arr);
  preOrder(node);
 }

}