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

概述

• 所谓顺序存储，就是以数组的模式存储二叉树
• 通常顺序存储是用在齐全二叉树上，如果齐全二叉树用数组存储，那么这个数组也能很快的依照前序、中序和后序遍历的形式还原出齐全二叉树，因为每一个雷同类型节点（左/右/父节点）的序号都能用同一个数学公式示意

• 如果程序二叉树是齐全二叉树，那么

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