关于java:我所知道的数据结构之哈夫曼树

前几篇文章咱们学习二叉树、程序二叉树、线索化二叉树、堆，接下来咱们持续学习有对于树的下一个利用构造：哈夫曼树

一、什么是哈夫曼树

根本介绍

1.给定n个权值作为n个叶子结点，结构一棵二叉树，若该树的带权门路长度1(wpl)达到最小，称这样的二叉树为最优叉树。也称为哈夫曼树(HuffmanTree)，还有的书翻译为霍夫曼树。

wpl：weight pathI ength

2.哈夫曼树是带权门路长度最短的树，权值较大的结点离根较近。

问题剖析

那么这时就有新的问题呈现！须要咱们解决了

1.什么是门路呢？门路长度是什么？

2.什么是权和带权门路长度是什么？

3.带权门路长度最短的树，那么树的带权门路长度是什么？

什么是门路和门路长度？

在一棵树中，从一个结点往下能够达到的孩子或孙子结点之间的通路，称为门路。

通路中分支的数目称为门路长度。若规定根结点的层数为 1，则从根结点到第L层结点的门路长度为L-1。

什么是结点的权和带权门路长度？

若将树中结点赋给一个有着某种含意的数值，则这个数值称为该结点的权。

结点的带权门路长度为：从根结点到该结点之间的门路长度与该结点的权的乘积。

什么是树的带权门路长度？

树的带权门路长度规定为：
所有叶子结点的带权门路长度之和，记为WPL(weighted path length)，权值越大的结点离根结点越近的二叉树才是最优二叉树。

通过不同的WPL意识哈弗曼树

若该树的带权门路长度1(wpl)达到最小，称这样的二叉树为最优叉树。也称为哈夫曼树(HuffmanTree)

哈夫曼树是带权门路长度最短的树，权值较大的结点离根较近

如上图所示咱们发现两头的树其实就是哈夫曼树(HuffmanTree)，并且满足权值较大的结点离根较近

权值越大的叶子节点越凑近根节点，权值越小的叶子节点越远离根节点。

二、通过示例意识哈夫曼树

将一个权重数列{13, 7, 8,3,29,6,1}，求转成一颗赫夫曼树.

思路图解剖析

1.将数列{13, 7, 8, 3, 29, 6, 1}，进行从小到大排序

2.新数列的每个数看成最简略根节点的二叉树

3.取出权值最小的两颗二叉树组成新的二叉树，为两最小的树之和

4.将新二叉树以跟节点的权重值再次从小到大排序，一直反复步骤

咱们发现每次都须要依据节点权重值进行大小排序，那么咱们能不能使得对象节点自身就具备比拟的性能呢？

答案是有的：咱们的自定义对象Node实现Comparable接口

同时当咱们发现排序后，数列的前两个就是最小的权值。

那么依据图所示咱们来上节点的代码把

//创立节点类  
//为了让Node 对象继续排序Conllections汇合排序  
//让Node 实现Comparable接口  
class Node implements Comparable<Node>{  
  
    int value;//结点权值  
    Node left;//指向左节点  
    Node right;//指向右节点  
  
    public Node(int value) {  
            this.value = value;  
     }  

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

     @Override  
     public int compareTo(Node o) {  
         //示意从小到大进行排序  
         //从大到小进行排序 - (this.value - o.value)；
         return this.value - o.value;  
     }  
}

外围代码剖析

public static void createHuffmanTree(int[] arr ){  
  
    /**  
     * 操作思路
     * 1.遍历arr数组
     * 2.将arr数组里的元素形成Node节点
     * 3.将Node 放入ArrayList中
     * 4.进行从小到大排序
     */ 
     List<Node> nodes = new ArrayList<Node>();  
     for (int itme:arr) {  
        nodes.add(new Node(itme));  
     }  
  
    //进行排序，ArrayList里的sort排序Node 须要实现Comparable接口  
     Collections.sort(nodes);  
  
     System.out.println(nodes);  
}

咱们先来测试看看第一步：将数列形成节点并进行从小到大排序

public static void main(String[] args) {  
  
    int arr[] = {13,7,8,3,29,6,1};  
    createHuffmanTree(arr);  
}

运行后果如下：
[Node[value=1], Node[value=3], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]

如上所示，第一步看来还是胜利了的，那么接下来进行第二步

进行第二步：取出权值最小的两颗二叉树组成新的二叉树，为两最小的树之和

