java学习笔记——赫夫曼树（最优二叉树）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java学习笔记——赫夫曼树（最优二叉树），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2906字，纯文字阅读大概需要5分钟。

内容图文

目录

• 赫夫曼树的定义
• 与赫夫曼树相关的几个重要概念
• 构成赫夫曼树的步骤
• • 代码实现

赫夫曼树的定义

• 给定n个权值作为n个叶子节点，构建一个二叉树，若该树的带权路径长度（wpl - weight path length）
• 赫夫曼树是带权路径长度最短的树，权值较大的节点离根较近

与赫夫曼树相关的几个重要概念

• 路径：在一棵树中，从一个节点往下可以达到的孩子或孙子节点之间的通路，称为路径
• 路径长度：通路中分支的数目称为路径长度。第 n 层的节点到第 m 层节点的路径长度为 m-n（比如规定根节点的层数为1，那么从根节点到第L层节点的路径长度为L-1）
• 节点的权：若将树中的节点赋给一个有着特殊意义的数值，则这个数值叫做该节点的权
• 节点的带权路径长度:从根节点到该节点之间的路径长度与该节点的权的乘积
• 树的带权路径长度：所有叶子节点的带权路径长度之和（WPL），权值越大的节点离根节点越近的二叉树才是最优二叉树
• WPL最小的就是赫夫曼二叉树
  

构成赫夫曼树的步骤

• 给定一个序列{13,7,8,3,29,6,1}，要求转成一颗赫夫曼树：
  • 从小到大对数组进行排序，其中数组中的每一个数据都是一个节点，每个节点都可以看成是一个最简单的二叉树（没有左右子节点的二叉树）
  • 取出根节点权值最小的两颗二叉树（取出后从数组中删除）
  • 将取出的两颗二叉树组成一颗新的二叉树，该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
  • 再将这个新的二叉树放回到数组中，以根节点的权值大小再次排序，不断重复上面的步骤，直到数列中，所有的数据都被处理完毕，就得到一颗赫夫曼树
• 赫夫曼树的构建步骤视频讲解

代码实现

• Node类建立（创建树的节点类型）

public class Node implements Comparable<Node>{
    public int val;
    public Node left;
    public 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;    //this-o为从小到大排序，反过来为从大到小
    }
}

• 赫夫曼树类的建立

public class HuffmanTree {
    public Node root;
    public int[] arr;

    public HuffmanTree(int[] arr) {
        this.arr = arr;
        this.root = creatHuffmanTree(arr);
    }
	
	//构建赫夫曼树
    public Node creatHuffmanTree(int[] arr){
        if (arr.length == 0){
            return null;
        }
        if (arr.length < 2){
            return new Node(arr[0]);
        }

        //将数组中的元素都转换成节点，并添加到list中
        List<Node> list = new ArrayList<>();
        for (int i : arr) {
            list.add(new Node(i));
        }
        Collections.sort(list); //对list排序

        //循环最后list中只会有一个元素，即赫夫曼树的根节点
        while (list.size()>1){
            //将数组中权值最小的两个节点构成新的二叉树，该树的权为那两个节点的权值之和
            Node sub_root = new Node(list.get(0).val + list.get(1).val);
            sub_root.left = list.get(0);
            sub_root.right = list.get(1);

            //将拿出的两个节点从list中去除，并将新二叉树的根节点添加进去，然后排序
            //这里注意一定要先remove索引为 1 的元素，如果后remove它，那么在最后list中只剩2个元素的时候，先remove了索引为 1 的元素，此时list中就只剩一个元素了，此时如果list.remove(1)会产生索引越界异常
            list.remove(1);
            list.remove(0);
            list.add(sub_root);
            Collections.sort(list);
        }

        return list.get(0);
    }

	//前序遍历
    public void preList(Node root){
        if (root == null){
            System.out.println("二叉树为空！！");
            return;
        }

        System.out.println(root);

        if (root.left != null){
            preList(root.left);
        }
        if (root.right != null){
            preList(root.right);
        }
    }
}

内容总结

以上是互联网集市为您收集整理的java学习笔记——赫夫曼树（最优二叉树）全部内容，希望文章能够帮你解决java学习笔记——赫夫曼树（最优二叉树）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---