[数据结构与算法]数据结构与算法

数据结构

数据结构是一门研究组织数据方式的学科，有了编程语言也就有了数据结构，学好数据结构可以编写出更有效率的代码。数据结构是算法的基础，想要学好算法，就必须把数据结构学到位。

数据结构包括：线性结构、非线性结构。

线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性存储关系。线性结构有两种不同的存储结构，即顺序存储和链式存储。顺序存储的线性表被称为顺序表，顺序表中存储元素的地址是连续的；链式存储的线性表被称为链表，链表中存储元素的地址不一定是连续的，元素结点中存放数据元素以及相邻元素地址信息。

常见的线性结构有：数组、链表、队列、栈；常见非线性结构有：多维数组、广义表、树结构、图结构。

稀疏数组

使用稀疏数组可以用来压缩数据。稀疏数组的第一行依次记录原数组一共有几行几列，有多少个不为零的值，之后的每行记录原数组中不为零的值所在的行数、列数以及数组中元素该值。如图所示：

二维数组转稀疏数组

class TwoDimensionArrayDemo {
  // 将二维数组转换为稀疏数组
  public static int[][] twoDimensionArrayToSparseArray(int[][] array) {
    // 记录棋盘中有效值的数量
    int sum = 0;
    int row = array.length;
    int column = 0;
    for (int[] ints : array) {
      column = ints.length;
      for (int item : ints) {
        if (item != 0) {
          sum++;
        }
      }
    }

    // 创建稀疏数组
    int[][] sparseArray = new int[sum + 1][3];
    sparseArray[0][0] = row;
    sparseArray[0][1] = column;
    sparseArray[0][2] = sum;

    // 给稀疏数组赋值
    int count = 0;
    for (int i = 0; i < array.length; i++) {
      for (int j = 0; j < array[i].length; j++) {
        if (array[i][j] != 0) {
          count++;
          sparseArray[count][0] = i;
          sparseArray[count][1] = j;
          sparseArray[count][2] = array[i][j];
        }
      }
    }

    System.out.println("稀疏数组====》");
    for (int i = 0; i < sparseArray.length; i++) {
      System.out.printf("%d\t%d\t%d\t\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
    }
    return sparseArray;
  }
}

稀疏数组转二维数组

class TwoDimensionArrayDemo {
  // 稀疏数组转二维数组
  public static int[][] sparseArrayToTwoDimensionArray(int[][] sparseArray) {
    int[][] toTwoDimensionArray = new int[sparseArray[0][0]][sparseArray[0][1]];
    // 给二维数组赋值
    for (int i = 1; i < sparseArray.length; i++) {
      toTwoDimensionArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
    }

    System.out.println("二维数组====》");
    for (int[] row : toTwoDimensionArray) {
      for (int data : row) {
        System.out.printf("%d\t", data);
      }
      System.out.println();
    }
    return toTwoDimensionArray;
  }
}

队列

队列是一个有序列表，可以使用数组或链表来实现。队列遵循先入先出的原则。即，先存入队列的数据，要先取出。后存入的要后取出。

使用数组模拟队列示意图：

数组模拟单向队列

    public class ArrayQueue{

        // 队列容量
        private int capacity;

        // 保存队列中的数据
        private int[] arr;

        // 头部指针
        private int front;

        // 尾部指针
        private int rear;

        public ArrayQueue(int capacity) {
            this.capacity = capacity;
            arr = new int[capacity];
            front = -1;
            rear = -1;
        }

        public boolean isEmpty() {
            return front == rear;
        }

        public boolean isFull() {
            return capacity - 1 == rear;
        }

        public void add(int data) {
            if (isFull()) {
                System.out.println("队列已经满了，不能在继续添加");
                return;
            }
            arr[++rear] = data;
        }

        public int get() {
            if (isEmpty()) {
                System.out.println("队列为空，不能获取元素");
                return -1;
            }
            return arr[++front];
        }

        // 显示队列的所有数据
        public void show() {
            if (isEmpty()) {
                System.out.println("队列空的，没有数据~~");
                return;
            }
            System.out.println("开始遍历队列：");
            for (int i = front + 1; i <= rear; i++) {
                System.out.printf("arr[%d]=%d\n", i, arr[i]);
            }
        }


        // 显示队列的头数据， 注意不是取出数据
        public int peek() {
            if (isEmpty()) {
                throw new RuntimeException("队列空的，没有数据~~");
            }
            return arr[front + 1];
        }

    }

数组模拟环形队列

    public  class CircleArrayQueue{

        // 队列容量
        private int capacity;

        // 保存队列中的数据
        private int[] arr;

        // 头部指针
        private int front;

        // 尾部指针
        private int rear;

        public CircleArrayQueue(int capacity) {
            this.capacity = capacity;
            arr = new int[capacity];
        }

        public boolean isEmpty() {
            return front == rear;
        }

        public boolean isFull() {
            // 此处+1 是因为存储元素从0算起
            return (rear + 1) % capacity  == front;
        }

        public void add(int data) {
            if (isFull()) {
                System.out.println("队列已经满了，不能在继续添加");
                return;
            }
            arr[rear] = data;
            rear = (rear + 1) % capacity;
        }

        public int get() {
            if (isEmpty()) {
                System.out.println("队列为空，不能获取元素");
                return -1;
            }
            int value = arr[front];
            front = (front + 1) % capacity;
            return value;
        }

        // 显示队列的所有数据
        public void show() {
            if (isEmpty()) {
                System.out.println("队列空的，没有数据~~");
                return;
            }
            System.out.println("开始遍历队列：");
            for (int i = front % capacity; i < front + ((rear + capacity - front) % capacity); i++) {
                System.out.printf("arr[%d]=%d\n", i, arr[i]);
            }
        }

