二叉树遍历的应用之分治法

/**
* 前提：已排好序的序列
* 注意：设计成左闭右开--是一种区间无重复的思想
* random(０，１)等大量的数学函数
* for(int i=0;i<array.length;i++）
*/
public int binarySearch(int[] array,int begin,int end,int key){
        if (begin > end){
            return -1;
        }
        int low = begin;
        int high = end - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            int midValue = array[mid];
            if (key > midValue) {// 往右边找
                low = mid + 1;
            } else if (key < midValue) {// 往左边找
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

/**
* 对应树的前序遍历，而汉诺塔对应的是中序遍历。应用场景：数据量大并且是线性结构，不适用链式结构或者数据大量重复的场景
*/
public void quickSort(int[] array,int begin,int end){
        if (begin > end){
            return;
        }
        int key = array[begin];
        int low = begin;
        int high = end;
        boolean direction = true;//true代表<--，false代表-->
        L1:
        while (low < high) {
            if (direction) {// 从右往左
                for (int i = high; i > low; i--) {
                    if (array[i] <= key) {
                        array[low++] = array[i];
                        high = i;
                        direction = !direction;
                        continue L1;
                    }
                }
                high = low;
            } else { // 从左往右找
                for (int i = low;i < high;i++){
                    if (array[i] >= key) {
                        array[high--] = array[i];
                        low = i;
                        direction = !direction;
                        continue L1;
                    }
                }
                low = high;
            }
        }
        // 把最后找到的值 放入中间位置
        array[low] = key;
        // 开始完成左右两边的操作
        quickSort(array,begin,low - 1);
        quickSort(array,low + 1,end);
    }

/**
* 对应树的后序遍历，应用场景就是数据量大并且是链式结构，但不是最好的，典型的空间换时间，适合大量重复数据
*/
public void mergeSort(int[] array,int begin,int end){
        if (begin >= end) {
            return;
        }
        int mid = (begin+end)/2;
        mergeSort(array,0,mid);// 分治
        mergeSort(array,mid+1,end);// 分治
        merge(array,begin,mid+1,end);// 归并,mid一定要加一
    }


    // 1 2 3 4 === 5 6 7 8
    public void merge(int[] array,int begin,int mid,int end){
        // 生成两个数组
        int leftSize = mid - begin;
        int rightSize = end - mid + 1;

        int[] leftArray = new int[leftSize];
        int[] rightArray = new int[rightSize];
        // 填充数据
        for (int i = begin;i < mid;i++){
            leftArray[i - begin] = array[i];
        }
        for (int i = mid;i <= end;i++){
            rightArray[i - mid] = array[i];
        }
        // 归并
        int leftIndex = 0;
        int rightIndex = 0;
        int originIndex = begin;

        while (leftIndex < leftSize && rightIndex < rightSize) {
            if (leftArray[leftIndex] < rightArray[rightIndex]) {
                array[originIndex] = leftArray[leftIndex];
                leftIndex++;
                originIndex++;
            } else {
                array[originIndex] = rightArray[rightIndex];
                rightIndex++;
                originIndex++;
            }
        }
        while (leftIndex < leftSize) {
            array[originIndex++] = leftArray[leftIndex++];
        }
        while (rightIndex < rightSize) {
            array[originIndex++] = rightArray[rightIndex++];
        }
    }