总目录：地址如下看总纲
1、介绍
- 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组
遍历数组 arr时，仍然可以以�前序遍历，中序遍历和后序遍历的方式得到二叉树
image.png
image.png
2、顺序二叉树特点：
- 顺序二叉树通常只考虑完全二叉树，以下推导
- 第n个元素的左子节点为 2 * n + 1
- 第n个元素的右子节点为 2 * n + 2
- 第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、关于应用
八大排序算法中的堆排序，就会使用到顺序存储二叉树
