BinaryArrayTree Traversal

BinaryArrayTree.java

import java.io.*;
import java.util.*;

public class BinaryArrayTree {

    private List<Integer> list = new ArrayList<>();

    public BinaryArrayTree(int n) {
        list.add(null);
        for (int i = 1; i <= n; i++)
            list.add(i);
    }

    public BinaryArrayTree() {
        list.add(null);
    }

    public void push(int n) {
        push(1, n);
    }
    private void push(int idx, int n) {
        if (idx >= list.size()) {
            while (list.size() < idx * 2)
                list.add(null);
        }
        if (list.get(idx) == null) {
            list.set(idx, n);
            return;
        }
        if (list.get(idx) < n)
            push(2 * idx + 1, n);
        else
            push(2 * idx, n);
    }

    public void levelorder() {
        for (int i = 1; i < list.size(); i++)
            System.out.print(list.get(i) + " ");
        System.out.println();
    }

    public void preorder() {
        preorder(1);
        System.out.println();
    }
    private void preorder(int idx) {
        if (idx >= list.size())
            return;
        // 먼저 방문 -> 출력
        System.out.print(list.get(idx) + " ");
        // 좌측자식 idx * 2
        preorder(idx * 2);
        // 우측자식
        preorder(idx * 2 + 1);
    }

    public void inorder() {
        inorder(1);
        System.out.println();
    }
    private void inorder(int idx) {
        if (idx >= list.size())
            return;

        inorder(idx * 2);
        System.out.print(list.get(idx) + " ");
        inorder(idx * 2 + 1);
    }

    public void postorder() {
        postorder(1);
        System.out.println();
    }
    private void postorder(int idx) {
        if (idx >= list.size())
            return;

        postorder(idx * 2);
        postorder(idx * 2 + 1);
        System.out.print(list.get(idx) + " ");
    }

    /* 트리 출력 */
    public void printTree() {
        printTree(1, "", "");
    }
    private void printTree(int idx, String front, String child) {
        if (idx >= list.size()) {
            if (idx - 1 < list.size()) {
                System.out.println(front + "X");
            }
            return;
        }

        System.out.println(front + list.get(idx));

        printTree(2 * idx + 1, child + "├── ", child + "│  ");
        printTree(2 * idx, child + "└── ", child + "   ");
    }

    public void run() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        BinaryArrayTree bt = new BinaryArrayTree(n);
        bt.preorder();
        bt.inorder();
        bt.postorder();
        bt.levelorder();
        bt.printTree();
    }

    /* null 포함된 트리 출력 */
    public void printAddTree() {
        printAddTree(1, "", "");
    }
    private void printAddTree(int idx, String front, String child) {
        if (idx >= list.size())
            return;
        if (list.get(idx) == null) {
            if ((idx % 2 == 1 && list.get(idx - 1) != null) || (idx % 2 == 0 && list.get(idx + 1) != null))
                System.out.println(front + "x");
            return;
        }

        System.out.println(front + list.get(idx));

        printAddTree(2 * idx + 1, child + "├── ", child + "│  ");
        printAddTree(2 * idx, child + "└── ", child + "   ");
    }

    public void runAddMode() throws Exception {
        BinaryArrayTree bt = new BinaryArrayTree();
        while (true) {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            if (n == -1)
                break;

            bt.push(n);
            bt.printAddTree();
        }
    }
    public static void main(String[] args) throws Exception {
        new BinaryArrayTree().runAddMode();
    }
}