        // 显示队列的头数据， 注意不是取出数据
        public int peek() {
            if (isEmpty()) {
                throw new RuntimeException("队列空的，没有数据~~");
            }
            return arr[front];
        }

    }

链表

链表属于线性结构，存储空间不连续。

链表特点：

• 链表是以节点的方式来存储，是链式存储；data 域存放数据，next 域指向下一个节点；
• 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定；

单向链表

操作单向链表：对于插入、删除操作，只能定位至待操作节点的前一个节点，如果定位至当前节点，那么其上一个节点的信息便会丢失。

单向链表，链表的增、删、查、改

class SingleLinkedList{

    // 头结点
    private Node headNode = new Node(0,"");

    // 添加方法
    public  void add(Node node){
        Node tmpNode = headNode;

        while (tmpNode.next != null){
            // 指向下一个结点
            tmpNode = tmpNode.next;
        }
        // 退出循环意味着tmpNode.next == null 即找到最后一个结点了
        tmpNode.next = node;
    }

    // 顺序添加
    public void addByOrder(Node node){
        boolean flag = false;
        Node tmp = headNode;
        while (true){
            if (tmp.next == null) {
                break;
            }

            // 将新插入的结点num跟链表中已经存在的num进行比较，如果 < 链表中的结点 则说明找到了该位置
            if (node.num < tmp.next.num){
                break;
            }
            // 如果num相同则不能添加
            if (node.num == tmp.next.num){
                flag = true;
                break;
            }
            tmp = tmp.next;
        }

        if (!flag){
            node.next = tmp.next;
            tmp.next = node;
            return;
        }
        System.out.printf("需要添加的结点编号：%d已经存在了",node.num);
    }

    // 遍历链表
    public void list() {
        // 遍历除了头结点外的所有结点
        Node tmpNode = headNode.next;
        if (tmpNode == null){
            System.out.println("链表为空！");
            return;
        }

        while (tmpNode != null){
            System.out.println(tmpNode);
            // 指向下一个结点
            tmpNode = tmpNode.next;
        }
    }


}


class Node {

    int num;
    String name;
    Node next;

    public Node(int num,String name){
        this.num = num;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ", name='" + name + '\'' +
                '}';
    }
}

反转单向链表

class LinkedListDemo{
    // 反转链表
    public void reserve(Node head) {
      if (head.next == null || head.next.next == null) {
        return;
      }

      Node reserve = new Node(0, "");
      Node cur = head.next;
      Node next = null;
      // 遍历链表
      // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
      while (cur != null) {

        // 保存当前结点的下一个结点
        next = cur.next;

        // 将cur的下一个节点指向新的链表的最前端（覆盖掉）保证将最新的结点放到reseve的最前面
        cur.next = reserve.next;

        // 将cur 连接到新的链表上
        reserve.next = cur;

        // 将之前保存好的结点赋值给当前结点
        cur = next;
      }
    }
}

利用栈逆序打印单向链表

class LinkedListDemo {
  public void reservePrint(Node head) {
    if (head.next == null || head.next.next == null) {
      return;
    }

    Stack<Node> nodes = new Stack<>();
    Node tmp = head.next;
    while (tmp != null) {
      nodes.push(tmp);
      tmp = tmp.next;
    }

    // 从stack中取出结点
    while (nodes.size() > 0) {
      System.out.println(nodes.pop());
    }
  }
}

双向链表

对比单向链表：

• 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找；
• 单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除；

双向链表，增、删、改、查

class DoubleLinkedList{

    // 头结点
    private Node headNode = new Node(0,"");


    public Node getHeadNode() {
        return headNode;
    }


    // 添加方法
    public  void add(Node node){
        Node tmpNode = headNode;

        while (tmpNode.next != null){
            // 指向下一个结点
            tmpNode = tmpNode.next;
        }
        // 退出循环意味着tmpNode.next == null 即找到最后一个结点了
        tmpNode.next = node;
        node.prev = tmpNode;
    }


    // 双向链表修改
    public void update(Node node){
        if (headNode == null) {
            return;
        }

        Node tmp = headNode.next;
        while (true){
            if (tmp == null){
                break;
            }
            if (node.num == tmp.num){
                tmp.name = node.name;
                break;
            }
            tmp = tmp.next;
        }
    }

    // 双向链表删除
    public void remove(int num){
        if (headNode.next == null){
            System.out.println("链表为空，无法删除！");
            return;
        }
        Node tmp = headNode.next;
        while (tmp != null){
            if (num == tmp.num){
                tmp.prev.next = tmp.next;

                // 最后一个结点的next 为null null.pre会出现空指针异常
                if(tmp.next != null) {
                    tmp.next.prev = tmp.prev;
                }
                break;
            }
            tmp = tmp.next;
        }
    }

    // 遍历链表
    public void list() {
        // 遍历除了头结点外的所有结点
        Node tmpNode = headNode.next;
        if (tmpNode == null){
            System.out.println("链表为空！");
            return;
        }

        while (tmpNode != null){
            System.out.println(tmpNode);
            // 指向下一个结点
            tmpNode = tmpNode.next;
        }
    }


}


class Node {

    int num;
    String name;
    Node next;
    Node prev;

    public Node(int num,String name){
        this.num = num;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ", name='" + name + '\'' +
                '}';
    }
}

约瑟夫问题

约瑟夫问题为：设编号为 1，2，…n的n个人围坐一圈，约定编号为 k（1<=k<=n） 的人从 1 开始报数,数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列， 依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

用一个不带头结点的循环链表来处理约瑟夫问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

class JoesphSingletonLinkedList {

    private Node first = null;


    // 向单向链表添加数据
    public void add(int nums) {
        if (nums < 1) {
            System.out.println("nums的值不正确");
            return;
        }
        Node cur = null;
        for (int i = 1; i <= nums; i++) {
            Node node = new Node(i);
            if (i == 1) {
                first = node;
                first.next = first;
                cur = first;
            } else {
                cur.next = node;
                node.next = first;
                cur = node;
            }
        }
    }


