顺序存储二叉树（java）

顺序存储二叉树的概念：

以数据存储来卡你，数组存储方式和树的存储方式是可以相互转换的，即数组可以转换为树，树也可以转换为数组；

那么在对于顺序存储二叉树，我们就可以利用数组的顺序存储的特点，用数组来实现二叉树的顺序存储；如下图所示：

顺序存储二叉树的特点：

1、顺序二叉树通常只考虑完全二叉树

2、第n个节点的左子节点为 2 * n + 1

3、第n个元素的右子节点为 2 * n + 2

4、第n个元素的父节点为 (n - 1) / 2

5、n：表示二叉树中的第几个元素（按0开始编号）

例子： 给定一个数组{1,2,3,4,5,6,7}，要求以二叉树前序、中序、后序遍历的方式进行遍历

首先需要创建一个AayBinaryTree类

class ArrayBinaryTree { private int[] arr; //存储数据节点的数组 public ArrayBinaryTree(int[] arr) { this.arr = arr; } }

前序遍历

public void preOrder(int index) { //如果数组为空，或者 arr.length = 0 if (arr == null || arr.length == 0) { System.out.println("数组为空，不能按照二叉树的前序遍历"); return; } //输出当前这个元素 System.out.println(arr[index]); //向左递归遍历 if (index * 2 + 1 < arr.length) { preOrder(2 * index + 1); } //向右递归遍历 if (index * 2 + 2 < arr.length) { preOrder(2 * index + 2); } }

中序遍历

public void infixOrder(int index) { //如果数组为空，或者 arr.length = 0 if (arr == null || arr.length == 0) { System.out.println("数组为空，不能按照二叉树的前序遍历"); return; } //向左递归遍历 if (index * 2 + 1 < arr.length) { infixOrder(2 * index + 1); } //输出当前这个元素 System.out.println(arr[index]); //向右递归遍历 if (index * 2 + 2 < arr.length) { infixOrder(2 * index + 2); } }

后序遍历

public void postOrder(int index) { //如果数组为空，或者 arr.length = 0 if (arr == null || arr.length == 0) { System.out.println("数组为空，不能按照二叉树的前序遍历"); return; } //向左递归遍历 if (index * 2 + 1 < arr.length) { postOrder(2 * index + 1); } //向右递归遍历 if (index * 2 + 2 < arr.length) { postOrder(2 * index + 2); } //输出当前这个元素 System.out.println(arr[index]); }