2020-03-25

【灵光一现】两三点雨山前-二分查找&二叉树的创建和遍历

写在前面

二分查找思维不论是在算法中，还是在错误查找中都占据着及其重要的角色，所以本章用来复习二分查找。
此外，由于在写MR的TOPN时用到了treemap（由红黑树算法实现），突然意识到自己在二叉树这一块有欠缺，所以本文也对二叉树做一个初步复习
以下内容均为个人理解，若有不对，欢迎指正。

二分查找

所谓二分查找便是不停的将待查找树组对半分，取其中间值于查找值进行比较，若找到则不再对分，若不是则根据大小比结果朝不同方向继续对分。
这里需要注意的是，查找数组需要是有序的，可以在查找前先进行排序。

整个查找过程遵循两个原则

1.若中间值大于查找值，则取中间值左边（即比中间值小的值）部分进行对分。
2.若中间值小于查找值，则取中间值右边（即比中间值大的值）部分进行对分。

归并排序&二分查找代码如下

package com.sumiya.binarysearch;

import com.sun.xml.internal.org.jvnet.mimepull.CleanUpExecutorFactory;

public class BinarySearch {
    public static double binarySearch(double[] arr,int left,int right,double key){
        if(key<arr[left]||key>arr[right]||left>right){
            return  -1;
        }
        int mid = (left+right)/2;
        if(arr[mid]==key){
            return mid;
        }else if(arr[mid]>key){
            return binarySearch(arr,left,mid-1,key);
        }else{
            return binarySearch(arr,mid+1,right,key);
        }
    }

    public static void mergeSort(double[] arr,int left,int right){
        int mid = (left+right)/2;
        if(left<right){
            mergeSort(arr,left,mid);
            mergeSort(arr,mid+1,right);

            merge(arr,left,right,mid);
        }
    }
    public static void merge(double[] arr ,int left,int right,int mid){
        double[] tmp = new double[right-left+1];
        int k = 0;
        int i = left;
        int j = mid+1;
        while(i<=mid&&j<=right){
            if(arr[i]<arr[j]){
                tmp[k++] = arr[i++];
            }else{
                tmp[k++] = arr[j++];
            }
        }

        while(i<=mid){
            tmp[k++] = arr[i++];
        }
        while(j<=right){
            tmp[k++] = arr[j++];
        }

        for(int l = 0;l<tmp.length;l++){
            arr[l+left] = tmp[l];
        }
    }
    public static int count=0;
    public static void arrToString(double[] arr,String status){
        String str = "";
        for (double word : arr) {
            str = str + word + "\t";
        }
        System.out.println("当前数组状态："+ status+"\t"+str);
    }

    public static void main(String[] args) {
        double[] arr = {21,43,5,67,11,87,33,2};
        int left = 0;
        int right = arr.length-1;
        int key = 21;
        arrToString(arr,"未排序：");
        mergeSort(arr,0,arr.length-1);
        arrToString(arr,"排序后：");
        System.out.println("循环次数："+count);
        System.out.println("数组21,43,5,67,11,87,33,2，排序后二分查找21的索引结果为：");
        System.out.println(binarySearch(arr,left,right,key));
    }
}

二叉树的创建和遍历

思路：
1.定义一个二叉树类BinaryTree
2.调用本类去定义三个变量left,root,right
3.定义一个BinaryTree类型的集合datas，用于存放节点
4.定义一个Object类型的data用于存放实际数据
5.建立left,root,right的构造方法
6.初始化二叉树，将左右节点都置空

//将初始的左右孩子置为空
    public BinaryTree(Object data){
        this(null,null,data);
    }

7.创建二叉树创建方法create，设置参数为Object[] objs
8.将传入的数组转换为BinaryTree类型，存储到datas中
9.设置节点数组的第一个为根节点，之后的奇数索引为左节点，偶数索引为右节点
10.先序中序后序遍历分别为：根左右，左根右，右左根

代码如下：

package com.sumiya.binarytree;

import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
    private static String str = "";
    private BinaryTree root;
    private BinaryTree left;
    private BinaryTree right;

    //数据域
    private Object data;
    //存节点
    public List<BinaryTree> datas;

    public BinaryTree(BinaryTree left, BinaryTree right,Object data){
        this.left = left;
        this.right = right;
        this.data = data;
    }
    //将初始的左右孩子置为空
    public BinaryTree(Object data){
        this(null,null,data);
    }
    public BinaryTree(){

    }

    public void create(Object[] objs){
        datas = new ArrayList<BinaryTree>();
        //将传入的数组转换为node
        for (Object obj : objs) {
            datas.add(new BinaryTree(obj));
        }
        //设置节点数组的第一个为根节点，之后的奇数索引为左节点，偶数索引为右节点
        root = datas.get(0);
        for(int i =0;i<objs.length/2;i++){
            //左孩子
            datas.get(i).left=datas.get(i*2+1);
            str+=datas.get(i).left.data+"\t";
            //防止超出数组范围
            if(i*2+2<datas.size()){
                datas.get(i).right = datas.get(i*2+2);
                str+=datas.get(i).right.data+"\t";
            }
        }
    }

    //先序
    public void preorder(BinaryTree root){
        if(root!=null){
            System.out.print(root.data+"\t");
            preorder(root.left);
            preorder(root.right);
        }
    }
    //中序
    public void midOrder(BinaryTree root){
        if (root!=null){
            midOrder(root.left);
            System.out.print(root.data+"\t");
            midOrder(root.right);
        }
    }
    //后序
    public void lastOrder(BinaryTree root){
        if (root!=null){
            lastOrder(root.left);
            lastOrder(root.right);
            System.out.print(root.data+"\t");
        }
    }


    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        Object[] data = {2,4,5,7,1,6,12,32,51,22};
        bt.create(data);
        //创建后的二叉树
        System.out.println("创建后的二叉树为："+str);
        System.out.print("前序遍历结果为："+"\t");
        bt.preorder(bt.root);
        System.out.println();
        System.out.print("中序遍历结果为："+"\t");
        bt.midOrder(bt.root);
        System.out.println();
        System.out.print("后序遍历结果为："+"\t");
        bt.lastOrder(bt.root);
    }
}