    // 遍历单向循环链表
    public void list() {
        Node tmp = first;
        while (true){
            System.out.printf("当前结点为：%d\n",tmp.num);
            if (tmp.next == first){
                break;
            }
            tmp = tmp.next;
        }
    }


    // 约瑟夫问题
    public void joseph(int startNum,int countNum,int sum){
        if (startNum > sum || startNum < 0 || countNum < 0) {
            System.out.println("输入的参数不正确！");
            return;
        }
        // 创建辅助指针，将该指针指向 first 的前一个
        Node helper = first;
        while (helper.next != first) {
            helper = helper.next;
        }

        // 将first 和 help指针循环 （startNum - 1）次；因为从startNum开始，需要减一
        for (int i = 0; i < startNum - 1; i++) {
            first = first.next;
            helper = helper.next;
        }

        while (true){
            // 当环形链表中只存在一个结点
            if (first == helper){
                break;
            }

            // 因为是环形链表，所以需要循环挨个出链表
            for (int i = 0; i < countNum - 1; i++) {
                first = first.next;
                helper = helper.next;
            }

            // 当前 first 就是出圈的结点
            System.out.printf("当前出队列的结点编号为：%d\n",first.num);
            first = first.next;
            helper.next = first;
        }
        System.out.printf("最后的结点为：%d\n",first.num);
    }

}


class Node {

    int num;
    Node next;

    public Node(int num){
        this.num = num;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                '}';
    }
}

栈

栈的英文为stack，是一个先入后出(FILO-First In Last Out)的有序列表，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。

下图是出栈和入栈

栈的应用场景：

• 子程序的调用： 在跳往子程序前， 会先将下个指令的地址存到堆栈中， 直到子程序执行完后再将地址取出， 以回到原来的程序中；
• 处理递归调用： 和子程序的调用类似， 只是除了储存下一个指令的地址外， 也将参数、 区域变量等数据存入栈中；
• 表达式的转换：中缀表达式转后缀表达式与求值；
• 二叉树的遍历；
• 图形的深度优先(depth 一 first)搜索法；

数组模拟栈

class ArrayStack<T>{

    private int size;
    private int top;
    private Object[] stack;

    public ArrayStack(int size) {
        this.size = size;
        this.stack = new String[size];
        top = -1;
    }

    public boolean isFull(){
        return top == size -1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    // 入栈
    public void push(T item) {
        if (isFull()) {
            System.out.println("栈已经满了，不能继续添加！");
            return;
        }
        top++;
        this.stack[top] = item;
    }

    // 出栈操作
    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈已经为空，不能继续pop");
        }
        T val = (T)this.stack[top];
        top--;
        return val;
    }

    // 遍历栈
    public void list() {
        if (isEmpty()) {
            System.out.println("栈为空不能继续遍历！");
            return;
        }

        System.out.println("遍历栈==》");
        for (int i = top; i >=0; i--){
            System.out.println(this.stack[i]);
        }
    }

}

栈实现中缀表达式

class CalcInfixExpressions {


    public int calcInfixExpressions(String expression) {
        // 定义变量
        char[] chars = expression.toCharArray();
        int len = chars.length;
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> oprStack = new Stack<>();
        int index = 0;

        for (int j = 0; j < len; j++) {

            char ch = chars[j];

            index++;

            // 判断字符是否为数字,如果是数字就放入数栈中
            if (Character.isDigit(ch)) {

                // 接收多位数
                int num = ch;
                boolean flag = false;

                // 从当前字符开始遍历，如果下一位字符不是数字，则将该数字压入栈中并退出循环，如果是数字，则需要拼接起来
                for (int i = index; i < len; i++) {
                    if (Character.isDigit(expression.charAt(i))) {
                        String strNum = String.valueOf(ch) + expression.charAt(i);
                        num = Integer.parseInt(strNum);
                        flag = true;
                        index++;
                        j++;
                    }else {
                        break;
                    }
                }
                if (!flag) {
                    num -= 48;
                }
                numStack.push(num);
                continue;
            }

            // 非数字，即运算符,如果为空直接加入栈中
            if (oprStack.isEmpty()) {
                oprStack.push(ch);
                continue;
            }

            // 如果运算符栈不为空，需要比较运算符的优先级，如果当前运算符的优先级 <= 栈顶的运算符的优先级，需要计算在压入栈中
            if (oprPriority(oprStack.peek()) >= oprPriority(ch)) {
                numStack.push(calc(numStack.pop(), numStack.pop(), oprStack.pop()));
            }

            // 将字符压入操作符栈中
            oprStack.push(ch);
        }


        // 将处理好的数据按照顺序弹出，进行计算，得到数栈中最后一个数就是最终的结果
        while (!oprStack.isEmpty()){
            numStack.push(calc(numStack.pop(), numStack.pop(), oprStack.pop()));
        }

        return numStack.pop();
    }


    // 获取字符的优先级
    private int oprPriority(int ch) {
        if (ch == '*' || ch == '/') {
            return 2;
        }
        if (ch == '+' || ch == '-') {
            return 1;
        }
        return -1;
    }


    // 计算
    private int calc(int num1, int num2, int opr) {
        int res = 0;
        switch (opr) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
        }
        return res;
    }

}

栈实现后缀表达式

后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后。例如： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

思路：从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。

class PolandNotation{

    // 计算后缀表达式
    public int calcSuffixExceptions(String suffixExpres) {
        char[] chars = suffixExpres.toCharArray();
        Stack<Integer> stack = new Stack<>();
        int res =0;

        for (int i = 0; i < chars.length; i++) {
            char ch = suffixExpres.charAt(i);
            if (!Character.isDigit(ch)) {
                res = calc(stack.pop(),stack.pop(),ch);
                stack.push(res);
            }else {
                stack.push(ch - 48);
            }
        }
        return res;
    }

    // 计算
    private int calc(int num1, int num2, int opr) {
        int res = 0;
        switch (opr) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                throw new RuntimeException("运算符有误");
        }
        return res;
    }

}

