数组顺序储存二叉树

根据数组顺序，将数组元素储存进一个完全二叉树。
至于为什么是完全二叉树，因为完全二叉树转化成有序数组后才最有效的利用数组空间，不至于浪费。
提示：记录，复习，学习

一、具体步骤

1.思路分析

一个有序数组，对应的完全二叉树：
一个二叉树的节点(下标index)，对应的父节点下标：(index-1)/2，对应的值index+1
同样，该节点（下标index）的左子节点下标：2index+1
右子节点的下标2index+2
先根据数组从index=0开始，根据子节点的规律，在数组中得到相应的子节点下标，然后根据下标的值得到节点的值，通过getparent（val）得到父节点，然后将待添加节点添加到父节点左右，先左后右。
顺序储存的二叉树
引用于尚硅谷截图（哈哈哈）

数组方法

代码如下（示例）：

//完全二叉树，顺序储存二叉树
    //给定符合完全二叉树的数组，顺序储存进二叉树
    public void SequentialStorage(int[] arr, int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空");
            return;
        }
        //添加节点,节点的值两个参数
        head.addOrder(new Node(arr[index], (index + 1) + ""), arr[index]);
        //根据数组下标遍历数组，顺序储存进二叉树
        if (index * 2 + 1 < arr.length)
            SequentialStorage(arr, index * 2 + 1);
        if (index * 2 + 2 < arr.length)
            SequentialStorage(arr, index * 2 + 2);
    }

2.加入二叉树的方法

代码如下（示例）：

 //顺序储存
    public void addOrder(Node node, int index) {
        //获得父节点
        Node parent = getParent(index);
        //根节点没有父节点
        if (parent == null) {
            System.out.println("无父节点");
            return;
        } else
            System.out.println(index + "的父节点是:" + parent);
        if (parent.left == null) {
            parent.setLeft(node);
            return;
        } else {
            if (parent.right == null) {
                parent.setRight(node);
                return;
            }
        }
    }

该处使用先左后右顺序添加

得到父节点方法

//返回父节点
    public Node getParent(int val) {
        //val-1为下标，下标为0的是根节点
        if (val - 1 == 0)
            return null;
        //return find(val /2 )这里index是节点值
        return find((val - 1 - 1) / 2 + 1);
        //节点值为val
    }

find(Node node)

 //前序查找
    public Node find(int val) {

        /*
        //前序
        System.out.println("次数");
        if (val == this.val)
            return this;
        */

        //temp用来标记是否找到了
        //如果找到了才退出该方法，找不到temp==null,会继续向右递归
        //进行查找
        Node temp = null;
        if (this.left != null)
            temp = this.left.find(val);
        //左边找到了就不往右边找了，省时间
        if (temp != null)
            return temp;

//        /*
        //中序
//        System.out.println("次数");
        if (val == this.val)
            return this;
//         */

        //右边不为空，右递归前序查找
        if (this.right != null)
            temp = this.right.find(val);
        //这不用判断temp是否是null，找到就返回了
        //找不到就是真的找不到了

        /*
        //后序
        if (temp != null)
            return temp;
        System.out.println("次数");
        if (val == this.val)
            return this;
        */

        return temp;

    }