[数据结构与算法]二叉树之顺序存储二叉树Java数据结构篇

二叉树之顺序存储

>>二叉树的顺序存储：（为堆排序的学习做铺垫）
 将数组按顺序写成二叉树，再将二叉树前序，中序，后序遍历
                     int[] arr={1,2,3,4,5,6,7};
                     
                                     1
                                   /   \
                                  2     3
                                /   \  /  \
                               4    5  6   7
                 前序遍历:1245367
                 中序遍历:4251637
                 后续遍历:4526731
  借助的规律：
   2*父节点对应数组中的下标+1=左子节点对应数组的下标
   2*父节点对应数组中的下标+2=右子节点对应数组的下标

代码实现（以方法的形式展现）

• 前序遍历：

    public static void perOrder(int[] arr,int index){
        //如果数组为null和数组长度为0
        if (arr==null||arr.length==0){
            System.out.println("数组为空，不能遍历");
            return;
        }
        //输出当前节点
        System.out.print(arr[index]);
        //向左递归，条件
        if (2*index+1<arr.length){
            perOrder(arr,2*index+1);
        }
        //向右递归
        if (2*index+2<arr.length){
            perOrder(arr,2*index+2);
        }
    }

• 中序遍历：

    public static void infixOrder(int[] arr,int index){
        //如果数组为null和数组长度为0
        if (arr==null||arr.length==0){
            System.out.println("数组为空，不能遍历");
            return;
        }

        //向左递归，条件
        if (2*index+1<arr.length){
            infixOrder(arr,2*index+1);
        }
        //输出当前节点
        System.out.print(arr[index]);
        //向右递归
        if (2*index+2<arr.length){
            infixOrder(arr,2*index+2);
        }
    }

• 后序遍历：

    public static void postOrder(int[] arr,int index){
        //如果数组为null和数组长度为0
        if (arr==null||arr.length==0){
            System.out.println("数组为空，不能遍历");
            return;
        }

        //向左递归，条件
        if (2*index+1<arr.length){
            postOrder(arr,2*index+1);
        }
        //向右递归
        if (2*index+2<arr.length){
            postOrder(arr,2*index+2);
        }
        //输出当前节点
        System.out.print(arr[index]);
    }

代码实现（以数据结构的形式展示（仅演示前序遍历））

• 前序遍历

public class ArrToBinaryTreeOpt {
    private int[] arr;

    public ArrToBinaryTreeOpt(int[] arr) {
        this.arr = arr;
    }
    public  void perOrder(int index){
        //如果数组为null和数组长度为0
        if (arr==null||arr.length==0){
            System.out.println("数组为空，不能遍历");
            return;
        }
        //输出当前节点
        System.out.print(arr[index]);
        //向左递归，注意条件
        if (2*index+1<arr.length){
            perOrder(2*index+1);
        }
        //向右递归，注意条件
        if (2*index+2<arr.length){
            perOrder(2*index+2);
        }
    }
    //对上面方法，进行重载，因为递归需要参数，而该参数人为输入一直是0；
    public void perOrder(){
        this.perOrder(0);
    }

    public static void main(String[] args) {
        int[] arr={1,2,3,4,5,6,7};
        ArrToBinaryTreeOpt opt = new ArrToBinaryTreeOpt(arr);
//        opt.perOrder(0);//由于一直传的都是零，但是又考虑到递归的实现，所以重载该方法
        opt.perOrder();
    }
}