中缀表达式转后缀表达式

中缀表达式转后缀表达式代码实现

class InfixToPolandNotation{

    // 根据ASCII 判断是否为数字
    private boolean isNumber(char ch){
        return ch >=48 && ch <= 57;
    }

    // 获取字符的优先级
    private int oprPriority(String opr) {
        if (opr.equals("*") || opr.equals("/")) {
            return 2;
        }
        if (opr.equals("+") || opr.equals("-")) {
            return 2;
        }
        return -1;
    }

    // 将中缀表达式字符串转成中缀表达式集合
    public List<String> toInfixExceptionList(String str) {
        ArrayList<String> list = new ArrayList<>();
        int index = 0;
        StringBuilder number;
        char c;

        while (index < str.length()){
            if (!isNumber((c = str.charAt(index)))){
                list.add(String.valueOf(c));
                index++;
            }else {
                number = new StringBuilder();
                while (index < str.length() && isNumber((c = str.charAt(index)))){
                    index++;
                    number.append(c);
                }
                list.add(number.toString());
            }
        }
        return list;
    }


    // 将中缀表达式转为后缀表达式
    public List<String> infixExpressionToSuffixExpress(List<String> list) {
        Stack<String> stack = new Stack<>();
        ArrayList<String> finalList = new ArrayList<>();

        for (String item : list) {
            // 如果是数字或者为（ 将该值压入栈中
            if (item.matches("\\d+")){
                finalList.add(item);
                continue;
            }

            if (item.equals("(")){
                stack.push(item);
                continue;
            }

            // 如果是 ）则将 ()中间的数重新压入list中，最后将 ） 移除掉
            if (item.equals(")")){
                while (!stack.peek().equals("(")) {
                    finalList.add(stack.pop());
                }
                stack.pop();
            }else {
                // 如果不是 ）则判断运算符的优先级，如果符号栈栈顶的优先级 >= 当前的优先级，则将该运算符加入数字栈中
                while (stack.size() > 0 && oprPriority(stack.peek()) >= oprPriority(item)){
                    finalList.add(stack.pop());
                }
                stack.push(item);
            }
        }

        // 将operStack中剩余的运算符依次弹出并加入tempList
        while (stack.size() != 0) {
            finalList.add(stack.pop());
        }
        return finalList;
    }

}

完整逆波兰表达式代码，支持小数、支持消除空格

public class ReversePolishMultiCalc {

	 /**
     * 匹配 + - * / ( ) 运算符
     */
    static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";

    static final String LEFT = "(";
    static final String RIGHT = ")";
    static final String ADD = "+";
    static final String MINUS= "-";
    static final String TIMES = "*";
    static final String DIVISION = "/";

    /**
     * 加減 + -
     */
    static final int LEVEL_01 = 1;
    /**
     * 乘除 * /
     */
    static final int LEVEL_02 = 2;

    /**
     * 括号
     */
    static final int LEVEL_HIGH = Integer.MAX_VALUE;


    static Stack<String> stack = new Stack<>();
    static List<String> data = Collections.synchronizedList(new ArrayList<String>());

    /**
     * 去除所有空白符
     * @param s
     * @return
     */
    public static String replaceAllBlank(String s ){
        // \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
        return s.replaceAll("\\s+","");
    }

    /**
     * 判断是不是数字 int double long float
     * @param s
     * @return
     */
    public static boolean isNumber(String s){
        Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");
        return pattern.matcher(s).matches();
    }

    /**
     * 判断是不是运算符
     * @param s
     * @return
     */
    public static boolean isSymbol(String s){
        return s.matches(SYMBOL);
    }

    /**
     * 匹配运算等级
     * @param s
     * @return
     */
    public static int calcLevel(String s){
        if("+".equals(s) || "-".equals(s)){
            return LEVEL_01;
        } else if("*".equals(s) || "/".equals(s)){
            return LEVEL_02;
        }
        return LEVEL_HIGH;
    }

