[DataStructure]BinaryTree(二元樹)

二元樹可以利用連結串列或陣列來表示

鏈結串列可以直接定義parent、left、right三種變數來紀錄父節點和子節點
陣列擺放節點有一定的公式，且陣列[0]不使用

父節點 = floor(index / 2)
左子節點 = index * 2
右子節點 = index * 2 + 1

Java陣列二元樹走訪

public class btree {
    private static int [] tree_arr = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    public static void main(String [] argv) {
        btree.preorder(1);
        System.out.println();
        btree.inorder(1);
        System.out.println();
        btree.postorder(1);
    }

    //前序 樹根 > 左子樹 > 右子樹(DFS深度優先)
    public static void preorder(int index) {
        if (index < tree_arr.length) {
            System.out.println(tree_arr[index]);
            btree.preorder(index * 2);
            btree.preorder(index * 2 + 1);
        }
    }

    //中序 左子樹 > 樹根 > 右子樹
    public static void inorder(int index) {
        if (index < tree_arr.length) {
            btree.preorder(index * 2);
            System.out.println(tree_arr[index]);
            btree.preorder(index * 2 + 1);
        }
    }

    //後序 左子樹 > 右子樹 > 樹根
    public static void postorder(int index) {
        if (index < tree_arr.length) {
            btree.preorder(index * 2);
            btree.preorder(index * 2 + 1);
            System.out.println(tree_arr[index]);
        }
    }
}