Java版顺序存储二叉树 java

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); }

}
【Java版顺序存储二叉树】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();

}
日志打印如下所示：
图片