    /**
     * 匹配
     * @param s
     */
    public static List<String> doMatch (String s) throws Exception{
        if(s == null || "".equals(s.trim())) throw new RuntimeException("data is empty");
        if(!isNumber(s.charAt(0)+"")) throw new RuntimeException("data illeagle,start not with a number");

        s = replaceAllBlank(s);

        String each;
        int start = 0;

        for (int i = 0; i < s.length(); i++) {
            if(isSymbol(s.charAt(i)+"")){
                each = s.charAt(i)+"";
                //栈为空，(操作符，或者 操作符优先级大于栈顶优先级 && 操作符优先级不是( )的优先级 及是 ) 不能直接入栈
                if(stack.isEmpty() || LEFT.equals(each)
                        || ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)){
                    stack.push(each);
                }else if( !stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())){
                    //栈非空，操作符优先级小于等于栈顶优先级时出栈入列，直到栈为空，或者遇到了(，最后操作符入栈
                    while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek()) ){
                        if(calcLevel(stack.peek()) == LEVEL_HIGH){
                            break;
                        }
                        data.add(stack.pop());
                    }
                    stack.push(each);
                }else if(RIGHT.equals(each)){
                    // ) 操作符，依次出栈入列直到空栈或者遇到了第一个)操作符，此时)出栈
                    while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())){
                        if(LEVEL_HIGH == calcLevel(stack.peek())){
                            stack.pop();
                            break;
                        }
                        data.add(stack.pop());
                    }
                }
                start = i ;    //前一个运算符的位置
            }else if( i == s.length()-1 || isSymbol(s.charAt(i+1)+"") ){
                each = start == 0 ? s.substring(start,i+1) : s.substring(start+1,i+1);
                if(isNumber(each)) {
                    data.add(each);
                    continue;
                }
                throw new RuntimeException("data not match number");
            }
        }
        //如果栈里还有元素，此时元素需要依次出栈入列，可以想象栈里剩下栈顶为/，栈底为+，应该依次出栈入列，可以直接翻转整个stack 添加到队列
        Collections.reverse(stack);
        data.addAll(new ArrayList<>(stack));

        System.out.println(data);
        return data;
    }

    /**
     * 算出结果
     * @param list
     * @return
     */
    public static Double doCalc(List<String> list){
        Double d = 0d;
        if(list == null || list.isEmpty()){
            return null;
        }
        if (list.size() == 1){
            System.out.println(list);
            d = Double.valueOf(list.get(0));
            return d;
        }
        ArrayList<String> list1 = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            list1.add(list.get(i));
            if(isSymbol(list.get(i))){
                Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
                list1.remove(i);
                list1.remove(i-1);
                list1.set(i-2,d1+"");
                list1.addAll(list.subList(i+1,list.size()));
                break;
            }
        }
        doCalc(list1);
        return d;
    }

    /**
     * 运算
     * @param s1
     * @param s2
     * @param symbol
     * @return
     */
    public static Double doTheMath(String s1,String s2,String symbol){
        Double result ;
        switch (symbol){
            case ADD : result = Double.valueOf(s1) + Double.valueOf(s2); break;
            case MINUS : result = Double.valueOf(s1) - Double.valueOf(s2); break;
            case TIMES : result = Double.valueOf(s1) * Double.valueOf(s2); break;
            case DIVISION : result = Double.valueOf(s1) / Double.valueOf(s2); break;
            default : result = null;
        }
        return result;

    }

    public static void main(String[] args) {
        //String math = "9+(3-1)*3+10/2";
        String math = "12.8 + (2 - 3.55)*4+10/5.0";
        try {
            doCalc(doMatch(math));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

哈希表

哈希表也叫散列表，是根据关键码值(Key value)而直接进行访问的数据结构。

它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

手写模拟哈希表

public class HashTableDemo {

    public static void main(String[] args) {
        HashTab hashTab = new HashTab(3);
        Node node1 = new Node(1, "zs");
        Node node2 = new Node(2, "lx");
        Node node3 = new Node(3, "ex");
        Node node4 = new Node(4, "as");
        Node node5 = new Node(7, "we");

        hashTab.put(node1);
        hashTab.put(node2);
        hashTab.put(node3);
        hashTab.put(node4);
        hashTab.put(node5);

        System.out.println("添加元素后===》");
        System.out.println(hashTab.toString());

        System.out.println("删除后===》");
        hashTab.remove(4);
        System.out.println(hashTab.toString());
    }
}

class HashTab {

    private NodeList[] nodes;
    private int size;

    public HashTab(int size) {
        this.size = size;
        nodes = new NodeList[size];
        for (int i = 0; i < size; i++) {
            nodes[i] = new NodeList();
        }
    }

    public void put(Node node) {
        // 放入hash表的位置
        nodes[getPosition(node.id)].add(node);
    }

    public void remove(int id) {
        nodes[getPosition(id)].delete(id);
    }


    private int getPosition(int id) {
        return id % size;
    }

    @Override
    public String toString() {
        return "HashTab{" +
                "nodes=\n" + Arrays.toString(nodes) +
                "}";
    }
}

class NodeList {
    // 头结点
    Node head = null;

    // 添加结点方法
    public void add(Node node) {
        if (head == null) {
            head = node;
            return;
        }

        // 头结点不要动，将添加的结点放到链表的最后一个位置
        Node tmp = head;
        // 当下一个结点等于null时，找到最后一个结点
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = node;
    }


    // 展示当前链表
    public void list() {
        if (head == null) {
            System.out.println("当前链表为空");
            return;
        }
        // 辅助结点
        Node tmp = head;
        while (true) {
            System.out.println(tmp);
            if (tmp.next == null) {
                break;
            }
            tmp = tmp.next;
        }
    }

    // 根据ID删除链表中的某个结点
    public void delete(int id) {
        if (head == null) {
            System.out.println("当前链表为空");
            return;
        }
        // 判断删除的是否是头结点
        if (head.id == id) {
            head = head.next;
            return;
        }

        Node preNode = head;
        Node curNode = preNode.next;
        while (curNode != null) {
            if (curNode.id == id) {
                preNode.next = curNode.next;
                System.out.println("删除成功，删除的是: " + curNode.id + "," + curNode.name);
                curNode = null;
                return;
            }
            preNode = preNode.next;
            curNode = curNode.next;
        }
        System.out.println("删除失败，节点不存在");
    }


    @Override
    public String toString() {
        return "NodeList{" +
                "head=" + head +
                "}\n";
    }
}

class Node {
    int id;
    String name;
    Node next;

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", next=" + next +
                "}";
    }
}

二叉树

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

如果该二叉树的所有叶子节点都在最后一层，并且结点总数为 2^n -1， n 为层数，则称为满二叉树。

如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

PS: 二叉树中结点等价于节点

二叉树的遍历及查找

对于二叉树来讲最主要、最基本的运算是遍历。遍历二叉树 是指以一定的次序访问二叉树中的每个结点。所谓访问结点是指对结点进行各种操作的简称。

例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或是执行对结点的其他操作。遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。

二叉树的遍历方法：

• 前序遍历：先访问根结点，然后前序遍历左子树，在前序遍历右子树；
• 中序遍历：中序遍历根结点的左子树，然后访问根结点，最后遍历右子树；
• 后序遍历：后序遍历左子树，然后后序遍历右子树，最后访问根结点；

public class BinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTreeObj root = new BinaryTreeObj(1,"zs");
        BinaryTreeObj binaryTreeObj2 = new BinaryTreeObj(2,"ls");
        BinaryTreeObj binaryTreeObj3 = new BinaryTreeObj(3,"ww");
        BinaryTreeObj binaryTreeObj4 = new BinaryTreeObj(4,"zq");
        BinaryTreeObj binaryTreeObj5 = new BinaryTreeObj(5,"111");

        root.setLeft(binaryTreeObj2);
        root.setRight(binaryTreeObj3);
        binaryTreeObj3.setLeft(binaryTreeObj4);
        binaryTreeObj3.setRight(binaryTreeObj5);

        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setRoot(root);
        binaryTree.preOrderShow();

        BinaryTreeObj binaryTreeObj = binaryTree.preOrderSearch(11);
        if (binaryTreeObj == null) {
            System.out.println("没有找到该结点～");
            return;
        }
        System.out.printf("找到当前结点：id: %d, name: %s",binaryTreeObj.getId(),binaryTreeObj.getName());
    }
}


