CalculateForJava

~Java数据结构与算法～

时间复杂度
排序
查找
哈希表
线性表
链表
队列
栈
递归
树

时间复杂度

算法函数的常数可以忽略
算法函数幂指数前的常数项可以进行忽略
幂越小说明耗费的时间越少

常见的时间复杂度

以下的时间复杂度逐渐变大

O(1)

只要没有循环时间复杂度就是O(1)

O(log2n)
while(i < n){
i *= 2;
}
//x = log2n

O(n);

for(int i = 0;i < n;i++){
		j = i;
		j++;
}
//这段代码会判断n + 1遍 时间复杂度是O(n)

O(nlog2n)
O(n)里面套了一个O(log2n)
O(n ^ 2)
O(n)里面套了一个O(n);
O(n ^ 3)
O(n ^ k)
O(2 ^ n)

排序

冒泡排序

原理：俩俩比较，俩俩交换，最后将最大值放到最右边
一共进行了数组-1次大的循环
每一次循环的次数在不断减少
时间复杂度O(n * 2)
优化：可以判断交换次数，如果没有发生交换可以提前结束

代码实现

核心代码

int[] arr = {-2,5,1,3,6};
int temp = 0;
//一次for循环,总共需要四回
for(int i = 0;i < arr.length - 1;i++){
			if(arr[i] > arr[i + 1]){
				temp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = temp;
			}
}

成品展示

