总目录：地址如下看总纲

https://www.jianshu.com/p/929ca9e209e8

1、介绍

1. 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组

2. 遍历数组 arr时，仍然可以以�前序遍历，中序遍历和后序遍历的方式得到二叉树

   
   image.png
   image.png

2、顺序二叉树特点：

1. 顺序二叉树通常只考虑完全二叉树，以下推导
2. 第n个元素的左子节点为 2 * n + 1
3. 第n个元素的右子节点为 2 * n + 2
4. 第n个元素的父节点为 (n-1) / 2

• 注：表示二叉树中的第几个元素(按0开始编号，既每个 -1)

3、代码

package com.kk.datastructure.tree;
/**
 * title: 顺序存储二叉树（前中后序遍历）
 * @author 阿K
 * 2021年1月1日 上午11:53:09 
 */
public class ArrBinaryTreeDemo {

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
        //new ArrBinaryTree(arr).perOrder();
        new ArrBinaryTree(arr).infixOrder();
        //new ArrBinaryTree(arr).postOrder();
    }
}

// 顺序存储二叉树（前，中，后序遍历）
class ArrBinaryTree {

    private int[] data;// 存储数据节点的数组

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

    // 重载前序遍历(直接调用这个，方便）
    public void perOrder() {
        this.perOrder(0);
    }
    // 重载中序遍历(直接调用这个，方便）
    public void infixOrder() {
        this.infixOrder(0);
    }
    // 重载后序遍历(直接调用这个，方便）
    public void postOrder() {
        this.postOrder(0);
    }

    /**
     * 顺序存储二叉树的前序遍历
     * 
     * @param index 数组的下标
     */
    public void perOrder(int index) {
        // 判空
        if (data == null && data.length == 0) {
            System.out.println("数组为空，不能按照前序遍历为二叉树哦~~");
        }
        // 输出当前元素，用于查看
        System.out.printf("当前输出节点：%s\n", data[index]);

        // 注：以下左右递归的推导，在思路上有体现
        // 向左递归遍历
        if (index * 2 + 1 < data.length) {
            perOrder(index * 2 + 1);
        }
        // 向右递归遍历
        if (index * 2 + 2 < data.length) {
            perOrder(index * 2 + 2);
        }
    }

    /**
     * 顺序存储二叉树的中序遍历
     * 
     * @param index 数组的下标
     */
    public void infixOrder(int index) {
        // 判空
        if (data == null && data.length == 0) {
            System.out.println("数组为空，不能按照前序遍历为二叉树哦~~");
        }

        // 注：以下左右递归的推导，在思路上有体现
        // 向左递归遍历
        if (index * 2 + 1 < data.length) {
            infixOrder(index * 2 + 1);
        }
        // 输出当前元素，用于查看
        System.out.printf("当前输出节点：%s\n", data[index]);
        
        // 向右递归遍历
        if (index * 2 + 2 < data.length) {
            infixOrder(index * 2 + 2);
        }
    }

    /**
     * 顺序存储二叉树的后序遍历
     * 
     * @param index 数组的下标
     */
    public void postOrder(int index) {
        // 判空
        if (data == null && data.length == 0) {
            System.out.println("数组为空，不能按照前序遍历为二叉树哦~~");
        }

        // 注：以下左右递归的推导，在思路上有体现
        // 向左递归遍历
        if (index * 2 + 1 < data.length) {
            postOrder(index * 2 + 1);
        }
        // 向右递归遍历
        if (index * 2 + 2 < data.length) {
            postOrder(index * 2 + 2);
        }
        // 输出当前元素，用于查看
        System.out.printf("当前输出节点：%s\n", data[index]);

    }

}

4、输出结果预览

image.png

5、关于应用

八大排序算法中的堆排序，就会使用到顺序存储二叉树