顺序存储二叉树

首先有一个数组 int[] arr = {1,2,3,4,5,6,7} ,正常存储方式为线性存储，依然会有线性存储的缺点，做修改操作时变动较大。

接下来实现数组存储为二叉树形式。

image.png

首先得知道如何判断左子树和右子树，左子树为 index2+1,右子树为index2+2,index为数组的下标,然后递归遍历即可。

public class ArrBinaryTree {

    public static void main(String[] args) {
        BinaryTree1 binaryTree1 = new BinaryTree1();
        int[] arr = {1,2,3,4,5,6,7};
        binaryTree1.setArr(arr);
        //binaryTree1.preOrder(0);
        //binaryTree1.infixOrder(0);
        binaryTree1.postOrder(0);
    }   
}

class BinaryTree1{
    
    private int[] arr;

    public void setArr(int[] arr) {
        this.arr = arr;
    }
    
    //顺序存储二叉树前序遍历
    public void preOrder(int index) {
        if(arr==null || arr.length==0) {
            System.out.println("二叉树为空!");
            return;
        }
        System.out.println(arr[index]);
        //向左递归
        if((index*2+1)<arr.length) {
            preOrder(index*2+1);
        }
        //向右递归
        if((index*2+2)<arr.length) {
            preOrder(index*2+2);
        }
    }
    
    //顺序存储二叉树中序遍历
        public void infixOrder(int index) {
            if(arr==null || arr.length==0) {
                System.out.println("二叉树为空!");
                return;
            }
            
            //向左递归
            if((index*2+1)<arr.length) {
                infixOrder(index*2+1);
            }
            System.out.println(arr[index]);
            //向右递归
            if((index*2+2)<arr.length) {
                infixOrder(index*2+2);
            }
        }
        
        //顺序存储二叉树后序遍历
        public void postOrder(int index) {
            if(arr==null || arr.length==0) {
                System.out.println("二叉树为空!");
                return;
            }
            //向左递归
            if((index*2+1)<arr.length) {
                postOrder(index*2+1);
            }
            //向右递归
            if((index*2+2)<arr.length) {
                postOrder(index*2+2);
            }
            System.out.println(arr[index]);
        }
}