int temp = 0;
for(int i = 0;i < arr.length - 1;i++){
    for(int j = 0;j < arr.length - 1 - i;j++){
        if(arr[j] > arr[j + 1]){
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}
System.out.println(Arrays.toString(arr));

优化

boolean flag = false;
for(int j = 0;j < arr.length - i - 1;j++){
    if(arr[j] > arr[j + 1]){
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        flag = true;
    }
}
//如果未发生交换break
if(!flag){
    break;
}else {
    flag = false;
}

选择排序

原理：从第一个元素开始，与后面的元素进行比对，发现一个最小的将值赋值给他，让最小索引等于他
时间复杂度O(n * 2) —– 时间比冒泡少了很多

代码实现

第一次排序

int min = arr[0];
int minIndex = 0;
for(int i = 0 + 1;i < arr.length;i++){
    if(min > arr[i]){
        min = arr[i];
        minIndex = i;
    }
}
if(minIndex != 0){
    arr[minIndex] = arr[0];
    arr[0] = min;
}

成品展示

for(int j = 0;j < arr.length - 1;j++){
    int min = arr[j];
    int minIndex = j;
    for(int i = j + 1;i < arr.length;i++){
        if(min > arr[i]){
            min = arr[i];
            minIndex = i;
        }
    }
    if(minIndex != j){
        arr[minIndex] = arr[j];
        arr[j] = min;
    }
}

插入排序

原理：从第二个元素开始不断的往前面插入合适的位置

代码

核心代码

int insertVal = arr[1];
//代表的是插入元素的索引
int insertIndex = 1 - 1;
while(insertIndex >= 0 && insertVal < arr[insertIndex]){
    arr[insertIndex + 1] = arr[insertIndex];
    insertIndex--;
}
arr[insertIndex + 1] = insertVal;
System.out.println(Arrays.toString(arr));
return arr;

成品代码

for(int i = 1;i < arr.length;i++){
    int insertVal = arr[i];
    //代表的是插入元素的索引
    int insertIndex = i - 1;
    while(insertIndex >= 0 && insertVal < arr[insertIndex]){
        arr[insertIndex + 1] = arr[insertIndex];
        insertIndex--;
    }
    arr[insertIndex + 1] = insertVal;
    System.out.println(Arrays.toString(arr));
}

希尔排序

原理：将一组数/2分成多组进行排序，直到最后等于零为止，相当于是插入排序的进阶版

代码

采用交换法的希尔排序

for(int h = arr.length / 2;h > 0;h /= 2){
    for(int i = h;i < arr.length;i++){
        for(int j = i - h;j >= 0;j -= h){
            if(arr[j] > arr[j + h]){
                int temp = arr[j];
                arr[j] = arr[j + h];
                arr[j + h] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

采用移动法的希尔排序

for(int gap = arr.length / 2;gap > 0;gap /= 2){
    for(int j = gap;j < arr.length;j++){
        int i = j;
        int temp = arr[i];
        if(arr[i] < arr[i - gap]){
            while(i - gap >= 0 && temp < arr[i - gap]){
                arr[i] = arr[i - gap];
                i -= gap;
            }
            arr[i] = temp;
        }
    }
}

归并排序

原理：假如比较的是4578 1236将数组分成两半，重新定义一个新数组，首先比较4和1谁小放入到新数组中，然后小的向后移接着进行比较
注意点
- 有n个数进行排序，就合并了n - 1次

代码

合代码

public static void MergeSort(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;
        int j = mid + 1;
        int t = 0;
        while(i <= mid && j <= right){
            if(arr[i] <= arr[j]){
                temp[t] = arr[i];
                t++;
                i++;
            }else {
                temp[t] = arr[j];
                t++;
                j++;
            }
        }

        while(i <= mid){
            temp[t] = arr[i];
            t++;
            i++;
        }

        while(j <= right){
            temp[t] = arr[j];
            t++;
            j++;
        }
        //从头到尾将新数组拷贝到原数组中
        t = 0;
        int tempLeft = left;
        while(tempLeft <= right){
            arr[tempLeft] = temp[t];
            tempLeft++;
            t++;
        }

    }

分代码

public static void divideSort(int[] arr,int left,int right,int[] temp){
        if(left < right){
            int mid = (left + right) / 2;
            //左递归
            divideSort(arr,left,mid,temp);
            //右递归
            divideSort(arr,mid + 1,right,temp);
            //合并
            MergeSort(arr,left,mid,right,temp);

        }
    }

快速排序

原理：以这组数据的中间值为标准，将数据分为左递归和右递归，在左边找到比这个中间值大的和在右边找到比中间值小的进行交换

代码

public static void QuickSort(int[] arr,int left,int right){
        int l = left;
        int r = right;
        int temp = 0;
        int pivot = arr[(left + right) / 2];
        while(l < r){
            while(arr[l] < pivot){
                l++;
            }

            while(arr[r] > pivot){
                r--;
            }

            if(l >= r){
                break;
            }
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //两边的值交换完毕

            //如果发现交换后左边的值等于pivot
            if(arr[l] == pivot){
                r -= 1;
            }
            if(arr[r] == pivot){
                l += 1;
            }
        }
        if(l == r){
            l += 1;
            r -= 1;
        }
        if(left < r){
            QuickSort(arr,left,r);
        }
        if(right > l){
            QuickSort(arr,l,right);
        }

    }

基数排序

原理：将每一个元素的个位取出并放入0-9对应的桶中，然后是十位，如果没有的话进行补零操作
缺点：不能对负数进行排序，由于有10个桶的原因可能会浪费很多的内存

代码

核心代码

System.out.println(Arrays.toString(arr));

        for(int i = 0;i < arr.length;i++){
            int digitalEle = arr[i] / 1 % 10;
            bucket[digitalEle][bucketElement[digitalEle]] = arr[i];
            bucketElement[digitalEle]++;
        }

        index = 0;
        for(int i = 0;i < 10;i++){
            if(bucketElement[i] != 0){
                for(int l = 0;l < bucketElement[i];l++){
                    arr[index] = bucket[i][l];
                    index++;
                }
            }
            bucketElement[i] = 0;
        }
        System.out.println(Arrays.toString(arr));

完整代码

public static void RadixSort(int[] arr){
        //寻找最大数
        int max = arr[0];
        for(int i = 1;i <arr.length;i++){
            if(arr[i] > max){
                max = arr[i];
            }
        }
        int length = (max + "").length();

        //基数排序是通过空间换时间的排序方法
        int[][] bucket = new int[10][arr.length];

        int[] bucketElement = new int[10];


        for(int h = 0,n = 1;h < length;h++,n *= 10){
            for(int i = 0;i < arr.length;i++){
                int digitalEle = arr[i] / n % 10;
                bucket[digitalEle][bucketElement[digitalEle]] = arr[i];
                bucketElement[digitalEle]++;
            }

            int index = 0;
            for(int i = 0;i < 10;i++){
                if(bucketElement[i] != 0){
                    for(int l = 0;l < bucketElement[i];l++){
                        arr[index] = bucket[i][l];
                        index++;
                    }
                }
                bucketElement[i] = 0;
            }
            System.out.println(Arrays.toString(arr));
        }
}

查找

线性查找

原理：从头到尾逐一进行比对,将查找值对应的下标进行返回

代码实现

public static int LineSearch(int[] arr,int value){
        for(int i = 0;i < arr.length;i++){
            if(arr[i] == value){
                return i;
            }
        }
        return -1;
    }

二分查找

原理：在一个有序数组里面进行查找,定义left和right通过mid值来判断是left移动还是right移动

代码实现

二分查找(当出现重复元素时只返回一个下标)

public static int BinarySearch(int[] arr,int left,int right,int value){
        //递归的终止条件
        if(left > right) return -1;
        int mid = (left + right) / 2;
        int midValue = arr[mid];
        if(midValue < value) {
            return BinarySearch(arr,mid + 1,right,value);
        }else if(midValue > value) {
            return BinarySearch(arr,left,mid - 1,value);
        }else {
            return mid;
        }
    }

二分查找升级版(将出现元素的所有下标放入到数组中)

public static List<Integer> BinarySearch2(int[] arr,int left,int right,int value){
        //递归的终止条件
        if(left > right) return new ArrayList<>();
        int mid = (left + right) / 2;
        int midValue = arr[mid];
        if(midValue < value) {
            return BinarySearch2(arr,mid + 1,right,value);
        }else if(midValue > value) {
            return BinarySearch2(arr,left,mid - 1,value);
        }else {
            List<Integer> list = new ArrayList<>();
            int temp = mid - 1;
            while(true){
                if(temp < 0 || arr[temp] != value){
                    break;
                }
                list.add(temp);
                temp -= 1;
            }
            list.add(mid);

            temp = mid + 1;
            while(true){
                if(temp >= arr.length || arr[temp] != value){
                    break;
                }
                list.add(temp);
                temp += 1;
            }
            return list;

        }
    }

插值查找

插值查找什么时候使用合适
- 插值查找要求数组有序
- 关键字分布比较连续
插值查找mid公式

mid = (left) + (right - left) * (findVal - arr[left]) / arr[right] - arr[left];

代码实现

public static int insertSea(int[] arr,int left,int right,int value){
        System.out.println("插值查找次数");
        //判断第一位大于value和最后一位小于value必须有 否则当value值过大或者过小就会出现越界的情况
        if(left > right || arr[0] > value || arr[arr.length - 1] < value){
            return -1;
        }
        int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
        int midValue = arr[mid];
        if(midValue < value){
            return insertSea(arr,mid + 1,right,value);
        }else if(midValue > value){
            return insertSea(arr,left,mid - 1,value);
        }else {
            return mid;
        }
    }

斐波那契查找

原理：主要是通过黄金分割点来配合斐波那契数列来进行查找的

代码

public static int maxSize = 20;
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8};
        System.out.println(fibSearch(arr,5));
    }

    public static int[] fib(){
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for(int i = 2;i < maxSize;i++){
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    //通过mid = low + F(k - 1) - 1来获取到下标
    public static int fibSearch(int[] arr,int key){
        int low = 0;
        int high = arr.length - 1;
        int k = 0; //用来斐波那契分割数值的下标
        int mid = 0;
        int[] f = fib(); //获取斐波那契数列
        while(high > f[k] - 1){
            k++;

        }
        int[] temp = Arrays.copyOf(arr,f[k]);
        for(int i = high + 1;i < temp.length;i++){
            temp[i] = arr[high];
        }

        while(low <= high){
            mid = low + f[k - 1] - 1;
            if(key < temp[mid]){
                high = mid - 1;
                k--;
            }else if(key > temp[mid]){
                low = low + 1;
                k -= 2;
            }else {
                if(mid <= high){
                    return mid;
                }else {
                    return high;
                }
            }
        }
        return -1;


    }

哈希表

简单介绍

哈希表又称散列表，它通过将关键码值映射到表中某一个位置来访问记录，从而达到加快查找数据的目的，底层还是使用链表来实现的

哈希表达实现

提前准备

定义一个员工

class Emp{
		public int id;
		public String name;
		public Emp next;
		public Emp(int id,String name){
				this.id = id;
				this.name = name;
		}
	
}

定义一个链表用来串联员工

class EmpLinkedList{
    private Emp head;

    public void add(Emp emp){
        if(head == null){
            head = emp;
            return;
        }
        Emp curEmp = head;
        while(true){
            if(curEmp.next == null){
                break;
            }
            curEmp = curEmp.next;

        }
        curEmp.next = emp;

    }

    public void list(){
        if(head == null){
            System.out.println("空链表");
            return;
        }
        Emp curEmp = head;
        while(true){
            System.out.printf("id = %d name = %s\n",curEmp.id,curEmp.name);
            if(curEmp.next == null){
                break;
            }
            curEmp = curEmp.next;
        }
    }

    public Emp findById(int id){

        if(head == null){
            return null;
        }

        Emp curEmp = head;
        while(true){
            if(curEmp.id == id){
                break;
            }

            if(curEmp.next == null){
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;
        }
        return curEmp;


    }

    public Emp deleteById(int id){
        if(head == null){
            return null;
        }

        Emp cur = head;
        Emp pre = head;
        while(true){
            if(cur.next == null){
                cur = null;
                break;
            }
            if(cur.id == id){
                break;
            }
            //用pre记录cur变化后前一个节点
            pre = cur;
            cur = cur.next;

        }
        if(cur == null){
            return null;
        }

        pre.next = cur.next;
        return cur;

    }


}

定义一个哈希表用来串联多条链表

class Hashtable{
    public int size;
    public EmpLinkedList[] empLinkedLists;

    public Hashtable(int size) {
        this.size = size;
        this.empLinkedLists = new EmpLinkedList[size];
        for(int i = 0;i < size;i++){
            empLinkedLists[i] = new EmpLinkedList();
        }
    }

    public void add(Emp emp){
        //通过员工的id来确定所在链表的位置
        int id = emp.id;
        int index = Hashfun(id);
        empLinkedLists[index].add(emp);
    }


    public void list(){
        for(int i = 0;i < size;i++){
            empLinkedLists[i].list();
        }
    }


    public Emp findById(int id) {
        // 先找到该 id 属于那一条链表
        int no = Hashfun(id);
        // 先判断边界
        if (no > size || no < 0) {
            System.out.printf("id = %d 异常，计算出目标链表为 %d \n", id, no);
            return null;
        }
        Emp emp = empLinkedLists[no].findById(id);
        if (emp == null) {
            System.out.printf("在第 %d 条链表中未找到 id = %d 的雇员 \n", no, id);
        } else {
            System.out.printf("在第 %d 条链表中找到 id = %d 的雇员, name = %s \n", no, id, emp.name);
        }
        return emp;
    }

    public Emp deleteById(int id) {
        // 先找到该 id 属于那一条链表
        int no = Hashfun(id);
        // 先判断边界
        if (no > size || no < 0) {
            System.out.printf("id = %d 异常，计算出目标链表为 %d \n", id, no);
            return null;
        }

        Emp emp = empLinkedLists[no].deleteById(id);
        if (emp == null) {
            System.out.printf("在第 %d 条链表中未找到 id = %d 的雇员，删除失败 \n", no, id);
        } else {
            System.out.printf("在第 %d 条链表中找到 id = %d 的雇员, name = %s ,删除成功\n", no, id, emp.name);
        }
        return emp;
    }
		//通过id来获取处于的链表
    public int Hashfun(int id){
        return id % size;
    }
}

线性表

实现线性表

构建T类存储元素的数组作为线性表的主体
实现方法
- get
- getLength
- Insert / InsetIndex
- remove
- clear
- isEmpty

遍历线性表

public Iterator<T> iterator(){
        return new SIterator();
    }

    private class SIterator implements Iterator{
        private int cursor;
        public SIterator(){
            this.cursor = 0;
        }
        @Override
        public boolean hasNext() {
            return cursor < N;
        }

        @Override
        public Object next() {
            return eles[cursor++];
        }
    }

对于线性表的容积的改变

扩容

public void resize(int newSize){
        T[] temp = eles;
        eles = (T[])new Object[newSize];
        for(int i = 0;i < N;i++){
            eles[i] = temp[i];
        }
    }

链表

构成链表的大体操作
- 创建节点
- 链接节点

单向链表

实现(书写方法)

方法	实现原理
get	从i开始通过for循环获取item
clear	head.next = null && N = 0
isEmpty	return this.N == 0
Insert	while(cur.next != null) 遍历完之后向后添加
insertIndex	pre遍历到前一个元素，newNode.next = pre.next;
remove	Pre.next = pre.next.next
indexOf	for(i = 0;n.next != null;i++)

get,clear,isEmpty,insert,insertInIndex,remove,indexOf

实现Iterator接口，方便对元素进行遍历

public Iterator<T> iterator() {
        return new LIterator();
    }
    //通过重写Iterator来实现遍历的目的
    private class LIterator implements Iterator{
        //定义一个头节点 方便进行遍历
        private Node n;
        public LIterator(){
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public T next() {
            n = n.next;
            return n.item;
        }
    }

双向链表
- 在定义节点的时候需要新增一个pre
链表的反转
- 思路
  
  将头节点指向尾节点，尾节点依次向前指向

队列

遵循先进先出的原则

队列初始化
- front 代表队列最前的元素
- rear代表队列尾部的元素
- 通过rear == maxSize - 1判断队列是否已经满
- 提供数组用来存储数据
- 构造方法front rear初始化为-1
- 最大容量以及数组的大小都需要外部手动设置

部分API实现

方法	实现原理
判断队列是否满	return maxSize - 1 == rear
判断队列是否为空	return front == rear
向队列里面添加数据	需要判断队列是否满arr[++rear] = n;
获取队列的数据	需要判断队列是否为空arr[++front];
显示队列的所有数据	需要判断队列是否为空遍历数组进行打印
显示队列的头数据	需要判断队列是否为空return arr[front + 1];

缺点

队列rear到头就结束了，无法去使用前面已经空的队列单元

队列的改进

初始化条件变化
- front 和 rear 初始值为0
- front指向第一个元素
- rear指向队列的倒数第二个位置
- 此时队列满的条件发生了变化为(rear + 1) % maxSize == front
- 空的条件还是一样的
- 队列中有效数据的个数为(rear + maxSize - front ) % maxSize

代码实现

改动的方法	改动
向队列里面添加数据	rear向后移动需要取模
从队列里拿出数据	int value = arr[front] front = (front + 1) % maxSize; return value;
展示队列里的所有数据	for(int i = front;i < front + maxSize) sout(i % maxSize)

栈

遵循先进后出的原理

数组模拟栈初始化步骤
- 需要一个栈顶，初始化为-1
- 栈的大小
- 模拟一个数组栈
- 书写一个构造方法指定数组的长度和栈的的大小

基本方法实现

方法	实现代码
isFull	return top == maxSize - 1
isEmpty	return top == -1
Push	if(isFull) return; stack[top++] = value
Pop	if(isEmpty) thorw new error; int value = stack[top] top–; return value
list	if(isEmpty) return; for(int i = top;j >= 0;j–){System.out.printf(“stack[%d]=%d\n”),i,stack[i]};

栈模拟计算器

数栈

如果遍历到的是数字直接入数栈
符号栈
- 如果符号栈内没有内容直接入栈
- 否则的话比较符号的优先级，如果当前的操作符的优先级大的话就直接入符号栈，否则pop出两个数进行运算

main方法书写

String expression = "1 + 3 * 2";
ArrayStack numStack = new ArrayStack(10);
ArrayStack operStack = new ArrayStack(10);
int index = 0;
int num1 = 0;
int num2 = 0;
int res = 0;
char ch = ' ';
String keetNum = "";
while(true){
		ch = express.charAt(index++);
		if(operStack.isOper(ch)){
			if(!operStack.isEmpty){
				if(operStack.properties(ch) <= operStack.properties(operStack.peek())){
						num1 = numStack.pop();
						num2 = numStack.pop();
						oper = operStack.pop();
						res = numStack.cal(num1,num2,oper);
						numStack.push(res);
						operStack.push(ch);
				}else {
					operStack.push(ch);
				}
			}else {
					operStack.push(ch);
			}
		}else {
				//这里面push的数字都是有对应的ASCII值的
				//如果是多位数进行运算的话结果就会出现问题
				numStack.push(ch - 48);
				
				//通过字符拼接的方式可以解决
				keepNum += ch;
				if(index == expression.length() - 1){
						numStack.push(Integer.parseInt(keepNum));
				}else {
					if(operStack.isOper(expression.charAt(index + 1))){
							numStack.push(Integer.parseInt(keepNum));
							keepNum = "";
					}
				}
				
				
		}
		index++;
		if(index == expression.length()){
				break;
		}
}

//开始进行真正的运算
while(true){
	if(operStack.isEmpty()){
			break;
	}else {
			num1 = numStack.pop();
			num2 = numStack.pop();
			oper = operStack.pop();
			res = numStack.cal(num1,num2,oper);
			numStack.push(res);
	}
}

栈的三种表达式
- 前缀表达式(波兰表达式)
  
  从右向左扫描，先将数扫描扫描到符号后弹出两个数进行运算
- 中缀表达式
  
  最常见的表达式
- 后缀表达式(逆波兰表达式)
  
  先读取两个数然后读取符号，进行运算，拿着这个运算后的数再读取下一个数，下一个符号，进行运算…..
逆波兰表达式模拟计算器
- 将字符串中的每一个数据放入到ArrayList中
- 遍历ArrayList集合，如果是多位数的话直接将其入栈否则的话pop出两个数进行一系列的运算，将计算后的结果入栈
- 最后将pop出最终的结果

中缀表达式转后缀表达式

大体思路
- ex: 2 + ((2 + 3) * 5) - 5 => 2 2 3 + 5 * + 5 -
- 初始化两个栈：符号栈喝存储中间结果的栈
- 遍历中缀表达式，当遇到运算符的时候比较优先级
- 如果符号栈为空或者栈顶运算符为( 直接压入栈
- 如果优先级比较高，直接压入栈
- 否则的话将s1栈顶的运算符压入s2栈顶
- 。。。。。

代码实现

//将后缀表达式的每一项存放到list当中
List<String> list = new ArrayList<>();
String str = "";
do{	
		//说明是非数字
		if((c = s.charAt(i)) > 57 || (c = s.charAt(i)) < 48){
				list.add(" " + s.charAt(i));
				i++;
		}else {
				//如果是一个数的话
				while(i < s.length() && (c = s.charAt(i)) <= 57 || (c = s.charAt(i)) >= 48){
						str += s.charAt(i); //进行多位数的拼接
						i++;
				}
				list.add(str);
		}
}while(i < s.length())
return ls;

//将后缀表达式的List转化为中缀表达式List
Stack s1 = new Stack<>();
List<String> s2 = new ArrayList<>();
for(int item : ss){
		if(item.match("\\d+")){
				s2.add(item);
		}else if(item.equals('('){
				s1.push(item)
		}else if(item.equals(')')){
				//如果遇到了右括号一次将符号栈内的符号pop直到遇到了(
				while(!s1.peek().equals('(')){
						s2.add(s1.pop());
				}
				//消除(括号
				s1.pop();
		}else {
				//判断优先级
				while(s1.size() != 0 && Operation.getValue(s1.peek() >= Operation.getValue(item))){
						//如果item的优先级小于栈顶的优先级的话直接栈顶放入s2
						s2.push(s1.pop());
				}
				//将最后那个符号放入到符号栈中
				s1.push(item);
		}
		while(s1.size() != 0){
				//将s1中的剩余符号压入s2中
				s2.add(s1.pop());
		}
}
//判断符号优先级
Class Operation{
		private static int ADD = 1;
		private static int SUB = 1;
		private static int DIV = 2;
		private static int MUL = 2;
		
		public static int getValue(String oper){
				int res = 0;
				switch{
					'+'
					'-',
					'*',
					'/'
				}
				return res;
		}
}

递归

递归调用规则
- 当程序调用一个方法的时候就会在栈内开辟一段独立的空间
- 递归必须逐渐与递归结束的条件逼近，否则就会出现栈溢出
应用场景
- 汉诺塔
- 迷宫
- 快排
- 八皇后

迷宫回溯代码实现

public static void main(String[] args) {
        //构建一个87的迷宫
        int[][] map = new int[8][7];
        for(int i = 0;i < 8;i++){
            map[i][0] = 1;
            map[i][6] = 1;
        }
        for(int i = 0;i < 7;i++){
            map[0][i] = 1;
            map[7][i] = 1;
        }

        map[3][1] = 1;
        map[3][2] = 1;
//        map[1][2] = 1;
//        map[2][2] = 1;

        for(int i = 0;i < map.length;i++){
            for(int j = 0;j < map[i].length;j++){
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

        setWay(map,1,1);
        System.out.println("新构建出来的地图");
        //输入新的地图
        for(int i = 0;i < map.length;i++){
            for(int j = 0;j < map[i].length;j++){
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static boolean setWay(int[][] map,int i,int j){
        /*
        0点代表没有走过 1代表墙 2代表通路可以走 3代表死路
         */
        if(map[6][5] == 2){
            return true;
        }else {
            if(map[i][j] == 0){
                map[i][j] = 2;
                if(setWay(map,i - 1,j)){
                    //向下走
                    return true;
                }else if(setWay(map,i,j + 1)){
                    return true;
                    //向右走
                }else if(setWay(map,i + 1,j)){
                    //向上走
                    return true;
                }else if(setWay(map,i,j - 1)){
                    //向左走
                    return true;
                }else {
                    //死路
                    map[i][j] = 3;
                    return false;
                }
            }else {
                return false;
            }
        }
    }

如果想要求出最短路径需要分别统计上右下左，上左下右，下左上右，下右上左四种长度

八皇后问题

实现思路
- 将第一个皇后放在第一行的第一个位置
- 第二个皇后放在第二行的第一个位置，如果不合适放到第二行的指定位置，后面都以此类推
- 当得到一组正确答案后开始将第一个皇后后移，其他的放到合适的位置从而达到多组解

代码实现

public class Queue8 {
    //定义有多少个皇后
    int max = 8;
    //数组用来存放皇后放置的位置
    int[] arr = new int[max];
    static int count = 0;
    public static void main(String[] args) {
        Queue8 q = new Queue8();
        q.check(0);
        System.out.println(count);

    }
    //编写一个方法用来放置皇后
    private void check(int n){
        if(n == 8){
            print();
            return;
        }
        for(int i = 0;i < max;i++){
            arr[n] = i;

            if(judge(n)){
                //如果不冲突 往下一个行的第一列开始
                check(n + 1);
            }
        }
    }



    //用来判断皇后放置的位置是否与前面的位置冲突
    private boolean judge(int n){
        for(int i = 0;i < n;i++){
            //如果放入皇后的位置和前面放置皇后的列和对角线一样的话
            //对角线的原理
            if(arr[i] == arr[n] || Math.abs(i - n) == Math.abs(arr[i] - arr[n])){
                return false;
            }
        }
        return true;
    }

    public void print(){
        count++;
        for(int i = 0;i < arr.length;i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

树

为什么要引入树的概念

树也是用来存储数据的，在之前我们通过数组来存储数据，但是由于数组的增删效率比较低，于是我们又引入了链表，但是查找起来效率又比较低，于是树就诞生了

常用术语

节点
根结点
父节点
子节点
叶子节点

没有子节点的节点
节点的权

节点的值
节点的路径

从root几点开始找到该节点的路线
层

root算第一层，依次向下递增
二叉树

最多只有两个子节点

前序查找

先判断当前节点是否是要查找的
如果不是的话再去查找左节点，如果左节点是空的话就通过递归前序查找接着查
左边查完没有的话再去查找右边
如果查找到了直接将值进行返回

中序遍历

判断当前节点是否要查找的需要写在左查找完事之后

后续遍历

判断当前节点是否要查找的需要写在左右查找完事之后

删除节点

大体思路
- 删除节点需要判断当前节点的子节点点是否是要删除的
- 如果子节点不为空，那么就是删除该节点，如果不为空的话接着向下进行递归
- 右子节点也是同理
- 如果上述步骤没有删除节点的话，需要向左子树进行递归删除
- 如果还是没有再向右子树进行递归删除

顺序存储二叉树

二叉树的存储特点

第n个元素的左子节点为2 * n + 1

第n个元素的右子节点为2 * n + 2

第n个元素的父节点为(n - 1) / 2

顺序二叉树代码实现

class ArrayBinaryTree{
    private int[] arr;
    public ArrayBinaryTree(int[] arr){
        this.arr = arr;
    }


    public void preOrdered(){
        this.preOrdered(0);
    }

    public void midOrdered(){
        this.midOrdered(0);
    }

    public void lastOrdered(){
        this.lastOrdered(0);
    }
		//前序遍历
    public void preOrdered(int index){
        if(arr == null || arr.length == 0){
            System.out.println("数组为空，无法进行遍历");
        }
        System.out.println(arr[index]);
        //向左进行递归
        if((index * 2 + 1) < arr.length){
            preOrdered(2 * index + 1);
        }

        if((index * 2 + 2) < arr.length){
            preOrdered(2 * index + 2);
        }

    }
		//中序遍历
    public void midOrdered(int index){
        if(arr == null || arr.length == 0) return;

        if((index * 2 + 1) < arr.length){
            midOrdered(index * 2 + 1);
        }

        System.out.println(arr[index]);

        if((index * 2 + 1) < arr.length){
            midOrdered(index * 2 + 2);
        }


    }
		//后序遍历
    public void lastOrdered(int index){
        if(arr == null || arr.length == 0) return;
        if(index * 2 + 1 < arr.length){
            lastOrdered(index * 2 + 1);
        }
        if(index * 2 + 2 < arr.length){
            lastOrdered(index * 2 + 2);
        }
        System.out.println(arr[index]);
    }

}

线索化二叉树

基本介绍

n个节点的二叉树链表中含有n + 1 个空指针域,公式为2n - (n - 1) = n + 1,存在指向该节点在某种遍历次序下的前驱和后继节点的指针，这种指针称为线索

在这里，left和right分别包含两种情况指向左子树，右子树或者是前驱节点和后继节点

代码实现

public void threadTree(HeroNode node){
        if(node == null) return;
        //先对左子树进行线索化
        threadTree(node.getLeft());
        //线索化当前节点
        //线索化前驱
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
				//线索化后继
        if(pre != null && node.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;

        //再线索化右子树
        threadTree(node.getRight());
    }

遍历线索化二叉树

public void threadList(){
        //从root节点开始进行遍历
        HeroNode node = root;
//        去查找leftType = 1的节点也就是前驱节点
        while(node != null){
            while(node.getLeftType() == 0){
                node = node.getLeft();
            }
            System.out.println(node);
            while(node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            node = node.getRight();


        }
    }

堆排序

简单介绍

堆排序是选择排序，不稳定，时间复杂度是O(nlogn), 每个节点的值都大于等于左右孩子的值称为大顶堆，每个孩子的值都小于等于左右孩子的值称为小顶堆
大体思想
1. 将待排序序列构建成一个大顶堆，此时最大值就是根结点
2. 将其与末尾元素进行交换，此时末尾就是最大值
3. 然后将剩余的元素重新构建成一个堆，接着上述操作就会得到一个有序的序列了

代码实现(升序排序)

public static void heapSort(int[] arr){
        int temp = 0;
        //对第一个非叶子节点进行调整
        //adjustHeap(arr,1,arr.length);
        //对第二个非叶子点进行调整
        //adjustHeap(arr,0, arr.length);

        //1.通过非叶子节点对数组进行调整
        for(int i = arr.length / 2 - 1;i >= 0;i--){
            adjustHeap(arr,i,arr.length);
        }
        System.out.println(Arrays.toString(arr));

        //2.使最大元素沉底
        for(int j = arr.length - 1;j > 0;j--){
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr,0,j);
        }

        System.out.println(Arrays.toString(arr));


    }
    
    public static void adjustHeap(int[] arr,int i,int length){
        //保留最初始的值，因为后面要不断的对arr[i]进行修改
        int temp = arr[i];
        for(int k = i * 2 + 1;k < length;k = k * 2 + 1){
            if(k + 1 < length && arr[k] < arr[k + 1]){
                //让k指向右子节点
                k++;
            }
            if(arr[k] > temp){
                //将大值赋值给非叶子节点
                arr[i] = arr[k];
                //将i指向k接着向下进行该操作
                i = k;
            }else {
                break;
            }
        }

        arr[i] = temp;
    }

哈夫曼树

概念

路径的基本概念：从根结点出发到达孩子或者是孙子节点的通路叫做路径，路径的公式是L - 1

带权路径的长度(WPL)计算公式: 叶子节点的权 * 路径

带权路径长度最小的值就是哈夫曼树

构建哈夫曼树

public static Node createHuffmanTree(int[] arr){
        //1. 将数组中的每一个元素放入到集合当中
        List<Node> list = new ArrayList<>();
        for(int val : arr){
            list.add(new Node(val));
        }
        while(list.size() != 1){
            //对集合进行排序
            Collections.sort(list);

            //取出两个权值最小的子节点
            Node node1 = list.get(0);
            Node node2 = list.get(1);
            //计算两个树的和并且将两个子节点挂在到他两边
            Node parent = new Node(node1.val + node2.val);
            parent.left = node1;
            parent.right = node2;

            list.remove(node1);
            list.remove(node2);

            list.add(parent);

        }
        return list.get(0);



    }
    //最终返回到是哈夫曼树的根结点，通过这个根结点进行前序遍历

哈夫曼编码

通信编码发展史
- 通过ASCII码值值转二进制来解决，但是二进制码长度过大，不方便解析
- 变长编码： 1 : a 01 : b这种方式但是可能会出现解析重码的可能，信息解析错误
- 哈夫曼编码
原理图

思路分析

Node {data(存放数据) ，wieght(存放出现的个数) , left , right}

class HNode implements Comparable<HNode>{
    Byte data; //存放数据本身
    int weight; //数字的权重
    HNode left;
    HNode right;

    public HNode(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }


    @Override
    //从小到大进行排序
    public int compareTo(HNode o) {
        return weight - o.weight;
    }

    @Override
    public String toString() {
        return "HNode{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    public void preOrder(){
        System.out.println(this);
        if(this.left != null){
            this.left.preOrder();
        }

        if(this.right != null){
            this.right.preOrder();
        }

    }
}

得到字符对应的byte数组
将数据以及个数一块放入到List数组中
通过List创建哈夫曼树
创建一个Map<Byte,String> 从来存储子节点和其对应的哈希编码
创建一个StringBuffer用来拼接路径作为哈希编码
压缩字符串

		//封装一个方法用来执行整个步骤
    private static byte[] huffmanZip(byte[] bytes){
        //通过byte创建集合
        List<HNode> nodes =  getNodes(bytes);
        //通过集合构建哈夫曼树
        HNode huffmanTree = createHuffmanTree(nodes);
        //通过哈夫曼树来获取Map映射
        Map<Byte,String> huffCode = getCodes(huffmanTree);
        //最后进行压缩操作
        byte[] res = zip(bytes,huffCode);
        return res;
    }


		//将字符串转化的byte数组通过Map映射
		public static List<HNode> getNodes(byte[] bytes){
        List<HNode> list = new ArrayList<>();
        Map<Byte,Integer> map = new HashMap<>();
        for(byte b : bytes){
            map.put(b,map.getOrDefault(b,0) + 1);
        }
        //将每一个键值对转化成为一个Node对象，并加入到nodes集合中
        for(Map.Entry<Byte,Integer> entry : map.entrySet()){
            list.add(new HNode(entry.getKey(),entry.getValue()));
        }
        return list;
    }
		//构建哈夫曼树
    public static HNode createHuffmanTree(List<HNode> nodes){
        while(nodes.size() > 1){
            Collections.sort(nodes);
            HNode node1 = nodes.get(0);
            HNode node2 = nodes.get(1);
            HNode parent = new HNode(null,node1.weight + node2.weight);
            parent.left = node1;
            parent.right = node2;

            nodes.remove(node1);
            nodes.remove(node2);

            nodes.add(parent);

        }
        return nodes.get(0);
    }

    //将哈夫曼编码放入到Map<Byte,String>中
    static Map<Byte,String> huffmanCode = new HashMap<Byte,String>();

    //生成哈夫曼编码需要拼接路径
    static StringBuilder stringBuilder = new StringBuilder();


    private static Map<Byte,String> getCodes(HNode root){
        if(root == null){
            return null;
        }
        getCodes(root.left,"0",stringBuilder);
        getCodes(root.right,"1",stringBuilder); 
        return huffmanCode;
    }

    /**
     * 功能：获取所有node节点的叶子节点，并且放入到huffmanCode集合中
     * @param node 传入节点
     * @param code 路径 左子节点 0 右子节点 1
     * @param stringBuilder 用来拼接路径
     */
    private static void getCodes(HNode node,String code,StringBuilder stringBuilder){
        StringBuilder sb = new StringBuilder(stringBuilder);
        sb.append(code);
        if(node != null){
            if(node.data == null){
                //当访问的节点是非叶子节点
                //向左进行递归
                getCodes(node.left,"0",sb);
                //向右递归
                getCodes(node.right,"1",sb);
            }else {
                //叶子节点
                huffmanCode.put(node.data,sb.toString());

            }

        }

    }
		//将原来的byte数组根据huffman表进行压缩处理 即二进制转化成十进制进行返回的操作
		private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCode){
        //利用哈夫曼表将原来的byte数组转化成新的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for(byte b : bytes){
            stringBuilder.append(huffmanCode.get(b));
        }

        int len;
        if(stringBuilder.length() % 8 == 0){
            len = stringBuilder.length() / 8;
        }else {
            len = stringBuilder.length() / 8 + 1;
        }

        //创建压缩后的byte数组
        byte[] by = new byte[len];
        int index = 0;
        for(int i = 0;i < stringBuilder.length();i += 8){
            //substring(i,i + 8)是可能出现越界的情况
            String str;
            if(i + 8 > stringBuilder.length()){
                //这么写也相当于是从这个点开始截取到最后
                str = stringBuilder.substring(i);
//                str = stringBuilder.substring(i, stringBuilder.length());
            }else {
                str = stringBuilder.substring(i,i + 8);
            }
            //将八位二进制转化成十进制放入到byte数组当中
            by[index++] = (byte) Integer.parseInt(str,2);

        }

        return by;



    }

解压数据代码

//数据的解压
    //对压缩数据进行解压
    public static byte[] decode(Map<Byte,String> huffmanCode,byte[] huffmanBytes){
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0;i < huffmanBytes.length;i++){
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag,huffmanBytes[i]));

        }

        Map<String,Byte> map = new HashMap<String,Byte>();
        for(Map.Entry<Byte,String> origin : huffmanCode.entrySet()){
            map.put(origin.getValue(),origin.getKey());
        }
        List<Byte> list = new ArrayList<>();
        for(int i = 0;i < stringBuilder.length();){
            int count = 1;
            boolean flag = true;
            Byte b = null;
            while(flag){
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if(b == null){
                    count++;
                }else {
                    flag = false;
                }
            }
            list.add(b);
            i += count;
        }
        byte[] b = new byte[list.size()];
        for(int i = 0;i < list.size();i++){
            b[i] = list.get(i);
        }
        return b;




    }


    //将十进制转化成二进制的方法
    private static String byteToBitString(boolean flag,byte b){
        int temp = b;
        //将十进制转化成二进制
        //但是如果传入的是正数的话前面的零会省略掉
        //ex: -1 -> 10000001   1 -> 1
        //我们需要进行补位 |
        //按位与的规则是相同的不变不同的1来覆盖
        //256 -> 100000000 | 00000001 -> 100000001 截取八位就是00000001
        //如果满足八位才进行按位与的操作
        if(flag){
            temp |= 256;
        }



        String str = Integer.toBinaryString(temp);
        //这也是判断是否有八位的可能
        if(flag){
            return str.substring(str.length() - 8);
        }else {
            return str;
        }


    }

使用哈夫曼编码对文件进行压缩

//srcFile 希望压缩的文件的路径
    //destFile 压缩到那个目录
    public static void fileZip(String srcFile,String destFile){
        FileInputStream is = null;
        OutputStream os = null;
        ObjectOutputStream oos = null;
        try {
            //创建文件的输入流
            is = new FileInputStream(srcFile);
            //创建一个和源文件一样大小的byte数组
            byte[] b = new byte[is.available()];
            //将srcFile文件读取到b中
            is.read(b);
            //对文件进行压缩操作
            byte[] res = huffmanZip(b);
            //创建文件的输出流 存放压缩文件
            os = new FileOutputStream(destFile);
            //创建一个和输出流相关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            //通过对象流的方式写入哈夫曼编码后的字节文件
            oos.writeObject(res);
            //再将哈夫曼编码写入到压缩文件中
            oos.writeObject(huffmanCode);

        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                is.close();
                os.close();
                oos.close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

    }

对文件进行解压

/**
     *
     * @param zipFile 需要解压的文件
     * @param destFile 解压到哪里
     */
    public static void unzip(String zipFile,String destFile){
        InputStream is = null;
        ObjectInputStream ois = null;
        OutputStream os = null;
        try{
            //创建文件输入流
            is = new FileInputStream(zipFile);
            //创建和is相关联的对象输入流
            ois = new ObjectInputStream(is);
            //读取byte数组和哈夫曼表
            byte[] huffmanBytes = (byte[])ois.readObject();
            Map<Byte,String> huffmanCode = (Map<Byte,String>)ois.readObject();
            //解码
            byte[] bytes = decode(huffmanCode,huffmanBytes);
            //写入目标文件中
            os = new FileOutputStream(destFile);
            os.write(bytes);
        }catch (Exception e){
            System.out.println(e.getMessage());
        }finally {
            try {
                is.close();
                os.close();
                ois.close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    }

哈夫曼编码压缩文件注意事项
- 如果文件本身经过了压缩，压缩效率不会有明显的变化
- 哈夫曼编码按字节处理，因此可以处理所有的文件
- 文件内容重复数据不多，压缩内容不明显

二叉排序树(BST)

简单介绍

通过非叶子节点左边比当前值小，右边比当前值大的机制来进行排序

二叉排序树的创建与遍历

class BinaryTree{
    private Node root;
    //添加节点的方法
    public void add(Node node){
        if(root == null) root = node;
        else root.addNode(node);



    }


    public void midOrdered(){
        if(root != null){
            root.midOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }
}



class Node{
    Node left;
    Node right;
    int val;

    public Node(int val) {
        this.val = val;
    }
    //添加节点的方式
    public void addNode(Node node){
        if(node == null) return;
        //判断添加进来的节点和当前节点的大小
        if(node.val < this.val){
            //如果当前节点的左子姐弟哪为null
            if(this.left == null){
                this.left = node;
            }else {
                this.left.addNode(node);
            }

        }else {
            if(this.right == null){
                this.right = node;
            }else {
                this.right.addNode(node);
            }

        }
    }
    //中序遍历
    public void midOrder(){
        if(this.left != null){
            this.left.midOrder();
        }

        System.out.println(this);
        if(this.right != null){
            this.right.midOrder();
        }
    }

}

二叉排序树的删除

思路分析

第一种情况

删除叶子节点

首先需要找到删除的结点

找到他的父结点，判断是左子结点还是右子结点

通过parent.left = null ,parent.right = null

第二种情况

删除只有一棵子树的节点

定义当前节点为curNode 父节点为parent

如果当前节点有左子结点，curNode是父节点的左子节点

parent.left = curNode.left

如果当前节点有右子结点，curNode是父节点的左子节点

parent.left = curNode.right

如果当前节点有右子结点，curNode是父节点的右子节点

parent.right = curNode.right

如果当前节点有左子结点，curNode是父节点的右子节点

parent.right = curNode.left

第三种情况

删除有两个子树的结点

找到删除结点的结点curNode

用一个临时变量存储当前结点右子树中最小的结点

curNode.val = temp;

查找当前节点代码

public Node searchVal(int val){
        //如果查找的节点等于当前节点将其进行返回
        if(val == this.val){
            return this;
        }else if(val > this.val){
            //如果查找的节点大于当前节点将其进行返回 往右找
            if(this.right == null) {
                //说明找不到
                return null;
            }
            return this.right.searchVal(val);
        }else {
            if(this.left == null){
                return null;
            }
            return this.left.searchVal(val);
        }
    }

查找父节点

//查找当前节点的父结点
    public Node searchParent(int val){
        if(this.left != null && this.left.val == val || this.right != null && this.right.val == val){
            return this;
        }else {
            if(val < this.val && this.left != null){
                return this.left.searchParent(val);
            }else if(val >= this.val && this.right != null){
                return this.right.searchParent(val);
            }else {
                return null;
            }
        }

    }

删除节点

//删除最小节点的代码(用来删除左右都有子节点的节点) 
    public int delMinNode(Node root){
        Node cur = root;
        while(cur.left != null){
            cur = cur.left;
        }
        delNode(cur.val);
        return cur.val;
    } 

//删除节点代码
    public void delNode(int value){
        if(root == null) {
            return;
        }else {
            // 查找删除的节点
            Node cur = searchCur(value);
            if(cur == null) return;

            //如果删除当前节点没有父亲那么说明当前节点一定是root节点
            if(root.left == null && root.right == null) {
                root = null;
                return;
            }

            Node parent = searchParent(value);
            //代表删除的节点是叶子节点
            if(cur.left == null && cur.right == null){
                if(parent.left != null && parent.left.val == cur.val ){
                    parent.left = null;
                }else if(parent.right != null && parent.right.val == cur.val) {
                    parent.right = null;
                }
            }else if(cur.left != null && cur.right != null){
                //寻找到右子树中最小的值
                int minVal = delMinNode(cur.right);
                //让最小的值代替当前值
                cur.val = minVal;
            }else {
                //如果删除的左子节点
                if(cur.left != null){
                    if(parent.left.val == value) {
                        parent.left = cur.left;
                    }else {
                        parent.right = cur.left;
                    }
                }else {
                    //删除的如果是右子结点
                    if(parent.left.val == value){
                        parent.left = cur.right;
                    }else {
                        parent.right = cur.right;
                    }
                }

            }



        }
    }

删除二叉树注意点当删除到最后只有两个结点，并且此时可能根结点发生变化的话需要判断parent是否为空

if(cur.left != null){
    if(parent != null){
        if(parent.left.val == value) {
            parent.left = cur.left;
        }else {
            parent.right = cur.left;
        }
    }else {
        root = cur.left;
    }
}else {
    if(parent != null){
        //删除的如果是右子结点
        if(parent.left.val == value){
            parent.left = cur.right;
        }else {
            parent.right = cur.right;
        }
    }else {
        root = cur.right;
    }
}

平衡二叉树(AVL树)

简单介绍

平衡二叉树指的是左子树和右子树高度差的绝对值不超过1
图解

左高度，右高度求解

//返回左子树的高度
    public int LeftHeight(){
        if(left == null){
            return 0;
        }else {
            return left.height();
        }
    }


    //返回右子树的高度
    public int rightHeight(){
        if(right == null) {
            return 0;
        }else {
            return right.height();
        }
    }

    //返回树的高度
    public int height(){
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

左旋转和右旋转

目的：为了使保证左子树和右子树的高度差小于等于1，从而实现平衡二叉树

public void leftRotate(){
       Node newNode = new Node(val);
       newNode.left = left;
       newNode.right = right.left;
       val = right.val;
       newNode.right = right.right;
       left = newNode;
    
   }
    
   private void rightRotate(){
       Node newNode = new Node(val);
       newNode.right = right;
       newNode.left = left.right;
       val = left.val;
       left = left.left;
       right = newNode;
    
   }

双旋转

什么时候出现双旋转，当出现子树的左子节点和右子节点相差过大的时候就会需要双旋转来解决实际问题?

ex : int[] arr = {10,11,7,6,8,9}

双旋转的思路是先将子树左右节点差过大的那个节点进行左旋或者是右旋使该子树平衡再回到根结点接着进行左旋或者右旋使树变为平衡二叉树

//添加完节点判断是否要进行左旋转
if(rightHeight() - LeftHeight() > 1){
    if(right != null && right.LeftHeight() > right.rightHeight()){
        right.rightRotate();
        leftRotate();
    }else {
        leftRotate();
    }
    return;
}
if(LeftHeight() - rightHeight() > 1){
    if(left != null && left.rightHeight() > left.LeftHeight()){
        left.leftRotate();
        rightRotate();
    }else {
        rightRotate();
    }
}

多路查找树

B树，B+树

每一个节点存储的数据量上升，高度减少，不止有left和right，效率明显提升

应用场景：用于制作文件索引系统

B*树：在B+树的基础上在兄弟级节点之间建立了桥梁

图

基本概念

图是一种数据结构，用来处理多对多的情况
表达方式
- 邻接矩阵
  
  用来表示两个顶点之间的连通关系
- 邻接表

实现图

初始化变量

//从来存储顶点的
    private ArrayList<String> vertList;


    //定义二维数组
    private int[][] matrix;
    //线的个数
    private int num;
    public Graph(int n){
        matrix = new int[n][n];
        vertList = new ArrayList<>(n);
    }

定义方法

//插入结点
   public void insertNode(String str){
       vertList.add(str);
   }
    
   //添加边
   public void addAngle(int x,int y,int n){
       matrix[x][y] = n;
       matrix[y][x] = n;
       num++;
   }
    
    
   //返回权值
   public int getVal(int x,int y){
       return matrix[x][y];
   }
    
    
   public void showEdge(){
       for(int[] arr : matrix){
           System.out.println(Arrays.toString(arr));
       }
   }

显示邻接矩阵

public static void main(String[] args) {
        int n = 5;
        String[] str = {"A","B","C","D","E"};
        Graph g = new Graph(n);
        //将顶点放入集合中
        for(String s : str){
            g.insertNode(s);
        }

        //添加边
        //A-B A-C B-C B-D B-E
        g.addAngle(0,1,1);
        g.addAngle(0,2,1);
        g.addAngle(1,2,1);
        g.addAngle(1,3,1);
        g.addAngle(1,4,1);

        g.showEdge();

    }

深度优先搜索(DFS)

每一次访问都在访问当前结点的邻接点

算法实现步骤

访问初始结点，标记为已连接
判断当前结点的下一个邻接点是否和当前结点连通，如果连通的话，就以将下一个结点作为起点重复上述操作
如果不连通的话，回到当前结点的上一个结点判断是否和该节点连通

public class Graph {
    //存储顶点集合
    private ArrayList<String> arrayList;
    private int[][] edges;
    //边的个数
    private int num;
    //记录结点是否被访问
    private boolean[] isVisited;

    public static void main(String[] args) {
        int n = 5;
        String[] str = {"A","B","C","D","E"};
        Graph g = new Graph(n);
        for(String s : str){
            g.insertArrayList(s);
        }
        // A-B A-C B-C B-D B-E
        g.insertEdge(0,1,1);
        g.insertEdge(0,2,1);
        g.insertEdge(1,2,1);
        g.insertEdge(1,3,1);
        g.insertEdge(1,4,1);
        g.showGraph();

        g.dfs();

    }


    public Graph(int n){
        arrayList = new ArrayList<>(n);
        edges = new int[n][n];
        isVisited = new boolean[5];
    }

    /**
     *
     * @param v1 第一个顶点的下标
     * @param v2 第二个顶点的下标
     * @param weight 权值
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        num++;
    }


    public void insertArrayList(String str){
        arrayList.add(str);
    }


    public int getNumOfArrayLength(){
        return arrayList.size();
    }

    public int getEdgeNum(){
        return num;
    }

    public String getValueByIndex(int index){
        return arrayList.get(index);
    }

    public int getVal(int v1,int v2){
        return edges[v1][v2];
    }


    public void showGraph(){
       for(int[] arr : edges){
           System.out.println(Arrays.toString(arr));
       }
    }

    //
    public int getFirstNeighbor(int index){
         for(int j = 0;j < arrayList.size();j++){
             if(edges[index][j] > 0){
                 return j;
             }
         }
         return -1;
    }

    public int getNextNeighbor(int v1,int v2){
        for(int i = v2 + 1;i < arrayList.size();i++){
            if(edges[v1][i] > 0){
                return i;
            }
        }
        return -1;
    }


    public void dfs(boolean[] isVisited,int i){
        System.out.print(getValueByIndex(i) + "->");
        isVisited[i] = true;
        int w = getFirstNeighbor(i);
        while(w != -1){
            if(!isVisited[w]){
                dfs(isVisited,w);
            }
            w = getNextNeighbor(i,w);
        }
    }

    public void dfs(){
        for(int i = 0;i < getNumOfArrayLength();i++){
            if(!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }

}

时间复杂度

排序

冒泡排序

选择排序

插入排序

希尔排序

归并排序

快速排序

基数排序

查找

线性查找

二分查找

插值查找

斐波那契查找

哈希表

线性表

实现线性表

遍历线性表

对于线性表的容积的改变

链表

队列

队列的改进

栈

递归

树

为什么要引入树的概念

常用术语

前序查找

中序遍历

后续遍历

删除节点

顺序存储二叉树

线索化二叉树

堆排序

哈夫曼树

哈夫曼编码

二叉排序树(BST)

平衡二叉树(AVL树)

多路查找树

图

实现图

深度优先搜索(DFS)

广度优先搜索(BFS)