共计 2603 个字符，预计需要花费 7 分钟才能阅读完成。
PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
目录
1、顺序存储二叉树
1、顺序存储二叉树
从数据存储来看，数组存储形式和树的存储形式能够互相转换，即数组能够转换成树，树也能够转换成数组；这里咱们讲的顺序存储二叉树通常是齐全二叉树，所以，如果咱们想顺序存储一般二叉树，须要提前将一般二叉树转化为齐全二叉；对于齐全二叉树的定义，能够看 Java 版的数据结构和算法（三）这篇文章；二叉树的顺序存储，指的是应用程序表（数组）存储二叉树，齐全二叉树的顺序存储，仅需从根节点开始，依照档次顺次将树中节点存储到数组即可；好，上面咱们画一棵能够顺序存储的二叉树，如下图 1:
图片
留神：红色的数字示意节点的值，蓝色的数字示意节点的编号。
“二叉树的顺序存储，指的是应用程序表（数组）存储二叉树，齐全二叉树的顺序存储，仅需从根节点开始，依照档次顺次将树中节点存储到数组即可”这句话怎么了解呢？就拿图 1 的齐全二叉树来做例子，如果咱们用数组来存储这棵二叉树，那么数组的元素存储为 array = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}，看，红色的数字就作为数组的元素，蓝色的数字就作为数组的下标，如果根节点的层是第一层，根节点的子节点是第二层，那么数组就先存储第一层，而后再第二层，又再存下一层，以此类推，最终数组存储的元素遍历进去是程序的，这时候应该了解双引号外面那一段文字了吧。
顺序存储二叉树有如下几个特色：
留神：n 示意二叉树中的第几个元素（n 从 0 开始算，不能小于 0，n 也就示意节点的编号，如图 1 所示）
1）程序二叉树通常只思考齐全二叉树。
2）第 n 个元素的左子节点为 2 *n+ 1。
3）第 n 个元素的右子节点为 2 *n+ 2。
4）第 n 个元素的父节点为 (n-1)/2。
咱们这里用代码实现一把：就是把图 1 中的顺序存储二叉树的节点都寄存到数组中，而后依照肯定的法则输入数组元素时，也能实现图 1 中二叉树的前序遍历、中序遍历和后序遍历；对于二叉树的遍历，可看 Java 版的数据结构和算法（四）这篇文章。
（1）写一个将数组转化成二叉树遍历（前序、中序和后序）的类 ArrayBinaryTree：
public class ArrayBinaryTree {
private int[] array;// 存储数据节点的数组
public ArrayBinaryTree(int[] array) {
this.array = array;}
public void preOrder() {
preOrder(0);}
// 数组的输入程序转换成对应的二叉树的前序遍历
private void preOrder(int index) {
if (array == null || array.length == 0) {System.out.println("数组为空，不能进行二叉树的前序遍历");
return;
}
// 输入以后这个元素
System.out.println(array[index]);
// 向左递归遍历
if(index * 2 + 1 < array.length) {preOrder(index * 2 + 1);
}
// 向右递归遍历
if(index * 2 + 2 < array.length) {preOrder(index * 2 + 2);
}}
public void middleOrder() {
middleOrder(0);}
// 数组的输入程序转换成对应的二叉树的中序遍历
private void middleOrder(int index) {
if (array == null || array.length == 0) {System.out.println("数组为空，不能进行二叉树的前序遍历");
return;
}
// 向左递归遍历
if(index * 2 + 1 < array.length) {middleOrder(index * 2 + 1);
}
// 输入以后这个元素
System.out.println(array[index]);
// 向右递归遍历
if(index * 2 + 2 < array.length) {middleOrder(index * 2 + 2);
}}
public void postOrder() {
postOrder(0);}
// 数组的输入程序转换成对应的二叉树的后序遍历
private void postOrder(int index) {
if (array == null || array.length == 0) {System.out.println("数组为空，不能进行二叉树的前序遍历");
return;
}
// 向左递归遍历
if(index * 2 + 1 < array.length) {postOrder(index * 2 + 1);
}
// 向右递归遍历
if(index * 2 + 2 < array.length) {postOrder(index * 2 + 2);
}
// 输入以后这个元素
System.out.println(array[index]);}
}
前序遍历入口调用测试：
public static void main(String[] args) {
int[] array = new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
ArrayBinaryTree abt = new ArrayBinaryTree(array);
System.out.println("前序遍历");
abt.preOrder();}
日志打印如下所示：
图片
中序遍历入口调用测试：
public static void main(String[] args) {
int[] array = new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
ArrayBinaryTree abt = new ArrayBinaryTree(array);
System.out.println("中序遍历");
abt.middleOrder();}
日志打印如下所示：
图片
后序遍历入口调用测试：
public static void main(String[] args) {
int[] array = new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
ArrayBinaryTree abt = new ArrayBinaryTree(array);
System.out.println("后序遍历");
abt.postOrder();}
日志打印如下所示：
图片
