// 第 14 周 – 用数组表示的二叉树：A[1] 是根，i 的孩子是 2i 和 2i+1，父结点是 i/2
// 运行：java ArrayTree.java
public class ArrayTree {

    // 不使用第 0 个元素，这样下标公式比较简单（与伪代码一致）
    static final Character[] A = { null, 'A', 'B', 'C', 'D', 'E', null, 'G' };
    //            A(1)
    //          /      \
    //       B(2)      C(3)
    //       /  \         \
    //    D(4)  E(5)      G(7)

    static boolean exists(int i) { return i < A.length && A[i] != null; }

    static void preorder(int i, StringBuilder out) {
        if (!exists(i)) return;
        out.append(A[i]).append(' ');
        preorder(2 * i, out);       // 左孩子
        preorder(2 * i + 1, out);   // 右孩子
    }

    static void inorder(int i, StringBuilder out) {
        if (!exists(i)) return;
        inorder(2 * i, out);
        out.append(A[i]).append(' ');
        inorder(2 * i + 1, out);
    }

    static int height(int i) { return exists(i) ? 1 + Math.max(height(2 * i), height(2 * i + 1)) : -1; }

    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();
        preorder(1, sb);
        System.out.println("preorder: " + sb);
        sb.setLength(0);
        inorder(1, sb);
        System.out.println("inorder:  " + sb);
        System.out.println("height: " + height(1));
        for (int i = 1; i < A.length; i++) {
            if (A[i] == null) continue;
            System.out.printf("  A[%d] = %c, parent: %s, left: %s, right: %s%n", i, A[i],
                    i > 1 ? A[i / 2] : "-", exists(2 * i) ? A[2 * i] : "-", exists(2 * i + 1) ? A[2 * i + 1] : "-");
        }
        // 在数组表示中层序遍历很简单：从左到右遍历数组
        System.out.print("level order: ");
        for (int i = 1; i < A.length; i++) if (A[i] != null) System.out.print(A[i] + " ");
        System.out.println();
    }
}