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]