자바 데이터 구조의 하프 만 트 리 개술 및 실현

1.하프 만 나무 와 관련 된 개념
콘 셉 트
속뜻
1.경로
나무 속 의 한 결점 에서 다른 결점 의 가지 로 구 성 된 노선
2.경로 길이
경로 상의 분기 수
3.나무의 경로 길이
길이 가 뿌리 에서 각 노드 까지 의 경로 길이 의 합
4.대역 권 경로 길이
결점 은 가중치 가 있 는데 이 결점 에서 뿌리 사이 의 경로 길 이 를 결점 의 가중치 로 곱 하면 바로 이 결점 의 대역 권 경로 길이 이다.
5.트 리 의 대역 권 경로 길이
나무 에 있 는 모든 잎 결점 의 대역 권 경로 길이 의 합
2.하프 만 나무 란 무엇 인가
정의:
4.567917.n 개의 가중치 를 n 개의 잎 결점 으로 정 하고 구 조 된 띠 권 경로 길이(WPL)의 가장 짧 은 이 진 트 리 는 하 프 만 트 리()라 고도 부 르 며 가장 좋 은 이 진 트 리 라 고도 부른다.
WPL:Weighted Path Length of Tree 나무의 권한 경로 길이하프 만 나무의 특징:
1.가중치 가 큰 결점 일수 록 뿌리 노드 와 가깝다.
2.나무 에 1 의 결점 이 없고 하프 만 나무의 도 는 0 또는 1 에 불과 하 다.
3.권한 경로 길이 가 가장 짧 은 이 진 트 리;
다음 그림 세 개의 이 진 트 리 를 판단 하 겠 습 니 다.그것 은 하 프 만 나무 입 니까?
4.567917.당연히 WPL 에서 가장 작은 나무 입 니 다.즉,중간의 이 진 트 리 는..그렇다면 우 리 는 어떻게 수 동 으로 하프 만 나 무 를 만 들 었 을 까?
3.하 프 만 나무의 구조 방법
하프 만 나 무 를 만 드 는 절차:
1.모든 결점 의 가중치 를 작은 것 에서 큰 것 으로 정렬 합 니 다.
2.뿌리 노드 의 가중치 가 가장 작은 이 진 트 리 두 그루 꺼 내기;
3.새로운 이 진 트 리 를 구성 합 니 다.이 과 의 새로운 이 진 트 리 의 뿌리 노드 의 가중치 는 앞의 이 진 트 리 의 가중치 와
4.이 새로운 이 진 트 리 를 뿌리 노드 의 가중치 크기 로 정렬 하고 1-2-3-4 절 차 를 반복 하 며 주어진 서열 의 소유권 값 이 처 리 될 때 까지 우 리 는 하프 만 트 리 를 얻 었 다.
[도해 분석 구조 과정]
다음은 서열{13,7,8,3}을 예 로 들 어 하 프 만 나 무 를 구성 하 는 과정 을 도해 한다.
먼저 서열 을 오름차 순 으로 배열 하여{3,7,8,13}을 얻 을 수 있 습 니 다.

가중치 가 가장 작은 두 개의 결점 3,7 을 꺼 내 이 진 트 리 를 구성 하고 뿌리 노드 는 가중치 가 10 인 결점 이다.

원 시퀀스 에서 2 단계 에서 사 용 된 3 과 7 을 제거 하고 새로운 노드 값 10 을 시퀀스 에 넣 고 정렬 하여{8,10,13}을 얻 습 니 다.

가중치 가 가장 작은 두 노드 8,10 을 다시 꺼 내 서 뿌리 노드 가 18 인 이 진 트 리 를 구성 한 다음 에 우 리 는 서열 중의 8,10 을 제거 하고 18 을 서열 에 추가 하고 정렬 하여{13,18}을 얻 었 다.

서열{13,18}을 꺼 내 새로운 이 진 트 리 를 구성 합 니 다.가중치 는 31 입 니 다.이때 서열 에는 31 점 만 남 았 습 니 다.그 는 이 하 프 만 나무의 뿌리 노드 입 니 다.

이로써{13,7,8,3}의 하프 만 트 리 구축 이 완료 되 었 습 니 다.
4.하 프 만 트 리 의 코드 구현
결점 류

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();
    }

    //        
    public void setLeftNode(HTreeNode node){
        this.leftNode = node;
    }
    public void setRightNode(HTreeNode node){
        this.rightNode = node;
    }
    //     toString()
    public HTreeNode(int weight){
        this.weight = weight;
    }
    public String toString(){
        return "Node{weight: "+weight+"}";
    }
    //           
//    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{
    //       :
    //1.           buildHuffumanTree(int[] arr)
    //2.          (     )
    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.                
        //2.            
        for(int x : arr){
            nodesList.add(new HTreeNode(x));
        }
        while(nodesList.size() > 1){
            //3.          ,             
            Collections.sort(nodesList);
            // (   ,       comparable    copareTo  ),      ?      !
            //4.                    ,                   
            HTreeNode leftNode = nodesList.get(0);
            HTreeNode rightNode = nodesList.get(1);

            HTreeNode parent = new HTreeNode(leftNode.weight + rightNode.weight);
                          (      )
            //                ,                   
            parent.setLeftNode(leftNode);
            parent.setRightNode(rightNode);
            //5.              ,        
            nodesList.remove(leftNode);
            nodesList.remove(rightNode);
            nodesList.add(parent);
        }
        //6.            
        return nodesList.get(0);
    }
    //        
    public static void preOrder(HTreeNode root){
        if(root != null){
            root.preOrder();
        }else{
            System.out.println("     ! ");
        }
    }
}

자바 데이터 구조의 하프 만 트 리 개술 및 실현 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 하프 만 트 리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!