数据结构 - 哈夫曼树

基本概念 (Huffman Tree)

路径和路径长度:

在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1,则从根结点到第L层结点的路径长哈夫曼树度为 L-1。

结点的权及带权路径长度:

若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度:

树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为 WPL。即设二叉树有 n 个叶子结点,每个叶子结点带有权值 wk,从根结点到每个叶子的长度为 lk,则每个叶子结点的带权路径长度之和:WPL = ∑wi*li (i = 0,1,2...n)

哈夫曼树(也称为最优二叉树)就是使 WPL 达到最小的二叉树, 哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

构造方式:
  1. 将 w1、w2、…,wn 看成是有 n 棵树的森林(每棵树仅有一个结点)
  2. 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和
  3. 从森林中删除选取的两棵树,并将新树加入森林
  4. 重复步骤 2、3,直到森林中只剩下一棵树为止,该树即为所求的哈夫曼树

image.png

代码实现
package com.coderman.datastruct.tree;

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

/**
 * @Author zhangyukang
 * @Date 2020/5/31 16:59
 * @Version 1.0
 **/
public class HuffmanTreeTest {
    public static void main(String[] args) {
        int[] array={1,3,5,7};
        HuffmanTree huffmanTree = new HuffmanTree(array);
        //前序遍历验证
        huffmanTree.preOrder(huffmanTree.getRoot());
    }
}

class HuffmanTree{

    private Node root;

    private int[] array;

    public HuffmanTree(int[] array){
        this.array=array;
        this.root=createTree(array);
    }

    /**
     * 前序遍历
     */
    public void preOrder(Node current){
        if(current!=null){
            System.out.println(current);
            preOrder(current.left);
            preOrder(current.right);
        }
    }

    public Node getRoot() {
        return root;
    }

    /**
     * 构建哈夫曼树
     * @param array
     * @return
     */
    public Node createTree(int[] array){
        List<Node> nodes = getNodes(array);

        while (nodes.size()>1) {
            //1. 先将所有的节点进行排序
            Collections.sort(nodes);
            //2. 取出最小的一个节点(子树),和次小的节点的
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //3. 构建成一颗新的子树
            Node parentNode = new Node(leftNode.val + rightNode.val);
            parentNode.left=leftNode;
            parentNode.right=rightNode;
            //4, 移除leftNode和rightNode
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //5.将新构建的子树添加
            nodes.add(parentNode);
        }
        return nodes.get(0);
    }

    /**
     * 将数组构建成List集合节点
     * @param array
     * @return
     */
    public List<Node> getNodes(int[] array){
        List<Node> nodes=new ArrayList<>();
        for (int i : array) {
            nodes.add(new Node(i));
        }
        return nodes;
    }

}

class Node implements Comparable<Node>{
    int val;
    Node left;
    Node right;

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

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

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

输出结果
Node{val=16}
Node{val=7}
Node{val=9}
Node{val=4}
Node{val=1}
Node{val=3}
Node{val=5}

Process finished with exit code 0
# Java   二叉树   算法      数据结构  

评论

公众号:mumuser

企鹅群:932154986

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×