1. 首页
  2. IT资讯

(Java实现)二叉树—顺序存储

概述

  • 所谓顺序存储,就是以数组的形式存储二叉树
  • 通常顺序存储是用在完全二叉树上,如果完全二叉树用数组存储,那么这个数组也能很快的按照前序、中序和后序遍历的方式还原出完全二叉树,因为每一个相同类型节点(左/右/父节点)的序号都能用同一个数学公式表示
  • 如果顺序二叉树是完全二叉树,那么
    • 第n个元素的左子节点为2 * n + 1
    • 第n个元素的右子节点为2 * n + 2
    • 第n个元素的父节点为 (n-1) / 2
    • n从0开始,表示二叉树的第几个元素
  • 如下图所示,如何用数组来存储二叉树:image

顺序二叉树的遍历

  • 对于完全二叉树而言,根据上面提供的公式,我们能够很快的通过前序/中序/遍历的方式还原二叉树,这里就不细讲了(如果不懂得前序/中序/后序遍历的,可以看我上一篇文章
  • 具体代码如下:
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);
 }
}

本文来自投稿,不代表程序员编程网立场,如若转载,请注明出处:http://www.cxybcw.com/203489.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code