public static void createHuffmanTree(int[] arr ){  
  
    //省略第一步：将数列形成节点并进行从小到大排序代码
   /**  
    *  操作思路 
    *  1.取出两个权值最小的节点二叉树
    *  2.依据两个权值最小的二叉树构建成一个新的二叉树
    *  3.删除原先两个权值最小的节点二叉树
    *  4.将新的二叉树放入队列，并构建新的队列
    *  5.新的队列进行从小到大排序 */  
    
    //取出第一个权值最小的二叉树  
    Node leftNode = nodes.get(0);  
    //取出第二个权值最小的二叉树  
    Node rightNode = nodes.get(1);  

    //依据两个权值最小的二叉树构建成一个新的二叉树 同时构建连贯  
    Node parentNode  = new Node(leftNode.value + rightNode.value);  
    parentNode.left = leftNode;  
    parentNode.right = rightNode;  

    //删除原先两个权值最小的节点二叉树  
    nodes.remove(leftNode);  
    nodes.remove(rightNode);  

    //将新的二叉树放入队列，并构建新的队列  
    nodes.add(parentNode);  

    Collections.sort(nodes);  

    System.out.println("第一次解决后："+nodes);
}

运行后果如下：
[Node[value=1], Node[value=3], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]
第一次解决后：[Node[value=4], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]

细节法则小结

1.新的二叉树增加后、就会删除原两个权值最小的二叉树
2.解决完后须要从新排序从小到大
3.如思路剖析图所示反复步骤操作后队列里只剩下一个节点

整合外围代码

public static Node createHuffmanTree(int[] arr ){  
  
    /**  
     * 操作思路 
     * 1.遍历arr数组 
     * 2.将arr数组里的元素形成Node节点 
     * 3.将Node 放入ArrayList中 
     * 4.进行从小到大排序 
     */ 
     
     List<Node> nodes = new ArrayList<Node>();  
     for (int itme:arr) {  
            nodes.add(new Node(itme));  
     }  

     while(nodes.size() >1){  

         //进行排序从小到大  
         Collections.sort(nodes);  

         System.out.println(nodes);  

        /**  
        *  操作思路 
        *  1.取出两个权值最小的节点二叉
        *  2.依据两个权值最小的二叉树构建成一个新的二叉树
        *  3.删除原先两个权值最小的节点二叉树 
        *  4.将新的二叉树放入队列，并构建新的队列 
        *  5.新的队列进行从小到大排序 
        */ 
        
        //取出第一个权值最小的二叉树  
        Node leftNode = nodes.get(0);  
        
        //取出第二个权值最小的二叉树  
        Node rightNode = nodes.get(1);  

        //依据两个权值最小的二叉树构建成一个新的二叉树 同时构建连贯  
        Node parentNode  = new Node(leftNode.value + rightNode.value);  
        parentNode.left = leftNode;  
        parentNode.right = rightNode;  

        //删除原先两个权值最小的节点二叉树  
        nodes.remove(leftNode);  
        nodes.remove(rightNode);  

        //将新的二叉树放入队列，并构建新的队列  
        nodes.add(parentNode);  
     }  
     //因为队列只剩下最初一个节点所以间接返回即可  
     return nodes.get(0);  
}

接下来让咱们验证一下是否如图所示胜利绘制成哈夫曼树

应用前序遍历打印留在队列的root 节点，还记得前序遍历吗？

前序遍历特点：前序是先输入父节点，再遍历左子树和右子树

class Node implements Comparable<Node>{ 

    //省略Node 逻辑代码
    //增加前序遍历代码
    public void preOrder(){  
  
      System.out.println(this); 
         
      if(this.left!=null){  
        this.left.preOrder();  
      }  
      if(this.right!=null){  
        this.right.preOrder();  
      }  
   }
    
}

//增加根节点遍历办法
public  static void preOrder(Node root){  
  
    if(root!=null){  
        root.preOrder();  
    }else{  
        System.out.println("该哈弗曼树为空！无奈遍历");  
    }  
}

咱们的数列{13, 7, 8,3,29,6,1}，组装成哈弗曼树后的前序遍历，思考一下是什么呢？

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

运行后果如下：
[Node[value=1], Node[value=3], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]
[Node[value=4], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]
[Node[value=7], Node[value=8], Node[value=10], Node[value=13], Node[value=29]]
[Node[value=10], Node[value=13], Node[value=15], Node[value=29]]
[Node[value=15], Node[value=23], Node[value=29]]
[Node[value=29], Node[value=38]]
Node[value=67]
Node[value=29]
Node[value=38]
Node[value=15]
Node[value=7]
Node[value=8]
Node[value=23]
Node[value=10]
Node[value=4]
Node[value=1]
Node[value=3]
Node[value=6]
Node[value=13]