数据结构与算法Java版——哈夫曼树

小咪咪 2022-06-13 03:50 114阅读 0赞

哈夫曼树也称最优二叉树，是二叉树中的一种应用，它是权数路径最短的树，在信息检索中比较常用。

这个学期学了数据结构这本书，所以我打算用Java实现其中表，队，栈，树。如果你有兴趣可以持续关注我后续操作。我的个人博客为[我的博客][Link 1]

**哈夫曼树定义：给定一组具有确定权值的叶子节点，可以构造出不同的二叉树，将其中带权路径长度最小的二叉树称为哈夫曼树。**

哈夫曼树的实现的基本思想（书上的定义太多，这里我自己简化以下）：

**1. 我们自己创建一个节点集合，把每个节点初始化，并且权数要赋值。**  
**2. 选择节点集合中权值最小的两个节点，将这两个节点分别作为左子树和右子树，生成一颗新的二叉树，这个二叉树根节点权值就是选出的两个节点的权值的和。**  
**3. 在集合删除（2）中选择出来的两个节点，再把新生成的节点加入集合中。**  
**4. 重复（2）、（3），直到集合中只有一棵二叉树时，这个二叉树就是哈夫曼树。**

![这里写图片描述][57028932.jpg]

这里仍然用的二叉链表实现的二叉树，所以先创建Node类

class Node<T>{
        T data; //数据
        double quanShu; //权数
        Node lChild;    //左子树
        Node rChild;    //右子树
    
        public Node(T data, double quanShu) {
            super();
            this.data = data;
            this.quanShu = quanShu;
        }
    
        @Override
        public String toString() {
            return "Node["+data+" "+quanShu+"]";
        }
    
    }

创建哈夫曼树类并实现一系列方法：

public class HaFuManTree {
    
        //创建哈夫曼树
        public Node createHaFuManTree(List<Node> nodes){
            //节点元素大于或者等于2时继续循环
            while(nodes.size()>1)
            {
                //升序排序
                sort(nodes);
                //获得最小的两位节点
                Node lChild=nodes.get(0);
                Node rChild=nodes.get(1);
                //将最小的两个节点"结合"
                Node parent=new Node(null, lChild.quanShu+rChild.quanShu);
                parent.lChild=lChild;
                parent.rChild=rChild;
                //删除已经结合的两个节点
                nodes.remove(0);
                nodes.remove(0);
                //添加生成的节点
                nodes.add(parent);
            }
            return nodes.get(0);    //返回根节点
        }   
    
        //冒泡排序，将nodes按照权数升序排序
        public List<Node> sort(List<Node> nodes){
            for(int i=0;i<nodes.size();i++)
            {
                for(int j=i;j<nodes.size();j++)
                {
                    if(nodes.get(i).quanShu>nodes.get(j).quanShu)
                    {
                        Node node = nodes.get(i);
                        nodes.set(i,nodes.get(j));
                        nodes.set(j, node);
                    }
                }
            }
            return nodes;
        }
    
        //层序遍历，利用队实现
        public void levelTraversal(Node root){
            //创建队
            Queue q=new LinkedList<>();
            //添加根节点
            q.add(root);
            while(!q.isEmpty()){
                //第一个元素出队
                Node node=(Node) q.poll();
                System.out.print(node+" ");
                if(node.lChild!=null)
                    q.add(node.lChild);
                if(node.rChild!=null)
                    q.add(node.rChild); 
            }
        }
    
        //获得哈夫曼树带权数路径长度
        public double getPathNum(Node root,int height){
            if(root==null){
                return 0;
            }else{
                if(root.lChild==null&&root.rChild==null){
                    return root.quanShu*height;
                }else{
                    return getPathNum(root.lChild, height+1)+getPathNum(root.rChild, height+1);
                }
            }
        }
    }

以上代码就实现了哈夫曼树了，在这个过程中，个人觉得最麻烦的是递归，容易晕，不过递归最重要的就是两点：

**1. 找重复处理的逻辑**  
**2. 找结束处理的逻辑**

如果递归仍然理不清楚可以用笔画画，盘出逻辑，这样会比较清晰。

最后贴上自己的main方法的代码和截图啦

public static void main(String[] args) {
            List<Node> nodes=new ArrayList<>();
            nodes.add(new Node("A", 6));
            nodes.add(new Node("B", 20));
            nodes.add(new Node("C", 31));
            nodes.add(new Node("D", 2));
            nodes.add(new Node("E", 12));
            nodes.add(new Node("F", 25));
            nodes.add(new Node("G", 10));
            HaFuManTree fuManTree=new HaFuManTree();
            Node root = fuManTree.createHaFuManTree(nodes);
            fuManTree.levelTraversal(root);
            System.out.println();
            System.out.println("哈夫曼路径长度为："+fuManTree.getPathNum(root, 0));
    }

今天的内容就到此结束啦，有兴趣的小伙伴可以自己手动实现下。  
![这里写图片描述][27525600.jpg]

[Link 1]: http://xichangblog.com
[57028932.jpg]: http://or0um8wrx.bkt.clouddn.com/17-6-26/57028932.jpg
[27525600.jpg]: http://or0um8wrx.bkt.clouddn.com/17-6-26/27525600.jpg