class BinaryTree {

    private BinaryTreeObj root;

    public void setRoot(BinaryTreeObj root) {
        this.root = root;
    }

    public void preOrderShow() {
        if (this.root != null) {
            this.root.preOrder();
        }
    }


    public void postOrderShow() {
        if (this.root != null) {
            this.root.postOrder();
        }
    }


    public void midOrderShow() {
        if (this.root != null) {
            this.root.midOrder();
        }
    }

    public BinaryTreeObj preOrderSearch(int id){
        if (this.root != null) {
            return this.root.preOrderSearch(id);
        }
        return null;
    }

    public BinaryTreeObj infixOrderSearch(int id){
        if (this.root != null) {
            return this.root.infixOrderSearch(id);
        }
        return null;
    }

    public BinaryTreeObj postOrderSearch(int id){
        if (this.root != null) {
            return this.root.postOrderSearch(id);
        }
        return null;
    }

}


class BinaryTreeObj {

    private Integer id;
    private String name;

    public BinaryTreeObj(Integer id,String name){
        this.id = id;
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public Integer getId() {
        return id;
    }

    private BinaryTreeObj left;
    private BinaryTreeObj right;

    public void setLeft(BinaryTreeObj left) {
        this.left = left;
    }

    public void setRight(BinaryTreeObj right) {
        this.right = right;
    }

    // 前序遍历：根结点 =》 左结点 =》 右结点
    public void preOrder(){
        System.out.println(this);
        if (this.left != null){
            this.left.preOrder();
        }

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

    // 后序遍历： 左结点 =》 右结点 =》 根结点
    public void postOrder(){

        if (this.left != null){
            this.left.postOrder();
        }

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

    // 中序遍历： 左结点 =》 根结点 =》 右结点
    public void midOrder(){

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

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

    // 前序查找
    public BinaryTreeObj preOrderSearch(int id) {
        if (id == this.id){
            return this;
        }

        BinaryTreeObj binaryTreeObj = null;
        if (this.left != null){
            binaryTreeObj = this.left.preOrderSearch(id);
        }

        if (binaryTreeObj != null){
            return binaryTreeObj;
        }

        if (this.right != null){
            binaryTreeObj = this.right.preOrderSearch(id);
        }
        return binaryTreeObj;
    }

    // 中序查找
    public BinaryTreeObj infixOrderSearch(int id) {

        BinaryTreeObj binaryTreeObj = null;
        if (this.left != null){
            binaryTreeObj = this.left.infixOrderSearch(id);
        }

        if (id == this.id){
            return this;
        }

        if (binaryTreeObj != null){
            return binaryTreeObj;
        }

        if (this.right != null){
            binaryTreeObj = this.right.infixOrderSearch(id);
        }
        return binaryTreeObj;
    }

    // 后序查找
    public BinaryTreeObj postOrderSearch(int id) {

        BinaryTreeObj binaryTreeObj = null;
        if (this.left != null){
            binaryTreeObj = this.left.postOrderSearch(id);
        }

        if (binaryTreeObj != null){
            return binaryTreeObj;
        }

        if (this.right != null){
            binaryTreeObj = this.right.postOrderSearch(id);
        }
        if (id == this.id){
            return this;
        }
        return binaryTreeObj;
    }

    @Override
    public String toString() {
        return "BinaryTreeObj{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

二叉树的删除

class BinaryTree {
    public void del(int id){
        if (this.root == null){
            return;
        }
        if (this.root.getId() == id){
            this.root = null;
            return;
        }
        this.root.delNo(id);
    }
}

class BinaryTreeObj {
    // 根据ID删除结点
    public void delNo(int id){
        // 找到当前结点的左子树结点是否为指定结点，如果是则将其置空
        if (this.left != null && this.left.id == id){
            this.left = null;
            return;
        }

        // 与上面同理删除右子树结点
        if (this.right != null && this.right.id == id){
            this.right = null;
            return;
        }


        if (this.left == null && this.right == null){
            return;
        }

        // 如果当前左结点或右结点 不是要删除的结点 则进行递归删除
        if (this.left != null){
            this.left.delNo(id);
        }

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

顺序存储二叉树

二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。

需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。

顺序存储二叉树应用实例：八大排序算法中的堆排序，就会使用到顺序存储二叉树。

public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree();
        arrBinaryTree.setArrayTree(arr);
        arrBinaryTree.preArrBinaryTree(0);
    }
}

class ArrBinaryTree {

    private int[] arr = null;

    public void setArrayTree(int[] arr) {
        this.arr = arr;
    }

    public void preArrBinaryTree(int index) {
        if (arr == null || arr.length == 0) {
            return;
        }
        System.out.println(arr[index]);

        int nextLeftIndex = (index << 1) + 1;
        int nextRightIndex = (index << 1) + 2;

        if (nextLeftIndex < arr.length) {
            preArrBinaryTree(nextLeftIndex);
        }

        if (nextRightIndex < arr.length) {
            preArrBinaryTree(nextRightIndex);
        }
    }

}

线索化二叉树

n 个结点的二叉链表中含有 n+1【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在 某种遍历次序 下的前驱和后继结点的指针，这种附加的指针称为"线索"。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。

根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

如图，按照前序遍历可以得到数组 {1, 2, 4, 5, 3, 6} 其中

• 【2】的前驱结点为【1】，后继结点为【4】
• 【6】的前驱结点为【3】，后继结点为 null

中序线索化二叉树示意图

public class ThreadedBinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTreeObj root = new BinaryTreeObj(1,"zs");
        BinaryTreeObj binaryTreeObj2 = new BinaryTreeObj(2,"ls");
        BinaryTreeObj binaryTreeObj3 = new BinaryTreeObj(3,"ww");
        BinaryTreeObj binaryTreeObj4 = new BinaryTreeObj(4,"zq");
        BinaryTreeObj binaryTreeObj5 = new BinaryTreeObj(5,"111");

        root.setLeft(binaryTreeObj2);
        root.setRight(binaryTreeObj3);
        binaryTreeObj3.setLeft(binaryTreeObj4);
        binaryTreeObj3.setRight(binaryTreeObj5);

        // 中序线索化二叉树
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.infixThreadedBinaryTree(root);

        // 遍历中序线索化二叉树
        threadedBinaryTree.forEachInfixThreadedBinaryTree(root); // 2,1,4,3,5
    }
}


class ThreadedBinaryTree{

    private BinaryTreeObj pre;

    // 中序线索化二叉树
    public void infixThreadedBinaryTree(BinaryTreeObj node){
        if (node == null){
            return;
        }
        // 左递归线索化二叉树
        infixThreadedBinaryTree(node.getLeft());

        // 线索化核心代码 将左结点线索化
        if (node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        // 将右结点线索化
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        // 使辅助结点指针指向当前结点
        pre = node;

        // 右递归线索化二叉树
        infixThreadedBinaryTree(node.getRight());
    }

    // 遍历中序线索二叉树
    public void forEachInfixThreadedBinaryTree(BinaryTreeObj root) {
        // 用辅助结点保存根结点
        BinaryTreeObj node = root;

        while (node != null){

            // 向左子树遍历,直到找到 leftType=1 的结点，等于1代表该结点为前驱结点
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            System.out.println(node);

            // 向右子树遍历，直到找到 rightType=0 的结点， 等于0代表该结点为右子树
            while (node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }

            // node 结点向右边找
            node = node.getRight();
        }
    }
}

class BinaryTreeObj {

    private Integer id;
    private String name;

    private BinaryTreeObj left;
    private BinaryTreeObj right;

    // 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
    // 如果rightType == 0 表示指向是右子树, 如果 1 表示指向后继结点
    private int leftType;
    private int rightType;

    public BinaryTreeObj(Integer id,String name){
        this.id = id;
        this.name = name;
    }
    public String getName() {
        return name;
    }
    public Integer getId() {
        return id;
    }
    public BinaryTreeObj getLeft() {
        return left;
    }
    public BinaryTreeObj getRight() {
        return right;
    }
    public void setLeft(BinaryTreeObj left) {
        this.left = left;
    }
    public void setRight(BinaryTreeObj right) {
        this.right = right;
    }
    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }
    public void setRightType(int rightType) {
        this.rightType = rightType;
    }
    public int getLeftType() {
        return leftType;
    }
    public int getRightType() {
        return rightType;
    }
}

哈夫曼树

哈夫曼树重要概念：

• 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L-1；
• 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积；
• 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weighted path length) ，权值越大的结点离根结点越近的二叉树才是最优二叉树。WPL 最小的就是赫夫曼树；

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，称为哈夫曼树，有些资料也译为赫夫曼树。

WPL最小的就是哈夫曼树，如上图，中间的树就是哈夫曼树。

public class HuffmanTreeDemo {
    public static void main(String[] args) {
        HuffmanTree huffmanTree = new HuffmanTree();
        HuffmanTreeNode root = huffmanTree.buildHuffmanTree(new int[]{13, 7, 8, 3, 29, 6, 1});
        System.out.println("前序遍历huffman树：");
        huffmanTree.preOrder(root);
    }
}

class HuffmanTree{

    public void preOrder(HuffmanTreeNode root){
        if (root != null){
            root.preOrder();
        }
    }

    public HuffmanTreeNode buildHuffmanTree(int[] arr){

        List<HuffmanTreeNode> list = new ArrayList<>();
        for (int value : arr) {
            list.add(new HuffmanTreeNode(value));
        }

        // 如果集合中的元素大于1则继续循环
        while (list.size() > 1){
            // 从大到小进行排序
            Collections.sort(list);

            // 获取集合中两个较小的元素进行构建 huffman 树
            HuffmanTreeNode leftNode = list.get(0);
            HuffmanTreeNode rightNode = list.get(1);
            HuffmanTreeNode parentNode = new HuffmanTreeNode(leftNode.value + rightNode.value);
            parentNode.left = leftNode;
            parentNode.right = rightNode;

            // 构建后将 leftNode， rightNode 移除集合；将parentNode加入集合；然后重新排序
            list.remove(leftNode);
            list.remove(rightNode);
            list.add(parentNode);
        }
        return list.get(0);
    }

}


class HuffmanTreeNode implements Comparable<HuffmanTreeNode>{
    int value;
    HuffmanTreeNode left;
    HuffmanTreeNode right;

    public HuffmanTreeNode(int value){
        this.value = value;
    }

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

    @Override
    public int compareTo(HuffmanTreeNode o) {
        // 从小到大排序
        return this.value - o.value;
    }

    @Override
    public String toString() {
        return "HuffmanTreeNode{" +
                "value=" + value +
                '}';
    }
}

二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。如果有相同的值，可以将该节点放在左子节点或右子节点，二叉排序树的中序遍历为有序数列。

class BinarySortTree {

    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    // 添加结点
    public void add(Node node) {
        if (this.root == null) {
            this.root = node;
        } else {
            this.root.add(node);
        }
    }

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

    // 查找结点
    public Node search(int target) {
        if (this.root == null) {
            return null;
        }
        return this.root.search(target);
    }

    // 查找当前结点的父结点
    public Node searchParentNode(int target) {
        if (this.root == null) {
            return null;
        }
        return this.root.searchParentNode(target);
    }

    // 删除结点
    public void delNode(int target) {
        if (this.root == null) {
            return;
        }
        // 如果删除的结点是根结点
        if (this.root.left == null && this.root.right == null) {
            this.root = null;
            return;
        }
        Node targetNode = search(target);
        if (targetNode == null) {
            return;
        }
        // 获取当前结点的父结点
        Node parentNode = searchParentNode(target);
        // 删除的结点是叶子结点
        if (targetNode.left == null && targetNode.right == null) {
            // 判断是左结点还是右结点
            if (parentNode.left != null && parentNode.left.val == target) {
                parentNode.left = null;
            } else {
                parentNode.right = null;
            }
            return;
        }

        // 删除的结点有两个结点
        if (targetNode.left != null && targetNode.right != null) {
            // 从右子树找到最小的值并删除，将该值赋值给targetNode
            targetNode.val = delRightTreeMin(targetNode.right);
            return;
        }

        // 删除只有一颗子树的结点
        if (targetNode.left != null) {
            if(parentNode == null){
                root = targetNode.left;
                return;
            }
            // 当前结点存在左子树
            if (parentNode.left.val == target) {
                parentNode.left = targetNode.left;
            } else {
                parentNode.right = targetNode.left;
            }
        }
        if (targetNode.right != null) {
            if(parentNode == null){
                root = targetNode.right;
                return;
            }
            // 当前结点存在右子树
            if (parentNode.right.val == target) {
                parentNode.left = targetNode.right;
            } else {
                parentNode.right = targetNode.right;
            }
        }
    }

    private int delRightTreeMin(Node node) {
        Node target = node;
        // 循环的查找左子节点，就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        // 此时 target就指向了最小结点 删除最小结点（该节点肯定是左叶子节点）
        delNode(target.val);
        return target.val;
    }

}

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

    public Node(int val) {
        this.val = val;
    }

    // 查找结点
    public Node search(int target) {
        if (this.val == target) {
            return this;
        } else if (this.val > target) {
            if (this.left == null) {
                return null;
            }
            return this.left.search(target);
        } else {
            if (this.right == null) {
                return null;
            }
            return this.right.search(target);
        }
    }

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

    // 添加结点
    public void add(Node node) {
        if (node == null) {
            return;
        }
        // 如果当前待插入结点的值小于当前结点，将其插入在左子树中
        if (node.val < this.val) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            // 将当前结点插入右子树
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
}

平衡二叉树

二叉搜索树一定程度上可以提高搜索效率，但是当序列构造二叉搜索树，可能会将二叉树退化成单链表，从而降低搜索效率。

平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树，可以保证查询效率较高。

平衡二叉树的特点：

• 平衡二叉树一定是二叉排序；
• 是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树；

将有序二叉树变为平衡二叉树代码

public class AVLTreeDemo {
    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        int[] arr = {10, 11, 7, 6, 8, 9 };
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node(arr[i]);
            avlTree.add(node);
        }
        System.out.println("当前树高度："+ avlTree.height());
        System.out.println("当前根结点：" + avlTree.getRoot());
        System.out.println("当前左子树高度："+ avlTree.getRoot().leftHeight());
        System.out.println("当前右子树高度："+ avlTree.getRoot().rightHeight());
    }
}

class AVLTree{
    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    public Node getRoot() {
        return root;
    }

