4.2 赫夫曼樹資料結構

• • • 介紹
    • 代碼

介紹

來自百度百科

1. 給定N個權值作為N個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹。
2. 路徑和路徑長度：在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。
3. 結點的權及帶權路徑長度：若将樹中結點賦給一個有着某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。
4. 樹的帶權路徑長度：樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL。

代碼

給一組資料作為節點權值，構造一棵赫夫曼樹。

構造一棵赫夫曼樹：

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

/**
 * 依據給定數組資料 構造 huffman樹
 * @author dxt
 *
 */
public class HuffmanTree {
	public static void main(String[] args) {
		int arr[] = {13, 3, 6, 9, 5, 20, 64};
		
		Node root = createHuffmanTree(arr);
		if(root != null) {
			root.preOrder();
		}
	}
	
	//建立huffman樹
	public static Node createHuffmanTree(int[] arr) {
		//1. 依據數組arr構造節點，然後将節點儲存到ArrayList中
		List<Node> nodes = new ArrayList<Node>();
		for(int temp : arr) {
			Node n = new Node(temp);
			nodes.add(n);
		}
		
		while(nodes.size() > 1) {
			//2. 将nodes中的節點進行排序，使用sort方法，sort方法會調用在Node類中重寫的compareTo()方法
			Collections.sort(nodes);
		
			//3. 構造樹
			//3.1 取出權值最小的兩個節點
			Node leftNode = nodes.get(0);
			Node rightNode = nodes.get(1);
			//3.2 建構一個新的二叉樹,其中parent.value = left.value + right.value
			Node parent = new Node(leftNode, rightNode);
			//3.3 nodes删除使用的兩個節點，添加此新建構的節點
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			nodes.add(parent);
		}
		
		//4. 傳回nodes中剩餘的節點，即是huffman樹的根
		return nodes.get(0);
	}
}
           

構造過程中使用到的Node類

/**
 * 節點類
 * @author dxt
 *
 */
public class Node implements Comparable<Node>{
	int value;		//節點權值
	Node left;		//指向左子節點
	Node right;		//指向右子節點
	
	public Node(int value) {
		this.value = value;
	}
	public Node(Node left, Node right) {
		this.value = left.value + right.value;
		this.left = left;
		this.right = right;
	}
	
	//前序周遊
	public void preOrder() {
		System.out.println(this);
		if(this.left != null) {
			this.left.preOrder();
		}
		if(this.right != null) {
			this.right.preOrder();
		}
	}
	
	//重寫toString()方法
	public String toString() {
		return "Node: value = " + this.value;
	}

	@Override
	public int compareTo(Node o) {
		//從小到達進行排序
		return this.value - o.value;
	}
}