Lucy's Note of Coding

二元樹說明：

完美二元樹	Perfect Binary Tree	Every node except the leaf nodes have two children and every level (last level too) is completely filled.除了葉子結點之外的每一個結點都有兩個孩子，每一層(當然包含最後一層)都被完全填充。
完全二元樹	Complete Binary Tree	Every level except the last level is completely filled and all the nodes are left justified.除了最後一層之外的其他每一層都被完全填充，並且所有結點都保持向左對齊。
完滿二元樹	Full/Strictly Binary Tree	Every node except the leaf nodes have two children.除了葉子結點之外的每一個結點都有兩個孩子結點。

•   完美(Perfect)二元樹一定是完全(Complete)二元樹，但完全(Complete)二元樹不一定是完美(Perfect)二元樹。
• 完美(Perfect)二元樹一定是完滿(Full)二元樹，但完滿(Full)二元樹不一定是完美(Perfect)二元樹。
• 完全(Complete)二元樹可能是完滿(Full)二元樹，完滿(Full)二元樹也可能是完全(Complete)二元樹。
• 既是完全(Complete)二元樹又是完滿(Full)二元樹也不一定就是完美(Perfect)二元樹。

參考來源：https://www.cnblogs.com/idorax/p/6441043.html

 

package utitled;

// 通過陣列以二元樹形式進行前序, 中序, 後續遍歷
public class ArrBinaryTreeTraversalDemo {

  public static void main(String[] args) {
    int[] arr = {1,2,3,4,5,6,7};
    ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
    // 從根結點開始遍歷
    int rootInx = 0;
    System.out.println("前序");
    arrBinaryTree.preOrder(rootInx);// 1,2,4,5,3,6,7
    System.out.println("\n中序");
    arrBinaryTree.inOrder(rootInx);// 4,2,5,1,6,3,7
    System.out.println("\n後序");
    arrBinaryTree.postOrder(rootInx);// 4,5,2,6,7,3,1
  }


}

class ArrBinaryTree {
  private int[] arr;

  public ArrBinaryTree(int[] arr) {
    this.arr = arr;
  }

  /**
   * 將陣列前序遍歷
   * @param index 陣列索引
   */
  public void preOrder(int index) {
    // 先判斷index是否越界
    if (arr == null && arr.length == 0) {
      System.out.println("陣列為空，無法遍歷");
      return;
    }
    if (index >= arr.length) {
      return;
    }

    // 輸出當前node
    System.out.print(arr[index]+"\t");
    // 向左前序遍歷
    preOrder(2 * index + 1);
    // 向右前序遍歷
    preOrder(index * 2 + 2);
  }

  /**
   * 將陣列中序遍歷
   * @param index 陣列索引
   */
  public void inOrder(int index) {
    // 先判斷index是否越界
    if (arr == null && arr.length == 0) {
      System.out.println("陣列為空，無法遍歷");
      return;
    }
    if (index >= arr.length) {
      return;
    }

    // 向左前序遍歷
    inOrder(2 * index + 1);
    // 輸出當前node
    System.out.print(arr[index]+"\t");
    // 向右前序遍歷
    inOrder(index * 2 + 2);
  }

  /**
   * 將陣列後序遍歷
   * @param index 陣列索引
   */
  public void postOrder(int index) {
    // 先判斷index是否越界
    if (arr == null && arr.length == 0) {
      System.out.println("陣列為空，無法遍歷");
      return;
    }
    if (index >= arr.length) {
      return;
    }

    // 向左前序遍歷
    postOrder(2 * index + 1);
    // 向右前序遍歷
    postOrder(index * 2 + 2);
    // 輸出當前node
    System.out.print(arr[index]+"\t");
  }
}

 

如有敘述錯誤，還請不吝嗇留言指教，thanks!