概述
- 所谓顺序存储,就是以数组的模式存储二叉树
- 通常顺序存储是用在齐全二叉树上,如果齐全二叉树用数组存储,那么这个数组也能很快的依照前序、中序和后序遍历的形式还原出齐全二叉树,因为每一个雷同类型节点(左 / 右 / 父节点)的序号都能用同一个数学公式示意
-
如果程序二叉树是齐全二叉树,那么
- 第 n 个元素的左子节点为 2 * n + 1
- 第 n 个元素的右子节点为 2 * n + 2
- 第 n 个元素的父节点为 (n-1) / 2
- n 从 0 开始,示意二叉树的第几个元素
- 如下图所示,如何用数组来存储二叉树:
程序二叉树的遍历
- 对于 齐全二叉树 而言,依据下面提供的公式,咱们可能很快的通过前序 / 中序 / 遍历的形式还原二叉树,这里就不细讲了(如果不懂得前序 / 中序 / 后序遍历的,能够看我上一篇文章)
- 具体代码如下:
public class ArrayBinaryTree {private static int[] arr = {18, 20, 29, 16, 42, 39, 8}; // 存储二叉树节点
private static int length = arr.length;
// 前序遍历
public static void preOrder_Traversal(int index){if (index < 0 || index > length) return;
System.out.print(arr[index] + " ");
int leftIndex = 2 * index + 1;
int rightIndex = 2 * index + 2;
if (leftIndex < length)
preOrder_Traversal(leftIndex);
if (rightIndex < length)
preOrder_Traversal(rightIndex);
}
// 中序遍历
public static void inOrder_Traversal(int index){if (index < 0 || index > length) return;
int leftIndex = 2 * index + 1;
int rightIndex = 2 * index + 2;
if (leftIndex < length)
inOrder_Traversal(leftIndex);
System.out.print(arr[index] + " ");
if (rightIndex < length)
inOrder_Traversal(rightIndex);
}
// 后序遍历
public static void postOrder_Traversal(int index){if (index < 0 || index > length) return;
int leftIndex = 2 * index + 1;
int rightIndex = 2 * index + 2;
if (leftIndex < length)
postOrder_Traversal(leftIndex);
if (rightIndex < length)
postOrder_Traversal(rightIndex);
System.out.print(arr[index] + " ");
}
public static void main(String[] args) {
//index 示意根节点
postOrder_Traversal(0);
}
}