package DataStrcture.huffmantreedemo;

public class HTreeNode implements Comparable<HTreeNode>{
    //
    public HTreeNode leftNode;
    public HTreeNode rightNode;
    public int weight;

    // 前序遍歷
    public void preOrder(){

        System.out.println(this);

        if(this.leftNode != null) this.leftNode.preOrder();

        if(this.rightNode != null) this.rightNode.preOrder();
    }

    // 設(shè)置左右子節(jié)點(diǎn)
    public void setLeftNode(HTreeNode node){
        this.leftNode = node;
    }
    public void setRightNode(HTreeNode node){
        this.rightNode = node;
    }
    //構(gòu)造方法和toString()
    public HTreeNode(int weight){
        this.weight = weight;
    }
    public String toString(){
        return "Node{weight: "+weight+"}";
    }
    //根據(jù)權(quán)值對(duì)結(jié)點(diǎn)進(jìn)行排序
//    public int compareTo(Object obj){
//        return this.weight - ((HTreeNode)(obj)).weight;
//    }
    public int compareTo(HTreeNode node){
        return this.weight - node.weight;
    }
}

package DataStrcture.huffmantreedemo;

import java.util.ArrayList;
import java.util.Collections;

public class HuffmanTree{
    //哈夫曼樹的實(shí)現(xiàn):
    //1. 構(gòu)建哈夫曼樹的方法 buildHuffumanTree(int[] arr)
    //2. 對(duì)哈夫曼樹進(jìn)行遍歷(二叉樹遍歷)
    public static void main(String[] args) {
        int[] arr = {13,7,8,3,29,6,1};
        HTreeNode hTreeNode = buildHuffmanTree(arr);
        preOrder(hTreeNode);
    }
    public static HTreeNode buildHuffmanTree(int[] arr){
        //
        ArrayList<HTreeNode> nodesList = new ArrayList<HTreeNode>();
        //1. 把存放權(quán)值的數(shù)組拿出來構(gòu)建結(jié)點(diǎn)
        //2. 把這些節(jié)點(diǎn)存放到集合中
        for(int x : arr){
            nodesList.add(new HTreeNode(x));
        }
        while(nodesList.size() > 1){
            //3. 利用集合的排序方法,可以根據(jù)權(quán)值對(duì)結(jié)點(diǎn)進(jìn)行排序
            Collections.sort(nodesList);
            // (當(dāng)然了, 我們需要實(shí)現(xiàn)comparable接口中的copareTo方法), 在哪實(shí)現(xiàn)的? 在結(jié)點(diǎn)類中!
            //4. 不斷的循環(huán)從集合中取出兩個(gè)結(jié)點(diǎn)進(jìn)行相加, 直到集合中只剩下一個(gè)結(jié)點(diǎn)才會(huì)終止循環(huán)
            HTreeNode leftNode = nodesList.get(0);
            HTreeNode rightNode = nodesList.get(1);

            HTreeNode parent = new HTreeNode(leftNode.weight + rightNode.weight);
            建立父節(jié)點(diǎn)和左右子節(jié)點(diǎn)的關(guān)系(千萬不要忘了)
            //因?yàn)槲覀冸m說是父節(jié)點(diǎn)和左右子節(jié)點(diǎn), 還是要實(shí)實(shí)在在的于內(nèi)存中體現(xiàn)出來的哈
            parent.setLeftNode(leftNode);
            parent.setRightNode(rightNode);
            //5.從結(jié)合中移除用過的左右子節(jié)點(diǎn), 添加父節(jié)點(diǎn)進(jìn)去
            nodesList.remove(leftNode);
            nodesList.remove(rightNode);
            nodesList.add(parent);
        }
        //6. 返回一個(gè)最終的唯一結(jié)點(diǎn)
        return nodesList.get(0);
    }
    //前序遍歷哈夫曼樹
    public static void preOrder(HTreeNode root){
        if(root != null){
            root.preOrder();
        }else{
            System.out.println("二叉樹為空! ");
        }
    }
}