資料結構與算法-樹（赫夫曼樹）

文章目錄

• 赫夫曼樹
• 一、幾個概念
• 二、赫夫曼樹實作源碼
• 總結

赫夫曼樹

一、幾個概念

二、赫夫曼樹實作源碼

代碼如下（示例）：

package HuffmanTree;

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

public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node root = CreatHaffmanTree(arr);
        PreOrder(root);
    }

    /**
     *
     * @param arr 給出需要建立赫夫曼樹的數組
     * @return 傳回赫夫曼樹的root節點
     */
    public static Node CreatHaffmanTree(int[] arr) {
        //建立一個ArrayList集合，将arr中的數以節點的形式放入ArrayList中
        ArrayList<Node> arrayList = new ArrayList<Node>();
        for (int n : arr) {
            arrayList.add(new Node(n));
        }
        while (arrayList.size() > 1) {
            //對ArrayList集合中的元素進行排序
            Collections.sort(arrayList);
            //将ArrayList中的前2個節點取出來組合成一個赫夫曼樹
            Node leftnode = arrayList.get(0);
            Node rightnode = arrayList.get(1);
            Node parentnode = new Node(leftnode.value + rightnode.value);
            parentnode.left = leftnode;
            parentnode.right = rightnode;
            //移除已經組成赫夫曼樹的兩個節點
            arrayList.remove(leftnode);
            arrayList.remove(rightnode);
            //然後将父節點加入到原始的arraylist中
            arrayList.add(parentnode);

        }
        return arrayList.get(0);
    }

    //實作前序列印
    public static void PreOrder(Node root) {
        if (root != null) {
            root.PreOrder();
        } else {
            System.out.println("赫夫曼樹為空");
        }
    }
}

//對Collections集合進行排序，實作Comparable接口
class Node implements Comparable<Node> {
    public int value;
    public Node left;
    public Node right;

    //加一個構造方法
    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }

    //實作前序排序
    public void PreOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.PreOrder();
        }
        if (this.right != null) {
            this.right.PreOrder();
        }
    }
}

           

總結

主要思路是先進行排序，這裡直接利用集合中的Comparable接口實作，然後就是将前面2個小節點排序成赫夫曼樹，知道最後一個節點。