CompleteBinaryTree(완전이진탐색)

import java.util.ArrayDeque;
import java.util.Queue;

public class CompleteBinaryTree<T> { //완전이진트리 탐색
	
	private Object[] nodes;//(어떠한 타입의 데이터라도 허용하는)노드를 담을 배열 선언
	private int lastIndex; //마지막추가된 노드의 인덱스 정보
	private final int SIZE; //배열크기
	
	public CompleteBinaryTree(int size) {
		SIZE = size;
		nodes = new Object[size+1];  //0인덱스 사용 안함  ==> 인덱스와 노드번호를 일치시키기 위하여
	}
	
	//꽉찬상태 체크
    private boolean isFull() {
    	return lastIndex == SIZE;
    }
    
    //빈상태 체크
    private boolean isEmpty() {
    	return lastIndex == 0;
    }
	
	//데이터 추가
	public void add(T e) {
		
		//배열이 꽉찬 상태라면 그만!!
		if(isFull()) {
			System.out.println("포화상태입니다..");
			return;
		}
				
		nodes[++lastIndex] = e;
	}

	
	public void printTreeByPreOrder() {
		System.out.print("PreOrder :");
		printTreeByPreOrder(1); //1 ==> 루트노드
		System.out.println();
	}
	
    //전위순회(탐색) - 재귀호출 (DFS)
	private void printTreeByPreOrder(int current) { //current:부모노드!!
//		 1.current처리!
//		 2.왼쪽자식처리
//		 3.오른쪽자식처리
		
		//1.
		System.out.print(nodes[current]+" ");//현재노드 처리
		
		//2.
		if(current*2 <= lastIndex) //노드 범위내에서 재귀호출을 하자
		printTreeByPreOrder(current*2);
		
		//3.
		if(current*2+1 <= lastIndex)
		printTreeByPreOrder(current*2+1);
	}
	
	//============================= 중위 순회 ================================
	public void printTreeByInOrder() {
		System.out.print("InOrder :");
		printTreeByInOrder(1); //1 ==> 루트노드
		System.out.println();
	}
	
	//중위순회(탐색) - 재귀호출 (DFS)
	private void printTreeByInOrder(int current) { //current:부모노드!!
		 if(current > lastIndex) return;
//		 2.왼쪽자식처리
//		 1.current처리!
//		 3.오른쪽자식처리
		
		//2.
		printTreeByInOrder(current*2);
		
		//1.
		System.out.print(nodes[current]+" ");//현재노드 처리
		
		//3.
		printTreeByInOrder(current*2+1);
	}
	
//========================= 후위 순회 ===============================
	public void printTreeByPostOrder() {
		System.out.print("PostOrder :");
		printTreeByPostOrder(1); //1 ==> 루트노드
		System.out.println();
	}
	
    //후위순회(탐색) - 재귀호출 (DFS)
	private void printTreeByPostOrder(int current) { //current:부모노드!!
		 if(current > lastIndex) return;
//		 2.왼쪽자식처리
//		 3.오른쪽자식처리
//		 1.current처리!
		
		
		//2.
			printTreeByPostOrder(current*2);
		
		//3.
			printTreeByPostOrder(current*2+1);
		
		//1.
		System.out.print(nodes[current]+" ");//현재노드 처리
	}
	
	//큐를 통한 탐색 ==> BFS 탐색
	public void bfs() {
		Queue<Integer> queue = new ArrayDeque<Integer>();
		
		queue.offer(1);//루트노드가 시작점!!
		int current;
		
		while(!queue.isEmpty()) {//자식노드 추가!!
			current = queue.poll();
			
			//노드처리
			System.out.println(nodes[current]);
			
			//대기열에서 빠진 노드 정보를 가지고 == 자식 노드들 얻어오기 *2,  *2+1
			if(current*2 <= lastIndex)queue.offer(current*2); //왼쪽자식
			if(current*2+1 <= lastIndex)queue.offer(current*2+1);//오른쪽자식
			
		}
		
	}
	
}