1. 概念

  1. 1.以数组的形式保存的二叉树
  2.     相关的方法，如遍历仍然通过二叉树的方式
  5. 2.顺序二叉树和数组之间可以相互转换
  6.     条件：二叉树为完全二叉树
  7.     转换规则：
  8.         数组下标：0开始，从左往右
  9.         节点编号：1开始，从上往下，从左往右
  10.     关系：【数组下标index】与节点相对位置的关系
  11.         数组中index为n的某个元素：
  12.             左子节点index = 2n + 1
  13.             右子节点index = 2n + 2
  14.               父节点index = (n-1) / 2

2. 定义顺序存储二叉树

  1. @Data
  2. class ArrayBinaryTree {
  3.     // 元数组
  4.     private int[] arr;
  6.     // 前置遍历 TODO
  7.     public void preOrder(int index) {}
  9.     // 前置遍历 TODO
  10.     public void infixOrder(int index) {}
  12.     // 后置遍历
  13.       public void postOrder(int index) {} 
  14. }

3. 遍历

这里只展开前置遍历

  1. 前置遍历实现

    1.  // 前置遍历,从0开始
    2.  public void preOrder(int index) {
    4.      System.out.println(arr[index]);
    5.      // 判断左节点(左节点index=2*index+1)
    6.      if (2 * index + 1 < arr.length) {
    7.          preOrder(2 * index + 1);
    8.      }
    9.      // 判断右节点(右节点index=2*index+2)
    10.      if (2 * index + 2 < arr.length) {
    11.          preOrder(2 * index + 2);
    12.      }
    13.  }

  2. 前置遍历测试

    1. /**
    2. * 输出结果：
    3. *      1    2    4    5    3    6    7
    4. */
    5. public static void main(String[] args) {
    6.   int[] arr = {1,2,3,4,5,6,7};
    7.   ArrayBinaryTree arrTree = new ArrayBinaryTree(arr);
    8.   arrTree.preOrder(0);
    9. }