哈夫曼树

基本介绍

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

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

重要概念和举例说明

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

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

步骤

• 1 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
• 2 取出根节点权值最小的两颗二叉树
• 3 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
• 4 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

代码实现

​ 给你一个数列 {13, 7, 8, 3, 29, 6, 1}，要求转成一颗赫夫曼树.

package Tree;

import Sort.BubbleSort;
import Sort.QuickSort;

import java.util.regex.Pattern;

/**
 * @author yyq
 * @create 2021-11-06 14:25
 *
 * 创建哈夫曼树
 * 节点 数组 其中节点可能代表一个二叉树的根
 * 1 创建节点数组
 * 2 对节点数组进行排序
 * 3 选择最小的两个构成一个二叉树 并在加入节点数组
 * 4 重复上述步骤 直到数组长度唯一
 */
public class HuffmanTree {
    public static void main(String[] args) {
        int[] a={13, 7, 8, 3, 29, 6, 1};
        TreeNode<Integer> root = constructHuffmanTree(a);
        BinaryTree.preOrder(root);

    }


    public static TreeNode<Integer> constructHuffmanTree(int[] a){
        int l=a.length;
        int[] temp = a.clone();
        BubbleSort.bubbleSort(temp);
        //构建节点数组
        TreeNode<Integer>[] treeNodes=new TreeNode[l];
        for (int i = 0; i < l; i++) {
            treeNodes[i]=new TreeNode<Integer>(temp[i]);
        }

        while (true){
            //只剩下最后两个节点时结束 手动合成即可
            if(l==2) {
                int data=treeNodes[0].data+treeNodes[1].data;
                TreeNode parent=new TreeNode(data);
                parent.left=treeNodes[0];
                parent.right=treeNodes[1];
                return parent;
            }
            //选择最小的两个进行合成
            int data=treeNodes[0].data+treeNodes[1].data;
            TreeNode parent=new TreeNode(data);
            parent.left=treeNodes[0];
            parent.right=treeNodes[1];
            //加入数组并进行排序
            insertTreeNodes(treeNodes,parent,l);
            l--;
        }

    }
    //将合成的新节点加入数组,加入后数组有序 此时0 1应该为无用项 它两刚刚合成成新的节点parent
    public static void insertTreeNodes(TreeNode<Integer>[] treeNodes,TreeNode<Integer> node,int l){
        //首先把所有的往前移一位
        for(int i=1;i<l-1;i++){
            treeNodes[i]=treeNodes[i+1];
        }
        //现在长度其实缩小到l-1 边比较边移动
        for (int i = 1; i < l-1; i++) {
            //如果node比后面的节点大，后面的节点向前平移
            if(node.data>treeNodes[i].data){
                treeNodes[i-1]=treeNodes[i];
            }
            //如果node比后面的节点小 直接插入即可
            if(node.data<=treeNodes[i].data){
                treeNodes[i-1]=node;
                break;
            }
            //它是最大值 放在末尾
            if(i==l-2){
                treeNodes[l-2]=node;
            }
        }


    }
}