class CompleteBinaryTree {
    private char[] nodes;         // 트리의 노드
    private final int SIZE;       // 배열의 사이즈 고정
    private int lastIndex;        // 마지막에 추가된 노드의 인덱스

    public CompleteBinaryTree(int size) {
        this.SIZE = size;
        nodes = new char[SIZE+1];          // 1 ~ SIZE 번의 노드들을 저장하는 배열
    }

    public void add(char c) {
        if (lastIndex == SIZE) return;     // 배열 포화 상태
        nodes[++latIndex] = c;             // 배열에 트리 노드 추가
    }
}

// 트리의 노드
class Node {
    char data;         // 데이터 필드
    Node left;         // 왼쪽 자식 노드 링크 필드
    Node right;        // 오른쪽 자식 노드 링크 필드

    public Node(char data) {
        this.data = data;
        left = null;             // 리프 노드를 위한 초기화
        right = null;            // 리프 노드를 위한 초기화
    }
}

// 완전 이진 트리
class LinkedCompleteBinaryTree {
    Node[] binaryTree;

    public LinkedCompleteBinaryTree(int nodeCnt) {
        binaryTree = new Node[nodeCnt+1];                 // 노드 개수 + 1
    }

    public void add(int nodeCnt) {
        for (int i=1; i<=nodeCnt; i++) {
            binaryTree[i] = new Node(i);                  // 노드 생성 및 데이터 삽입
        }

        for (int i=1; i<=nodeCnt/2; i++) {
            binaryTree[i].left = binaryTree[2*i];         // 왼쪽 자식 노드 연결
            binaryTree[i].right = binaryTree[2*i+1];      // 오늘쪽 자식 노드 연결
        }
    }
}

public void bfs() {
    Queue<Integer> q = new LinkedList<>();      // 탐색을 기다리는 노드 저장
    q.offer(1);       // 루트 노드의 인덱스

    int level = 0, size = 0;

    while(!q.isEmpty()) {
        size = q.size();        // 현재 높이(너비)에서의 모든 노드 개수

        while(size-->0) {       // 높이 별 노드들을 단계적으로 탐색할 수 있음
            int current = q.poll();
            
            System.out.println(current + " ");

            // 왼쪽 자식 노드 유효성 검사 후 큐에 삽입
            if (current*2 <= lastIndex) q.offer(current*2);
            // 오른쪽 자식 노드 유효성 검사 후 큐에 삽입
            if (current*2+1 <= lastIndex) q.offer(current*2+1);
        }

        level++;     // 현재 높이, 한 높이(너비) 별 탐색이 끝나면 크기 하나씩 증가
    }
}

public void dfs(int current) {
    System.out.println(current + " ");      // 전위 순회 dfs로, 중위, 후위 순위의 경우 현재 라인의 위치만 자식 노드 중간과 마지막으로 바꿔주면 됨

    // 왼쪽 자식 노드 유효성 검사 후 재귀적 탐색
    if (current*2 <= lastIndex) dfs(current*2);
    // 오른쪽 자식 노드 유효성 검사 후 재귀적 탐색
    if (current*2+1 <= lastIndex) dfs(current*2+1);
}

public void dfsByPreOrder() {
    System.out.print("Preorder : ");
    dfsByPreOrder(1);
    System.out.println();
}
	
private void dfsByPreOrder(int current) {
    // 현재 노드 처리
    System.out.print(nodes[current] + " ");
    // 왼쪽 자식 노드 방문
    if (current*2<=lastIndex) dfsByPreOrder(current*2);
    // 오른쪽 자식 노드 방문
    if (current*2+1<=lastIndex) dfsByPreOrder(current*2+1);
}

public void dfsByInOrder() {
    System.out.print("Inorder : ");
    dfsByInOrder(1);
    System.out.println();
}

private void dfsByInOrder(int current) {
    // 왼쪽 자식 노드 방문
    if (current*2<=lastIndex) dfsByInOrder(current*2);
    // 현재 노드 처리
    System.out.print(nodes[current] + " ");
    // 오른쪽 자식 노드 방문
    if (current*2+1<=lastIndex) dfsByInOrder(current*2+1);
}

public void dfsByPostOrder() {
    System.out.print("Postorder : ");
    dfsByPostOrder(1);
    System.out.println();
}

private void dfsByPostOrder(int current) {
    // 왼쪽 자식 노드 방문
    if (current*2<=lastIndex) dfsByPostOrder(current*2);
    // 오른쪽 자식 노드 방문
    if (current*2+1<=lastIndex) dfsByPostOrder(current*2+1);
    // 현재 노드 처리
    System.out.print(nodes[current] + " ");
}