顺序存储二叉数（Java）

1、顺序存储二叉数

从存储角度来看，我们之前讲的树在存储结构上不是顺序存储的，都是非线性的存储结构，所以我们可以从数组的角度来分析，数组和树可以相互转换，数组可以转换成树，树也可以转换成数组，数的示意图如下：

我们在数组中的存储样式为：

int[] nums = {1,2,3,4,5,6,7};

1.1、顺序存储二叉树的特点

1. 对于顺序存储的树我们通常只考虑完全二叉树（规律）
2. 第n个元素的左子节点为2*n+1（左子节点不为空的情况下）
3. 第n个元素的右子节点为2*n+2（右子节点不为空的情况下）
4. 第n个元素的父节点为（n-1）/2

2、前序遍历

和之前讲的二叉树的遍历一样，只是遍历的逻辑条件需要变化一些

顺序为：1 2 4 5 3 6 7

代码实现：

public static void preOrder(int index, int[] nums) {
    System.out.println(nums[index]);
    if (nums.length > 2 * index + 1) {
        preOrder(2 * index + 1, nums);
    }
    if (nums.length > 2 * index + 2) {
        preOrder(2 * index + 2, nums);
    }
}

3、中序遍历

和之前讲的二叉树的遍历一样，只是遍历的逻辑条件需要变化一些

顺序为：4 2 5 1 6 3 7

代码实现：

public static void inOrder(int index, int[] nums) {
    if (nums.length > 2 * index + 1) {
        inOrder(2 * index + 1, nums);
    }
    System.out.println(nums[index]);
    if (nums.length > 2 * index + 2) {
        inOrder(2 * index + 2, nums);
    }
}

4、后序遍历

和之前讲的二叉树的遍历一样，只是遍历的逻辑条件需要变化一些

顺序为：4 5 2 6 7 3 1

代码实现：

public static void postOrder(int index, int[] nums) {
    if (nums.length > 2 * index + 1) {
        postOrder(2 * index + 1, nums);
    }
    if (nums.length > 2 * index + 2) {
        postOrder(2 * index + 2, nums);
    }
    System.out.println(nums[index]);
}