一、顺序存储二叉树的概念

1. 基本说明

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组
顺序存储二叉树 - 图1

2. 顺序存储二叉树的特点：

  1. 顺序二叉树通常只考虑完全二叉树
  2. 第 n 个元素的左子节点为 2 * n + 1
  3. 第 n 个元素的右子节点为 2 * n + 2
  4. 第 n 个元素的父节点为 (n-1) / 2
  5. n : 表示二叉树中的第几个元素(按 0 开始编号如图所示)

    二、顺序存储二叉树遍历

    需求: 给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。 前序遍历的结果应当为 1,2,4,5,3,6,7
    代码实现： ```java public class ArrBinaryTreeDemo { public static void main(String[] args) {
    1.  int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
    2.  //创建一个 ArrBinaryTree
    3.  ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
    4.  arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
    } }

//编写一个 ArrayBinaryTree, 实现顺序存储二叉树遍历 class ArrBinaryTree { private int[] arr;//存储数据结点的数组 public ArrBinaryTree(int[] arr) { this.arr = arr; }

//重载 preOrder
public void preOrder() {
    this.preOrder(0);
}

//编写一个方法，完成顺序存储二叉树的前序遍历
/**
 *
 * @param index 数组的下标
 */
public void preOrder(int index) {
    //如果数组为空，或者 arr.length = 0
    if(arr == null || arr.length == 0) {
        System.out.println("数组为空，不能按照二叉树的前序遍历");
    }
    //输出当前这个元素
    System.out.println(arr[index]);
    //向左递归遍历
    if((index * 2 + 1) < arr.length) {
        preOrder(2 * index + 1 );
    }
    //向右递归遍历
    if((index * 2 + 2) < arr.length) {
        preOrder(2 * index + 2);
    }
}

public void infixOrder() {
    this.infixOrder(0);
}

private void infixOrder(int index) {
    // left recursion
    if (2 * index + 1 < arr.length) {
        infixOrder(2 * index + 1);
    }
    // show current node
    System.out.println(arr[index]);
    // right recursion
    if (2 * index + 2 < arr.length) {
        infixOrder(2 * index + 2);
    }
}

public void postPre() {
    this.postPre(0);
}

private void postPre(int index) {
    // left recursion
    if (2 * index + 1 < arr.length) {
        postPre(2 * index + 1);
    }
    // right recursion
    if (2 * index + 2 < arr.length) {
        postPre(2 * index + 2);
    }
    // show current node
    System.out.println(arr[index]);
}

} ```