乐趣区

关于java:Java版顺序存储二叉树

jiezi

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

}

日志打印如下所示：

图片

退出移动版