概念

將 unsorted array 轉換為 binary tree,並用深度優先(DFS)遍歷。

  • left node: (i+1) * 2
  • right node: (i+1) * 2 + 1
  • parent node: (i+1) / 2
  • level: log(i+1)

實作

package com.BT;

import java.util.LinkedList;
import java.util.Queue;

public class BT_Array {
    private Integer[] nums;

    // 傳入陣列,用不同視角看陣列 -> 二元樹
    public BT_Array(Integer[] nums) {
        this.nums = nums;
    }

    /** DFS left **/
    public void traverse_preorder() {
        if (this.nums.length < 0) return; // 無陣列內容
        int i_root = 0; // 預設開頭
        if (this.nums[i_root] == null) return;
        this.traverse_preorder(i_root);
    }

    private void traverse_preorder(int i) {
        if (i >= this.nums.length) return;

        if (this.nums[i] != null) System.out.print(this.nums[i] + " "); // preoder: 先印

        /** next round step **/
        int i_plus_one = i + 1;  // 0+1, 1+1, 2+1

        //計算當前節點的下個左節點與右節點
        int i_left_plus_one = i_plus_one * 2; // left:(i+1)*2, 2, 4, 6
        int i_right_plus_one = i_plus_one * 2 + 1; // right:(i+1)*2+1, 3, 5, 7

        // 推算當前要執行的node
        int i_left = i_left_plus_one - 1; //3, 5
        int i_right = i_right_plus_one - 1; //4, 6

        traverse_preorder(i_left); // 往左到底
        traverse_preorder(i_right); // 往右到底
    }

    public void traverse_inorder() {
        if (this.nums.length < 0) return;
        int i_root = 0;
        if (this.nums[i_root] == null) return;
        this.traverse_inorder(i_root);
    }

    private void traverse_inorder(int i) {
        if (i >= this.nums.length) return;


        /** next round step **/
        int i_plus_one = i + 1;
        int i_left_plus_one = i_plus_one * 2;
        int i_right_plus_one = i_plus_one * 2 + 1;

        int i_left = i_left_plus_one - 1;
        int i_right = i_right_plus_one - 1;

        traverse_inorder(i_left);
        if (this.nums[i] != null) System.out.print(this.nums[i] + " ");
        traverse_inorder(i_right);
    }

    public void traverse_postorder() {
        if (this.nums.length < 0) return;
        int i_root = 0;
        if (this.nums[i_root] == null) return;
        this.traverse_postorder(i_root);
    }

    private void traverse_postorder(int i) {
        if (i >= this.nums.length) return;

        /** next round step **/
        int i_plus_one = i + 1;
        int i_left_plus_one = i_plus_one * 2;
        int i_right_plus_one = i_plus_one * 2 + 1;

        int i_left = i_left_plus_one - 1;
        int i_right = i_right_plus_one - 1;

        traverse_postorder(i_left);
        traverse_postorder(i_right);
        if (this.nums[i] != null) System.out.print(this.nums[i] + " ");

    }

    /** DFS right **/
    public void traverse_preorder_dfsright() {
        if (this.nums.length < 0) return;
        int i_root = 0;
        if (this.nums[i_root] == null) return;
        this.traverse_preorder_dfsright(i_root);
    }

    private void traverse_preorder_dfsright(int i) {
        if (i >= this.nums.length) return;

        if (this.nums[i] != null) System.out.print(this.nums[i] + " ");

        /** next round step **/
        int i_plus_one = i + 1;
        int i_left_plus_one = i_plus_one * 2;
        int i_right_plus_one = i_plus_one * 2 + 1;

        int i_left = i_left_plus_one - 1;
        int i_right = i_right_plus_one - 1;

        traverse_preorder_dfsright(i_right);
        traverse_preorder_dfsright(i_left);
    }

    public void traverse_inorder_dfsright() {
        if (this.nums.length < 0) return;
        int i_root = 0;
        if (this.nums[i_root] == null) return;
        this.traverse_inorder_dfsright(i_root);
    }

    private void traverse_inorder_dfsright(int i) {
        if (i >= this.nums.length) return;


        /** next round step **/
        int i_plus_one = i + 1;
        int i_left_plus_one = i_plus_one * 2;
        int i_right_plus_one = i_plus_one * 2 + 1;

        int i_left = i_left_plus_one - 1;
        int i_right = i_right_plus_one - 1;

        traverse_inorder_dfsright(i_right);
        if (this.nums[i] != null) System.out.print(this.nums[i] + " ");
        traverse_inorder_dfsright(i_left);
    }

    public void traverse_postorder_dfsright() {
        if (this.nums.length < 0) return;
        int i_root = 0;
        if (this.nums[i_root] == null) return;
        this.traverse_postorder_dfsright(i_root);
    }

    private void traverse_postorder_dfsright(int i) {
        if (i >= this.nums.length) return;

        /** next round step **/
        int i_plus_one = i + 1;
        int i_left_plus_one = i_plus_one * 2;
        int i_right_plus_one = i_plus_one * 2 + 1;

        int i_left = i_left_plus_one - 1;
        int i_right = i_right_plus_one - 1;

        traverse_postorder_dfsright(i_right);
        traverse_postorder_dfsright(i_left);
        if (this.nums[i] != null) System.out.print(this.nums[i] + " ");

    }
``