    public int height(){
        if (root == null){
            return 0;
        }
        return this.root.height();
    }

    // 添加结点
    public void add(Node node) {
        if (this.root == null) {
            this.root = node;
        } else {
            this.root.add(node);
        }
    }

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

}

class Node {

    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }
    
    // 获取当前左子树的高度
    public int leftHeight(){
        if (this.left == null){
            return 0;
        }
        return this.left.height();
    }
    
    // 获取当前结点右子树的高度
    public int rightHeight(){
        if (this.right == null){
            return 0;
        }
        return this.right.height();
    }

    // 获取当前结点的高度
    public int height() {
        return Math.max(
                (this.left == null ? 0 : this.left.height()),
                (this.right == null ? 0 : this.right.height())
        ) + 1;
    }

    // 左旋转
    public void leftRote(){
        // 创建一个新结点，并设置值等于当前结点的值
        Node newNode = new Node(value);
        // 使新结点的左结点指向当前结点的左结点
        newNode.left = left;
        // 新结点的右结点指向当前结点的右结点的左结点
        newNode.right = right.left;
        // 使当前结点的值指向新结点
        value = right.value;
        // 使当前结点的右结点指向当前结点的右结点的右结点
        right = right.right;
        // 使当前结点的左结点指向新结点
        left = newNode;
    }

    // 右旋转
    public void rightRote(){
        Node newNode = new Node(value);
        newNode.right = right;
        newNode.left = left.right;
        value = left.value;
        left = left.left;
        right = newNode;
    }

    // 添加结点
    public void add(Node node) {
        if (node == null) {
            return;
        }
        // 如果当前待插入结点的值小于当前结点，将其插入在左子树中
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            // 将当前结点插入右子树
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
        // 如果左子树的高度-右子树的高度 > 1 进行右旋转 反之进行左旋转
        if (this.leftHeight() - this.rightHeight() > 1){
            // 如果当前结点的左子树的右子树的高度>当前结点左子树的左子树的高度 则进行左旋转
            if (this.left != null && this.left.rightHeight() > this.left.leftHeight()){
                // 对当前结点的左结点进行左旋转
                this.left.leftRote();
                // 对当前结点右旋转
                this.rightRote();
            }else {
                this.rightRote();
            }
            return;
        }
        if (this.rightHeight() - this.leftHeight() > 1) {
            if (this.right != null && this.right.leftHeight() > this.right.rightHeight()){
                // 对当前结点的右结点进行右旋转
                this.right.rightRote();
                // 对当前结点进行左旋转
                this.leftRote();
            }else {
                this.leftRote();
            }
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}