채소 새:하프 만 나무 와 하프 만 코딩

드디어 하프 만 트 리 와 하프 만 인 코딩 을 마 쳤 습 니 다~
 
하프 만 나 무 는 가장 좋 은 이 진 트 리 다.
 
지난번 검색 한 이 진 트 리 와 마찬가지 로 하프 만 트 리 도 특정한 구조 규칙 이 있 습 니 다.
 
1.하프 만 트 리 에 저장 할 데 이 터 를 각각 트 리 만 들 기
 
2.이 트 리 들 을 크기 순 으로 정렬 합 니 다(자바 에 서 는 우선 대기 열 Priority Queue 를 사용 하 는 것 이 매우 편리 합 니 다)
 
3.가장 작은 나무 두 개 를 가서 그들 을 한데 모 으 고 합 친 나 무 를 대열 에 다시 놓 아 줍 니 다.이렇게 반복 합 니 다..................................................
 
4.마지막 남 은 나 무 를 뿌리 노드 로 설정 합 니 다.
 
이렇게 해서 하프 만 나 무 는 구조 가 완성 되 었 습 니 다~
 
검사 방법 은 하프 만 나무의 모든 잎 결점 의 인 코딩 을 모두 지 는 것 이다.왼쪽으로 가면 0 이 고 오른쪽으로 가면 1 이다.(자신의 규정 에 따라)
 
그리고 코드 에 따라 나 무 를 그 려 서 검사~
 
우선 노드 클래스:

/**
 *        
 * @author Micro
 *
 */
public class HafNode implements Comparable<HafNode>{
	private HafNode father;
	private HafNode left;
	private HafNode right;
	private int num;
	
	//     
	public HafNode (int num) {
		this.num=num;
	}
	
	
	public HafNode getFather() {
		return father;
	}
	public void setFather(HafNode father) {
		this.father = father;
	}
	public HafNode getLeft() {
		return left;
	}
	public void setLeft(HafNode left) {
		this.left = left;
	}
	public HafNode getRight() {
		return right;
	}
	public void setRight(HafNode right) {
		this.right = right;
	}
	public int getNum() {
		return num;
	}
	public void setNum(int i) {
		this.num = i;
	}

	//        
	@Override
	public int compareTo(HafNode o) {
		//          
		int P = o.getNum();
		return num-P;
	}
}

 
 그 다음 에 나 무 를 만 드 는 과정 과 하 프 만 인 코딩 을 출력 합 니 다.
 

import java.util.PriorityQueue;

/**
 *                    
 * 
 * @author Micro
 * 
 */
public class HafTest {

	//      
	private static HafNode root;

	//     
	public static void main(String[] args) {
		//       
		int[] a = { 1, 4, 3, 5, 6 ,4,6,7,6};
		//       
		PriorityQueue<HafNode> queue = new PriorityQueue<HafNode>();
		HafTest ht = new HafTest();
		//           
		for (int i = 0; i < a.length; i++) {
			HafNode hf = new HafNode(a[i]);
			queue.add(hf);
		}
		ht.HafTree(queue);
		String Code = "";
		ht.print(root, Code);
	}

	//       
	public void HafTree(PriorityQueue<HafNode> queue) {
		while (queue.size() > 1) {
			HafNode min1, min2;
			min1 = queue.poll();
			min2 = queue.poll();
			//        
			HafNode result = new HafNode(min1.getNum() + min2.getNum());
			result.setLeft(min1);
			result.setRight(min2);
			min1.setFather(result);
			min2.setFather(result);
			queue.add(result);
		}
		root = queue.peek();
	}

	//      
	public void print(HafNode a, String Code) {

		if (a.getLeft() == null && a.getRight() == null) {
			System.out.println(a.getNum() + "       ：" + Code);
		}
		if (a.getLeft() != null) {
			print(a.getLeft(), Code + '0');
		}
		if (a.getRight() != null) {
			print(a.getRight(), Code + '1');
		}
	}
}

 
출력 결과:
 
4 의 하프 만 인 코딩:000
1 의 하프 만 인 코딩:0010
3 의 하프 만 인 코딩:0011
4 의 하프 만 인 코딩:010
5 의 하프 만 인 코딩:011
6 의 하프 만 인 코딩:100
6 의 하프 만 인 코딩:101
6 의 하프 만 인 코딩:110
7 의 하프 만 인 코딩:111
음~~틀 리 지 않 았 어~~
 
이렇게 해서 가장 기본 적 인 하프 만 트 리 가 완성 되 었 습 니 다.다음은 이 트 리 를 이용 하여 파일 의 압축 을 실현 하 는 것 입 니 다.화 이 팅~~~