文章收藏的好句子：永远不要当生活的逃兵，也不必抱怨命运的不公。
目录
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();
}
日志打印如下所示：
