자바 최 적 화 된 이 진 트 리 의 하 프 만 알고리즘 간단 한 구현

가장 좋 은 이 진 트 리 는 하 프 만 트 리 라 고도 부 릅 니 다.직 설 적 인 점 은 모든 노드 가 가중치 가 있 습 니 다.우 리 는 큰 값 을 뿌리 에서 가 깝 고 작은 값 을 뿌리 에서 멀리 하여 전체 가중치(대권 경로 길이)를 최소 화 하 는 것 입 니 다.
하 프 만 알고리즘 의 사상 은 위 에서 말 한 것 이 라 고 생각 합 니 다.그의 알고리즘 실현 방향 은 이 렇 습 니 다.
뿌리 결점 에서 가중치 가 가장 작은 두 개(정렬 과 관련 되 지만 저 는 이 실현 코드 가 엄격 한 순 서 를 하지 않 고 비교 만 합 니 다)를 합 쳐 새로운 뿌리 결점 을 다시 정렬 합 니 다(뽑 힌 두 개 는 자 연 스 럽 게 비 뿌리 결점 이 되 었 습 니 다).이렇게 순환 하여 합병 이 완 료 될 때 까지 우 리 는 가장 좋 은 이 진 트 리 인 하 프 만 나 무 를 얻 었 습 니 다.
설명:
(1)하 프 만 나 무 는 n 개의 잎 결점 이 있 으 면 n-1 개의 가지 결점 을 내 놓 을 수 있다.그래서 저 는 허 프 맨 트 리 라 는 허 프 맨 노드 형식 배열 을 정의 할 때 길 이 를 2*n-1 로 정의 합 니 다.
(2)여기 서 정렬 과 관련 된 것 은 잘 하지 못 했 고 실현 을 위해 이 루어 졌 을 뿐 나중에 천천히 보완 되 었 다.
(3)이론 적 으로 하 프 만 나 무 는 수치 에 만 국한 되 지 않 고 compare 만 할 수 있 는 것 이 아니 라 int 로 만 표시 해 야 한다.
다음은 코드:
우선 하프 만 나무 결점 을 정의 합 니 다.

public class HuffmanNode {
  
  private int weight = -1;
  
  private int parent = -1;
  
  private int left = -1;
  
  private int right = -1;

  public HuffmanNode(int weight) {
    super();
    this.weight = weight;
  }

  public HuffmanNode(int weight, int left, int right) {
    super();
    this.weight = weight;
    this.left = left;
    this.right = right;
  }

  public int getWeight() {
    return weight;
  }

  public void setWeight(int weight) {
    this.weight = weight;
  }

  public int getParent() {
    return parent;
  }

  public void setParent(int parent) {
    this.parent = parent;
  }

  public int getLeft() {
    return left;
  }

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

  public int getRight() {
    return right;
  }

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

  @Override
  public String toString() {
    return "HuffmanNode [weight=" + weight + ", parent=" + parent + ","
        + " left=" + left + ", right=" + right + "]";
  }

}

하프 만 나무의 이상 류 를 정의 하 세 요.

public class TreeException extends RuntimeException {
  
  private static final long serialVersionUID = 1L;

  public TreeException() {}

  public TreeException(String message) {
    super(message);
  }

}

인 코딩 실현(처리 가 그렇게 효율 적 이지 않 음)

public class HuffmanTree {
  
  protected HuffmanNode[] huffmanTree;
  
  public HuffmanTree(int[] leafs) {
    //      
    if (leafs.length <= 1) {
      throw new TreeException("        2，        ");
    }
    //       
    huffmanTree = new HuffmanNode[leafs.length*2-1];
    //  n          
    for (int i = 0; i < leafs.length; i++) {
      HuffmanNode node = new HuffmanNode(leafs[i]);
      huffmanTree[i] = node;
    }
    //            
    for (int i = leafs.length; i < huffmanTree.length; i++) {
      //           
      int miniNum_1 = selectMiniNum1();
      //           
      int miniNum_2 = selectMiniNum2();
      if (miniNum_1 == -1 || miniNum_2 == -1) {
        return;
      }
      //               
      HuffmanNode node = new HuffmanNode(huffmanTree[miniNum_1].getWeight() + 
          huffmanTree[miniNum_2].getWeight(), miniNum_1, miniNum_2);
      huffmanTree[i] = node;
      huffmanTree[miniNum_1].setParent(i);
      huffmanTree[miniNum_2].setParent(i);
    }
  }
  
