Overview

顺序存储二叉树，是由数组转换成的二叉树，一个元素为数组的二叉树。

提供了数组转换成二叉树的思路

基本说明

image.png

要求

将arr:[1,2,3,4,5,6,7]转换为二叉树，并能够前序，中序，后序查找。

image.png

顺序存储二叉树的特点

image.png

notice：

这里n指的是数组中的索引，左右子节点公式计算的是对应数组的索引，而不是具体的数组的值。

比如3的左子节点：

3的index=2，

那么其左子节点索引为：

5，即对应数组arr[5]=6

右子节点索引：

6，即arr[6]=7

code

ArrayBinaryTree

package com.pl.arithmetic.arrayBinaryTree;

/**
 * <p>
 *
 * @Description: 数组二叉树，顺序二叉树
 * </p>
 * @ClassName ArrayBinaryTree
 * @Author pl
 * @Date 2020/11/6
 * @Version V1.0.0
 */
public class ArrayBinaryTree {
    private int arr[];

    public ArrayBinaryTree(int[] arr) {
        this.arr = arr;
    }

    public void preOrder(){
        preOrder(0);
    }

    /**
     * 前序遍历
     *
     * @param index 数组索引，角标
     * @return void
     * @exception
     * @author silenter
     * @date 2020/11/6 21:57
    */
    public void preOrder(int index){
        //@1 先判断是否数组越界 和数组是否为空
        if (index>arr.length){
            System.out.println("无此节点");
            return;
        }
        if (arr==null && arr.length == 0){
            System.out.println("数组为空");
            return;
        }
        System.out.println(arr[index]);
        //数组角标和数组大小永远是小于关系
        //@2 左子树
        if (index*2+1<arr.length){
            preOrder(index*2+1);
        }
        //@3 右子树
        if (index*2+2<arr.length){
            preOrder(index*2+2);
        }

    }
}

ArrBinaryTreeDemo

package com.pl.arithmetic.arrayBinaryTree;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName ArrBinaryTreeDemo
 * @Author pl
 * @Date 2020/11/6
 * @Version V1.0.0
 */
public class ArrBinaryTreeDemo {

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
        //创建一个 ArrBinaryTree
        ArrayBinaryTree arrBinaryTree = new ArrayBinaryTree(arr);
        arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
    }
}

输出

image.png