JAVA数据结构与算法实现-哈夫曼树

哈夫曼树，是一种特殊的二叉树，由一个叫做哈夫曼的人实现出来的，由于他的一致性所以数据统一。在这里我使用数组实现二叉树的原理。

在这里我们首先创建一个二叉树节点的类，名为point：

/**
* Created by jim_D on 2018/10/11.
*/
public class point {

int info;//定义节点的值
point left;//节点的左子树
point right;//节点右子树

point(int info){//节点的构造方法，要求必须要有默认值存入
this.info=info;
}

public int getInfo() {
return info;
}

public void setInfo(int info) {
this.info = info;
}

public point getLeft() {
return left;
}

public void setLeft(point left) {
this.left = left;
}

public point getRight() {
return right;
}

public void setRight(point right) {
this.right = right;
}
}

           

数组转换为哈夫曼树

创建哈夫曼树的方法类：

point[] list;//创建一个存放二叉树节点的数组
int[] arr;//创建一个用于存放数组的类
Tree(int[] arr){//构造方法要求创建哈夫曼树之前必须要将数组存入
this.arr=arr;
list = new point[arr.length];//由数组的长度确定节点数组的长度
}

public point getTree(){
for(int i=0;i<arr.length;i++){
list[i]=new point(arr[i]);//遍历数组将数组的挨个值创建为二叉树节点存入节点数组
}
return makeTree(list);//调用创建哈夫曼树的方法，将刚刚通过数组创建的节点数组传入该方法
}

public point makeTree(point[] list){
list = paixu(list);//调用排序的方法
point left = list[0];//通过排序后将该节点的两个属性的值最小的两哥
point right = list[1];
point p = new point(left.getInfo()+right.getInfo());
p.setLeft(left);//创建新节点将之前的两节点设置为这两个节点的左右子树
p.setRight(right);
for(int i=1;i<list.length;i++){
list[i-1]=list[i];//将节点数组往前移一位
}
list = Arrays.copyOf(list,list.length-1);//数组缩容
list[0]=p;//将新创建的节点设置为数组的第一个节点
if(list.length>1){
return makeTree(list);//递归调用该方法，直到数组里面只剩一个节点
}else{
return p;
}
}

public point[] paixu(point[] list){//使用for循环通过节点的info属性排序

for(int i=0;i<list.length;i++){
for(int j=0;j<list.length;j++){
if(list[i].getInfo()<list[j].getInfo()){
point p=list[i];
list[i]=list[j];
list[j]=p;
}
}
}
return list;
}

           

方法测试：

public static void main(String[] args){
int[] arr = {8,4,5,6,3,2,1,7,9};

Tree t = new Tree(arr);

point p = t.getTree();
showAll(p);

}

public static void showAll(point p){//先序递归调用查询
System.out.println(p.getInfo());
if(p.getLeft()!=null){
showAll(p.getLeft());
}
if(p.getRight()!=null){
showAll(p.getRight());
}
}

           

测试结果：

45
18
9
4
5
9
27
12
6
6
3
3
1
2
15
7
8
           

哈夫曼树转换为数组

创建哈夫曼树方法类：

public void getArr(point p){
        List<Integer> list = new ArrayList<Integer>();
        makeArr(p,list);
        System.out.println(list.toString());
    }

    public void makeArr(point p,List<Integer> list){//使用递归的方法将哈夫曼树的所有子节点存入数组
        if(p.getRight()==null && p.getLeft()==null){
            list.add(p.getInfo());
        }
        if(p.getLeft()!=null){
            makeArr(p.getLeft(),list);
        }
        if(p.getRight()!=null){
            makeArr(p.getRight(),list);
        }

    }
           

测试：

public static void main(String[] args){
        int[] arr = {8,4,5,6,3,2,1,7,9};

        Tree t = new Tree(arr);

        point p = t.getTree();
        t.getArr(p);

    }
           

结果：

[4, 5, 9, 6, 3, 1, 2, 7, 8]