  /**
   *            
   * @return
   */
  private int selectMiniNum1() {
    //   
    int min = -1;
    //     
    int index = -1;
    //          
    boolean flag = false;
    //    
    for (int i = 0; i < huffmanTree.length; i++) {
      //  、     ，    
      if (huffmanTree[i] == null || huffmanTree[i].getParent() != -1) {
        continue;
      } else if (!flag) {   //            
        //   
        min = huffmanTree[i].getWeight();
        index = i;
        //       min
        flag = true;
        //      
        continue;
      }
      int tempWeight = huffmanTree[i].getWeight();
      //    
      if (tempWeight < min) {
        min = tempWeight;
        index = i;
      }
    }
    return index;
  }
  
  /**
   *            
   * @return
   */
  private int selectMiniNum2() {
    //   
    int min = -1;
    //          
    boolean flag = false;
    //     （       ）
    int index = selectMiniNum1();
    //       ，        
    if (index == -1) {
      return -1;
    }
    //     
    int index2 = -1;
    //    
    for (int i = 0; i < huffmanTree.length; i++) {
      //     、  、     ，    
      if (index == i || huffmanTree[i] == null || huffmanTree[i].getParent() != -1) {
        continue;
      } else if (!flag) {   //            
        //   
        min = huffmanTree[i].getWeight();
        index2 = i;
        //       min
        flag = true;
        //      
        continue;
      }
      int tempWeight = huffmanTree[i].getWeight();
      //    
      if (tempWeight < min) {
        min = tempWeight;
        index2 = i;
      }
    }
    return index2;
  }

}

테스트 클래스 1

public class HuffmanTreeTester {

  public static void main(String[] args) {
    int[] leafs = {1, 3, 5, 6, 2, 22, 77, 4, 9};
    HuffmanTree tree = new HuffmanTree(leafs);
    HuffmanNode[] nodeList = tree.huffmanTree;
    for (HuffmanNode node : nodeList) {
      System.out.println(node);
    }
  }

}

테스트 결과 1
HuffmanNode [weight=1, parent=9, left=-1, right=-1]
HuffmanNode [weight=3, parent=10, left=-1, right=-1]
HuffmanNode [weight=5, parent=11, left=-1, right=-1]
HuffmanNode [weight=6, parent=12, left=-1, right=-1]
HuffmanNode [weight=2, parent=9, left=-1, right=-1]
HuffmanNode [weight=22, parent=15, left=-1, right=-1]
HuffmanNode [weight=77, parent=16, left=-1, right=-1]
HuffmanNode [weight=4, parent=11, left=-1, right=-1]
HuffmanNode [weight=9, parent=13, left=-1, right=-1]
HuffmanNode [weight=3, parent=10, left=0, right=4]
HuffmanNode [weight=6, parent=12, left=1, right=9]
HuffmanNode [weight=9, parent=13, left=7, right=2]
HuffmanNode [weight=12, parent=14, left=3, right=10]
HuffmanNode [weight=18, parent=14, left=8, right=11]
HuffmanNode [weight=30, parent=15, left=12, right=13]
HuffmanNode [weight=52, parent=16, left=5, right=14]
HuffmanNode [weight=129, parent=-1, left=15, right=6]
도형 표시:

테스트 클래스 2

public class HuffmanTreeTester {

  public static void main(String[] args) {
    int[] leafs = {2, 4, 5, 3};
    HuffmanTree tree = new HuffmanTree(leafs);
    HuffmanNode[] nodeList = tree.huffmanTree;
    for (HuffmanNode node : nodeList) {
      System.out.println(node);
    }
  }

}

테스트 결과 2
HuffmanNode [weight=2, parent=4, left=-1, right=-1]
HuffmanNode [weight=4, parent=5, left=-1, right=-1]
HuffmanNode [weight=5, parent=5, left=-1, right=-1]
HuffmanNode [weight=3, parent=4, left=-1, right=-1]
HuffmanNode [weight=5, parent=6, left=0, right=3]
HuffmanNode [weight=9, parent=6, left=1, right=2]
HuffmanNode [weight=14, parent=-1, left=4, right=5]
도형 표시:

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.