树结构入门教程-赫夫曼树

前面我们学习了堆排序,关于堆排序就两点需要我们清楚,ruguoxuqiu如果是升序操作,我们需要构建大顶堆,如果是降序操作,我们构建小顶堆,这节我们来学习如何构建赫夫曼树,那么在构建之前我们先来了解下什么是赫夫曼树.

赫夫曼树的介绍

给定n个权值作为n个叶子节点,构建一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的树为最优二叉树,也称赫夫曼树.

其中作为赫夫曼树必须是带权路径长度(wpl)最短的树,权值较大的节点离根节点比较近

关于上述的介绍中的出现的特有名词: 权值 和带权路径长度(wpl)我们接下来介绍下,首先我们来看张图

赫夫曼树介绍.png

在介绍权值和wpl时,我们先来了解下什么是树的路径和路径的长度这个问题

路径和路径长度: 如上图所示的一棵树,我们从一个节点往下可以到达孩子节点之间的通路我们称它为路径.其中通路中分支的数目我们称之为路径长度,若我们规定根节点的层数为1的话,那么从根节点到第L层节点的路径长度为L-1,那上图所示,我们节点13的路径长度= 3-1 =2

节点的权值和带权路径长度: 如果我们将树中节点给它们分别赋给存在某种含义的数值,则我们将这个数值称为该节点的权值.节点的带权路径长度: 从根节点到该节点之间的路径长度与该节点权值的乘积,如上图中节点13的,它的权值为13 ,带权路径长度 = 13* 2 = 26

树的带权路径长度:我们规定树的带权路径长度是所有叶子节点 的带权路径长度之和,我们称之为wpl(weighted path length),其中权值越大的节点离根节点越近的二叉树我们称之为最优二叉树,我们来看wpl的计算,首先我们计算下上述图中的二叉树的wpl:

    wpl = 13 *2 + 7*2 + 8*2 +3*2 = 62

关于节点相同的二叉树,我们需要选择最优的那棵二叉树,如下图:

2.png

我们来计算上述图中二叉树的wpl =131 +82+ 7*3 +3 *3 = 59

3.png

我们再来看上述图中wpl= 71+32+ 8*3+13 *3 = 76

通过我们对wpl的计算得知,wpl= 59就是最优的二叉树

上述就是对赫夫曼树的简单介绍,接下来我们来看看如何构建一棵赫夫曼树,我们通过一个实际的案例来分析下创建赫夫曼树的所需步骤:

假设我有一组数列{13,7,8,3,29,6,1},我们要求将它转成一棵赫夫曼树,我们来看下整个构建过程中的思路分析:

• 首先我们需要将待构建的数列进行升序操作,即:{1,3,6,7,8,13,29},其中这每一个数据我们都看成是一个节点,每个节点都可以看作为一棵最简单的二叉树

• 接着我们从排好序的数列中取出根节点权值最小的两棵二叉树如下图所示:

  
  赫夫曼树创建思路分析图解1.png

我们发现组成的新的二叉树,其根节点的权值(也就是上述图中的二叉树的根节点其权值为4)是前面两个二叉树根节点权值的和(也就是二叉树根节点1和根节点3)

• 我们在将这颗新的二叉树以根节点权值大小进行再次的排序操作如图所示:

  
  赫夫曼树创建思路分析图解2.png

接着就简单了,我们重复上述操作,直达我们的数列中所有的数据都被处理,最终完成赫夫曼树的创建,如图:

赫夫曼树创建思路分析图解3.png

上述就是我们最终的创建的赫夫曼树结果图,接下来我们采用代码的方式来实现该过程:

代码实现

首先我们需要一个节点类,实现了Comparable接口其目的时完成内部排序,具体代码如下:

//创建节点
class Node implements Comparable<Node>{
int value; //节点的权值
Node left;//指向左子节点
Node right;//指向右子节点

//写一个前序遍历的方法
public void preOrder(){
    System.out.println(this);
    if (this.left !=null){
        this.left.preOrder();
    }
    if (this.right !=null){
        this.right.preOrder();
    }
}

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;
}

其中方法compareTo是按照某种规则帮助我们完成排序,我们接着来看创建的过程的代码实现:

//创建赫夫曼树
public static Node createHuffmanTree(int[] arr){
    //为了方便操作,我们利用list集合
    List<Node> nodes = new ArrayList<>();
    //遍历数组来操作
    for (int value :arr){
        nodes.add(new Node(value));
    }
    //最后只剩下一个节点
    while (nodes.size() >1) {
        //排序:从小到大
        Collections.sort(nodes);
        //3.取出根节点权值最小的两棵二叉树
        //3.1.取出权值最小的节点(二叉树)
        Node leftNode = nodes.get(0);
        //3.2.取出权值第二小的节点(二叉树)
        Node rightNode = nodes.get(1);
        //3.3.构建一棵新的二叉树
        Node parent = new Node(leftNode.value + rightNode.value);
        parent.left = leftNode;
        parent.right = rightNode;
        //3.4.从arrayList中删除已经处理过的二叉树节点
        nodes.remove(leftNode);
        nodes.remove(rightNode);
        //3.5.将构建的二叉树添加到nodes中
        nodes.add(parent);
    }
    //返回赫夫曼树的最终的节点
    return nodes.get(0);
}

其实代码的实现不算太难,想看的可以自己看下,这里我打算采用的前序遍历的方式对我们创建的赫夫曼树完成遍历操作,首先来看前序遍历的代码编写:

 //写一个前序遍历的方法
public void preOrder(){
    System.out.println(this);
    if (this.left !=null){
        this.left.preOrder();
    }
    if (this.right !=null){
        this.right.preOrder();
    }
}

测试代码如下:

/**
 * 赫夫曼树
 */
public class HuffmanTree {
public static void main(String[] args) {
    int [] arr = {13,7,8,3,29,6,1};
    Node huffmanTree = createHuffmanTree(arr);

    preOrder(huffmanTree);

}

测试结果如下图所示:

测试结果.png

上述的测试结果和我们分析的结果是一致的,那么关于赫夫曼树的创建学习过程就到这了,完整代码请看git地址

• git地址: https://gitee.com/cblove_java/nacos_learning_demo