更多详情内容请访问:数据结构与算法系列文章导读

1、数组

数组是可以在内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始

  • 优点:按照索引查询元素速度快
  • 缺点:①大小固定;②只能存储一种类型的数据;③中间部分的增删操作复杂,因为要移动其后方元素
  • 适用场景:频繁查询,很少增加或删除的情况
  • 复杂度:
    1. 通过下标查询时间复杂度为 O(1)
    2. 增删时间复杂度 O(n)

1.1 稀疏数组

稀疏数组的作用就是将一个对应的数组数据进行优化,比如,棋盘问题:

1653141684361

原数组中存在大量的无效数据,占据了大量的存储空间,真正有用的数据很少

此时压缩存储可以节省储存空间,避免资源的不必要的浪费,在数据序列化到磁盘时,还可以提高 IO 效率

处理方法:

  1. 记录数组一共有几行几列,有多少个不同的值
  2. 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模

image-20220313145551376

  • 二维数组 -> 稀疏数组
    1. 遍历二维数组,得到有效的数据的个数 sum
    2. 创建稀疏数组 sparseArray = int[sum+1][3];
    3. 将二维数组中的有效数据放入稀疏数组中
  • 稀疏数组 -> 二维数组
    1. 先读取稀疏数组的第 0 行数据,将稀疏数组转换成原始二维数组
    2. 遍历稀疏数组给原始二维数组赋值

public class SparseArray {
    /**
     * 二维数组 -> 稀疏数组
     * @param checkerboard 要转换为稀疏数组的二维数组
     * @return
     */
    public static int[][] arrayToSparseArray(int[][] checkerboard) {
        System.out.println("原二维数组:");
        sysArray(checkerboard);

        // 第1步:遍历二维数组,得到有效的数据的个数
        int sum = 0;
        for (int i = 0; i < checkerboard.length; i++) {
            for (int j = 0; j < checkerboard[i].length; j++){
                if (checkerboard[i][j] != 0) {
                    sum++;
                }
            }
        }

        // 第2步:创建稀疏数组
        int[][] sparseArray = new int[sum+1][3]; // 列是固定3列(行、列、值),行数是有效数据的个数+1(因为第0行需要存储行数、列数、值的个数)

        // 第3步:将二维数组中的有效数据放入稀疏数组中
        sparseArray[0][0] = checkerboard.length;    // 行数
        sparseArray[0][1] = checkerboard[0].length; // 列数
        sparseArray[0][2] = sum;                    // 有效数据个数
        int index = 0; // 用于标识是第几个非0有效数据
        for (int i = 0; i < checkerboard.length; i++) {
            for (int j = 0; j < checkerboard[i].length; j++){
                if (checkerboard[i][j] != 0) {
                    index++;
                    sparseArray[index][0] = i; // 存放数据对应的第几行
                    sparseArray[index][1] = j; // 存放数据对应的第几列
                    sparseArray[index][2] = checkerboard[i][j]; // 存放数据对应的值
                }
            }
        }
        System.out.println("转换后的稀疏数组:");
        sysArray(sparseArray);
        return sparseArray;
    }


    /**
     * 稀疏数组 -> 二维数组
     * @param sparseArray 要转换为二维数组的稀疏数组
     */
    public static int[][] sparseArrayToArray(int[][] sparseArray) {
        // 第1步:先读取稀疏数组的第0行数据,将稀疏数组转换成原始二维数组
        int[][] array = new int[sparseArray[0][0]][sparseArray[0][1]];

        // 第2步:遍历稀疏数组给原始二维数组赋值
        for (int i = 1; i < sparseArray.length; i++) {
            array[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        System.out.println("转换回二维数组:");
        sysArray(array);
        return array;
    }


    /**
     * 输出传入数组的内容
     * @param arr
     */
    public static void sysArray(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++){
                System.out.printf("%d\t", arr[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }
}

public class MyTest {
    @Test
    public void test(){
        // 先创建一个11×11的二维数组
        int[][] checkerboard = new int[6][7];
        // 在二维数组上摆放有效数据
        checkerboard[0][1] = 12;
        checkerboard[0][2] = 9;
        checkerboard[2][0] = -3;
        checkerboard[2][5] = 14;
        checkerboard[3][2] = 24;
        checkerboard[4][1] = 18;
        checkerboard[5][0] = 15;
        checkerboard[5][3] = -7;
        // 二维数组 -》 稀疏数组
        int[][] sparseArray = SparseArray.arrayToSparseArray(checkerboard);
        // 稀疏数组 -》 二维数组
        int[][] array = SparseArray.sparseArrayToArray(sparseArray);
    }
}

2、栈

栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。

  • 优点:提供后进先出(LIFO)的存取方式,添加速度快
  • 缺点:只能在一头操作,存取其他项很慢
  • 适用场景:①实现递归; ②字符串逆序 ;③符号是否匹配等
  • 复杂度:可由数组或者单向链表实现,是一种 ADT(抽象数据类型),入栈和出栈的时间复杂度都是 O(1)

2.1 数组模拟栈

  1. 定义一个 top 表示栈顶
  2. 入栈的操作:当有数据加入到栈时,top++; stack[top] = data;
  3. 出栈的操作:intValue = stack[top]; top--; return value;

public class ArrayStack {

    private int maxSize; // 栈的大小
    private int[] stack; // 数组模拟栈
    private int top;     // 栈顶

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

    // 栈满
    public boolean isFull() {
        return top == maxSize - 1;
    }

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

    // 入栈
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈已满,无法再加入");
            return;
        }
        top++;
        stack[top] = value;
    }

    // 出栈
    public int pop() {
        //先判断栈是否空
        if(isEmpty()) {
            //抛出异常
            throw new RuntimeException("栈空,没有数据~");
        }
        int value = stack[top];
        top--;
        return value;
    }

    // 显示栈的情况[遍历栈], 遍历时,需要从栈顶开始显示数据
    public void list(){
        if (isEmpty()) {
            System.out.println("栈空,没有数据~~");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d] = %d\n", i, stack[i]);
        }
    }
}

public class MyTest {

    public static void main(String[] args) {
        //测试一下ArrayStack 是否正确
        //先创建一个ArrayStack对象->表示栈
        ArrayStack stack = new ArrayStack(4);
        String key = "";
        boolean loop = true; //控制是否退出菜单
        Scanner scanner = new Scanner(System.in);

        while(loop) {
            System.out.println("show: 表示显示栈");
            System.out.println("exit: 退出程序");
            System.out.println("push: 表示添加数据到栈(入栈)");
            System.out.println("pop: 表示从栈取出数据(出栈)");
            System.out.println("请输入你的选择");
            key = scanner.next();
            switch (key) {
                case "show":
                    stack.list();
                    break;
                case "push":
                    System.out.println("请输入一个数");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    try {
                        int res = stack.pop();
                        System.out.printf("出栈的数据是 %d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }

        System.out.println("程序退出~~~");
    }
}

2.2 波兰表达式

  1. 前缀表达式:又称波兰式,前缀表达式的运算符位于操作数之前

    举例说明: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6
  2. 中缀表达式:是人最为熟知的,对于计算机来说却并不友好,因此在计算结果时,常会将中缀表达式转为其他表达式

    举例说明: (3+4)×5-6 对应的中缀表达式就是 (3+4)×5-6
  3. 后缀表达式:又称逆波兰表达式,与前缀表达式类似,运算符位于操作数之后

    举例说明: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

2.2.1 中缀表达式

  1. 通过一个 index 值(索引),来遍历我们的表达式
  2. 如果我们发现是一个数字,就直接入数栈
  3. 如果发现扫描到是一个符号:
    • 如果发现当前的符号栈为空,就直接入栈
    • 如果符号栈有操作符,就进行比较:
      • 如果当前的操作符的优先级小于或者等于栈中的操作符, 就需要从数栈中 pop 出两个数,在从符号栈中 pop 出一个符号,进行运算,将得到结果入数栈,然后将当前的操作符入符号栈
      • 如果当前的操作符的优先级大于栈中的操作符, 就直接入符号栈
  4. 当表达式扫描完毕,就顺序的从 数栈和符号栈中 pop 出相应的数和符号,并运行
  5. 最后在数栈只有一个数字,就是表达式的结果

public class ArrayStack {

    private int maxSize; // 栈的大小
    private int[] stack; // 数组,数组模拟栈,数据就放在该数组
    private int top = -1;// top表示栈顶,初始化为-1

    //构造器
    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    //增加一个方法,可以返回当前栈顶的值, 但是不是真正的pop
    public int peek() {
        return stack[top];
    }

    //栈满
    public boolean isFull() {
        return top == maxSize - 1;
    }

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

    //入栈-push
    public void push(int value) {
        //先判断栈是否满
        if(isFull()) {
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top] = value;
    }

    //出栈
    public int pop() {
        //先判断栈是否空
        if(isEmpty()) {
            //抛出异常
            throw new RuntimeException("栈空,没有数据~");
        }
        int value = stack[top];
        top--;
        return value;
    }

    //显示栈的情况[遍历栈], 遍历时,需要从栈顶开始显示数据
    public void list() {
        if(isEmpty()) {
            System.out.println("栈空,没有数据~~");
            return;
        }
        //需要从栈顶开始显示数据
        for(int i = top; i >= 0 ; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }

    /**
     * 返回运算符的优先级,优先级是程序员来确定, 优先级使用数字表示
     * 数字越大,则优先级就越高.
     */
    public int priority(int oper) {
        if(oper == '*' || oper == '/'){
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1; // 假定目前的表达式只有 +, - , * , /
        }
    }

    /**
     * 判断是不是一个运算符
     */
    public boolean isOper(char val) {
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    /**
     * 计算方法
     */
    public int cal(int num1, int num2, int oper) {
        int res = 0; // res 用于存放计算的结果
        switch (oper) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;// 注意顺序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }
}

public class MyTest {

    public static void main(String[] args) {
        // 根据前面的思路,完成表达式的运算
        String expression = "7*2*2-5+1-5+3-4"; // 如何处理类似15这样的多位数?
        // 创建两个栈,数栈,一个符号栈
        ArrayStack numStack = new ArrayStack(10);
        ArrayStack operStack = new ArrayStack(10);
        // 定义需要的相关变量
        int index=  0; // 用于扫描
        int num1 = 0;
        int num2 = 0;
        int result = 0;
        int oper = 0;
        char ch = ' ';
        String keepNum = ""; // 用于拼接多位数
        while (true) {
            // 依次得到expression 的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            // 判断ch是什么,然后做相应的处理
            if (operStack.isOper(ch)) { // 如果是运算符
                // 判断当前的符号栈是否为空
                if (!operStack.isEmpty()) {
                    //如果符号栈有操作符,就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数,
                    //在从符号栈中pop出一个符号,进行运算,将得到结果,入数栈,然后将当前的操作符入符号栈
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        result = numStack.cal(num1, num2, oper);
                        // 把运算的结果如数栈
                        numStack.push(result);
                        // 然后将当前的操作符入符号栈
                        operStack.push(ch);
                    } else {
                        // 如果当前的操作符的优先级大于栈中的操作符, 就直接入符号栈.
                        operStack.push(ch);
                    }
                } else {
                    //如果当前符号栈为空则直接入符号栈
                    operStack.push(ch);
                }
            } else {
                // 如果是数字,则入数字栈
                //1. 当处理多位数时,不能发现是一个数就立即入栈,因为他可能是多位数
                //2. 在处理数,需要向 expression 的表达式的 index 后再看一位,如果是数就进行扫描,如果是符号才入栈
                //3. 因此我们需要定义一个变量 字符串,用于拼接
                keepNum += ch;
                //如果ch已经是expression的最后一位,就直接入栈
                if (index == expression.length() - 1){
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    // 判断下一个字符是不是数字,如果是数字,就继续扫描,如果是运算符,则入栈。注意是看后一位,不是index++
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))){
                        // 如果后一位是运算符,则入栈
                        numStack.push(Integer.parseInt(keepNum));
                        keepNum = "";
                    }
                }
            }
            //让index + 1, 并判断是否扫描到expression最后.
            index++;
            if (index >= expression.length()) {
                break;
            }
        }

        //当表达式扫描完毕,就顺序的从 数栈和符号栈中pop出相应的数和符号,并运行
        while (true) {
            if (operStack.isEmpty()) { // 如果符号栈为空,则计算到最后的结果, 数栈中只有一个数字【结果】
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            result = numStack.cal(num1, num2, oper);
            numStack.push(result);
        }

        //将数栈的最后数,pop出,就是结果
        int res2 = numStack.pop();
        System.out.printf("表达式 %s = %d", expression, res2);
    }
}

2.2.2 中缀表达式转后缀表达式

后缀表达式适合计算机运算,但在表达式很长的情况下,人却不容易写出来,因此在实际开发中,需要将中缀表达式转为后缀表达式

  1. 初始化两个栈:运算符栈 s1 和存储中间结果的栈 s2
  2. 从左至右扫描中缀表达式
  3. 遇到操作数时,将其压入 s2
  4. 遇到运算符时,比较其与 s1 栈顶运算符的优先级:
    • 如果 s1 为空,或栈顶运算符为左括号,则直接将此运算符入栈
    • 否则,若优先级比栈顶运算符的高,也将运算符压入 s1
    • 否则,将 s1 栈顶的运算符弹出并压入到 s2 中,再次重新与 s1 栈顶运算符相比较
  5. 遇到括号时:
    • 如果是左括号,则直接压入 s1
    • 如果是右括号,则一次弹出 s1 栈顶的运算符,并压入 s2,直到遇到左括号为止,此时将这一对括号丢弃
  6. 重复步骤2—步骤5,直到表达式最右边
  7. 将 s1 中剩余的运算符一次弹出并压入 s2
  8. 依次弹出 s2 中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式

public class PolandNotation {
    /**
     * 方法:将中缀表达式转成对应的 List
     */
    public static List<String> toInfixExpressionList(String s) {
        // 定义一个List,存放中缀表达式 对应的内容
        List<String> list = new ArrayList<>();
        int i = 0; // 这时是一个指针,用于遍历中缀表达式字符串
        String str; // 对多位数的拼接
        char c; // 每遍历到一个字符,就放入到c
        do {
            // 如果c是一个非数字,需要加入到 list
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                list.add("" + c);
                i++; // i需要后移
            } else { // 如果是一个数,需要考虑多位数
                str = ""; // 先将 str 置成""  '0'[48]->'9'[57]
                while(i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57) {
                    str += c; // 拼接
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());
        return list;
    }

    /**
     * 方法:将得到的中缀表达式对应的 List => 后缀表达式对应的 List
     */
    public static List<String> parseSuffixExpreesionList(List<String> list) {
        // 定义两个栈
        Stack<String> s1 = new Stack<String>(); // 符号栈
        // 说明:因为s2 这个栈,在整个转换过程中,没有pop操作,而且后面我们还需要逆序输出
        // 因此比较麻烦,这里我们就不用 Stack<String> 直接使用 List<String> s2
        List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2

        // 遍历list
        for(String item: list) {
            // 如果是一个数,加入s2
            if(item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                // 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
                while(!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();// !!! 将 ( 弹出 s1栈, 消除小括号
            } else {
                // 当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中,再次转到(4.1)与s1中新的栈顶运算符相比较
                while(s1.size() != 0 && getValue(item) <= getValue(s1.peek())) {
                    s2.add(s1.pop());
                }
                // 还需要将item压入栈
                s1.push(item);
            }
        }
        // 将s1中剩余的运算符依次弹出并加入s2
        while(s1.size() != 0) {
            s2.add(s1.pop());
        }
        return s2; // 注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
    }

    /**
     * 比较运算符优先级
     */
    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = 1;
                break;
            case "-":
                result = 1;
                break;
            case "*":
                result = 2;
                break;
            case "/":
                result = 2;
                break;
            default:
                System.out.println("不存在该运算符" + operation);
                break;
        }
        return result;
    }

    /**
     * 将一个逆波兰表达式,依次将数据和运算符放入到 ArrayList 中
     */
    public static List<String> getListString(String suffixExpression) {
        // 将 suffixExpression 分割
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for(String ele : split) {
            list.add(ele);
        }
        return list;
    }

    /**
     * 完成对逆波兰表达式的运算
     */
    public static int calculate(List<String> list) {
        // 创建给栈, 只需要一个栈即可
        Stack<String> stack = new Stack<String>();
        // 遍历 list
        for (String item : list) {
            // 这里使用正则表达式来取出数
            if (item.matches("\\d+")) { // 匹配的是多位数
                // 入栈
                stack.push(item);
            } else {
                // pop出两个数,并运算, 再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                // 把res 入栈
                stack.push("" + res);
            }

        }
        // 最后留在stack中的数据是运算结果
        return Integer.parseInt(stack.pop());
    }
}

public class MyTest {

    public static void main(String[] args) {
        String expression = "1+((12+3)*4)-5";//注意表达式

        List<String> infixExpressionList = PolandNotation.toInfixExpressionList(expression);
        System.out.println("中缀表达式对应的List=" + infixExpressionList); // [1,+,(,(,12,+,3,),*,4,),-,5]

        List<String> suffixExpreesionList = PolandNotation.parseSuffixExpreesionList(infixExpressionList);
        System.out.println("后缀表达式对应的List" + suffixExpreesionList); // [1,12,3,+,4,*,+,5,–]

        int calculate = PolandNotation.calculate(suffixExpreesionList);
        System.out.printf("expression=%d", calculate); // 56
    }
}

3、队列

队列是一个有序列表,可以用数组或链表实现

队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队

  • 优点:提供先进先出的存取方式,添加速度快
  • 缺点:只能在一头添加一头获取,存取其他项都很慢
  • 适用场景:多线程阻塞队列管理
  • 复杂度:
    1. 队列也可以由数组和双端链表实现,也是一种 ADT,出队和入队的时间复杂度是 O(1)
    2. 优先级队列的插入操作需要 O(n) 的时间,而删除操作则需要 O(1) 的时间

3.1 数组模拟普通队列

  1. 队列本身是有序列表,若使用数组的结构来存储存储队列的数据,则队列数组的声明如下图,其中 maxSize是该队列的最大容量
  2. 因为队列的输出、输入分别是从前后端处理,因此需要两个变量 fontrear 分别记录队列头尾的下标,font 随数据输出而改变,而 rear 则是随着数据输入而改变

image-20220228120953402

public class ArrayQueue {

    private int maxSize;    // 表示数组的最大容量
    private int front;      // 队列头
    private int rear;       // 队列尾
    private int[] arr;      // 该数组用于存放数据,模拟队列

    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.front = -1;    // 指向队列头,用于出队列时使用
        this.rear = -1;     // 指向队列尾,用于入队列时使用
        this.arr = new int[maxSize];
    }

    // 判断队列是否已满
    public boolean isFull(){
        return rear == maxSize -1; // 如果尾巴指针指向最大容量了,说明已满
    }

    // 判断队列是否为空
    public boolean isEmpty(){
        return front == rear;
    }

    // 添加数据到队列中
    public void addQueue(int data) {
        if (isFull()) {
            throw new RuntimeException("队列已满,添加数据失败");
        }
        rear++; // 尾指针向后移动
        arr[rear] = data;
    }

    // 从队列中获取数据(出队列)
    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空,不可取数据");
        }
        front++; // 头指针向后移动
        return arr[front];
    }

    // 显示队列中所有的数据
    public void showQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("第[%d]个数据,arr[%d]=[%d]\n", i+1, i, arr[i]);
        }
    }

    // 显示队列头数据,不是取出数据
    public int headQueue(){
        if (isEmpty()) {
            throw new RuntimeException("队列为空,不存在头数据");
        }
        return arr[front + 1];
    }

}

public class MyTest {

    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueue(3);
        char key = ' '; // 接受用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        // 输出一个菜单
        while (loop) {
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            System.out.println("s(show):显示队列");
            System.out.println("h(head):查看队列头的数据");
            key = scanner.next().charAt(0);
            switch (key) {
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                case 'a':
                    try {
                        System.out.println("输入一个数:");
                        int value = scanner.nextInt();
                        queue.addQueue(value);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'g': //取出数据
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 's':
                    try {
                        queue.showQueue();
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'h': //查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                default:
                    break;
            }
        }
    }
}

3.2 数组模拟环形队列

上面的模拟普通队列,存在一个问题:数组使用一次就不能够再使用,没有复用性

因此对前面的数组模拟队列优化,充分利用数组,将其看成一个环形的队列。

1653145841675

只凭 rear == front 的方式无法判断队列是满的还是空的,为了解决这个问题有两种方式:

  1. 另设一个标志位以区别队列是空还是满
  2. 少用一个元素空间,约定以“队列头指针 front 在队尾指针 rear 的下一个位置上”作为队列“满”状态的标志

因此在普通队列的基础上做些改动:

  • 变量
    1. front(头索引)初始值:0 ,指向队列的第一个元素
    2. rear(尾索引)初始值:0 ,指向队列最后一个元素的下一个元素
    3. maxsize:数组的最大长度
  • 分析条件
    1. 尾索引的下一个为头索引时表示队列满,将队列容量空出一个作为约定,判断满的条件:(rear + 1) % maxsize == front
    2. 判断队列空的条件:rear == front
    3. 队列中有效数据的个数:(rear + maxsize - front) % maxsize

public class CircleArrayQueue {

    private int maxSize;    // 表示数组的最大容量
    private int front;      // front 变量的含义做一个调整:front 就指向队列的第一个元素,即 arr[front] 就是队列的第一个元素
    private int rear;       // rear 变量含义做一个调整:rear 指向队列的最后一个元素的后一个位置,因为希望空出一个空间作为约定
    private int[] arr;      // 该数据用于存放数据,模拟队列

    // 创建队列的构造器
    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
    }

    //判断队列是否满
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return rear == front;
    }

    // 求出队列中有效数据的个数
    public int size() {
        return ((rear + maxSize - front) % maxSize);
    }

    // 添加数据到队列
    public void addQueue(int data) {
        if (isFull()) {
            throw new RuntimeException("队列已满,添加失败");
        }
        arr[rear] = data; // 直接将数据加入队列中
        rear = (rear + 1) % maxSize;
    }

    // 将数据中队列中取出
    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("空队列,无法取出数据");
        }
        int retValue = arr[front]; // 取出数据
        front = (front + 1) % maxSize;
        return retValue;
    }

    // 显示数组中的所有数据(真正数组中保存着的)
    public void showQueue_real() {
        if (isEmpty()) {
            throw new RuntimeException("空队列,无法遍历");
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=[%d]\n", i, arr[i]);
        }
    }
    // 显示队列中所有的数据(有效数据)
    public void showQueue_valid() {
        if (isEmpty()) {
            throw new RuntimeException("空队列,无法遍历");
        }
        for (int i = front; i < front + size(); i++) {
            System.out.printf("arr[%d]=[%d]\n", i % maxSize, arr[i % maxSize]);
        }
    }

    // 显示队列的头数据,注意不是取出数据
    public int headQueue(){
        if (isEmpty()) {
            throw new RuntimeException("空队列,无法读取头数据");
        }
        return arr[front];
    }
}

public class MyTest {

    public static void main(String[] args) {
        CircleArrayQueue queue = new CircleArrayQueue(3);
        char key = ' '; // 接受用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        // 输出一个菜单
        while (loop) {
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            System.out.println("s(show_real):显示队列真实数据");
            System.out.println("r(show_valid):显示队列有效数据");
            System.out.println("h(head):查看队列头的数据");
            key = scanner.next().charAt(0);
            switch (key) {
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                case 'a':
                    try {
                        System.out.println("输入一个数:");
                        int value = scanner.nextInt();
                        queue.addQueue(value);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'g': //取出数据
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 's':
                    try {
                        queue.showQueue_real();
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'r':
                    try {
                        queue.showQueue_valid();
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'h': //查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                default:
                    break;
            }
        }
    }
}

4、链表

链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现

  • 优点:插入快,删除快,只需要修改元素指针即可
  • 缺点:查找慢,需要从第一个节点逐个查找
  • 适用场景:少查询,需要频繁新增或删除的情况
  • 复杂度:
    1. 查询的时间复杂度为 O(n)
    2. 增删的时间复杂度为 O(1)

4.1 单链表

单向链表中内部节点 Node 类:

public class Node {

    public int no;
    public String name;
    public Node next;

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

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

单向链表 SingleLinkedList 类:

public class SingleLinkedList {

    private Node head = new Node(0, ""); // 头指针

    // 添加节点至单向链表的末尾
    public void addToRear(Node node) {
        Node pointer = head; // 因为头节点不能动,因此定义一个辅助遍历指针
        while (true) {
            if (pointer.next == null) { // 说明已经遍历到末尾节点,跳出循环
                break;
            }
            pointer = pointer.next; // 指针向后遍历
        }
        pointer.next = node; // 末尾节点的 next 指向新加入的节点
    }

    // 添加节点(根据 no 大小按照顺序添加)
    public void addByOrder(Node node) {
        Node pointer = head; // 因为头节点不能动,因此定义一个辅助遍历指针
        while (true) {
            if (pointer.next == null) { // 说明已经遍历到链表的最后了仍未找到插入位置,因此应该将该点放入链表尾
                break;
            }
            if (pointer.next.no > node.no) { // 当前节点的下一节点的 no > 要插入节点的 no,说明当前节点应该插在该指针节点的下一节点位置
                break;
            } else if (pointer.next.no == node.no) {
                System.out.printf("准备插入的编号 %d 已经存在了, 不能加入\n", node.no);
                return;
            }
            pointer = pointer.next; // 指针向后遍历
        }
        // 执行到这一步说明此时 pointer 就是要插入节点的前一节点
        node.next = pointer.next; // 插入节点的 next 指向 pointer 原本指向的节点
        pointer.next = node; // pointer 节点的 next 指向要插入的节点
    }

    // 修改节点
    public void update(Node node) {
        Node pointer = head; // 因为头节点不能动,因此定义一个辅助遍历指针
        while(true) {
            if (pointer == null) {
                System.out.printf("没有找到 编号 %d 的节点,不能修改\n", node.no);
                return;
            }
            if (pointer.no ==  node.no) {
                pointer.name = node.name;
                return;
            }
            pointer = pointer.next;
        }
    }

    // 删除节点
    public void delete(int no) {
        Node pointer = head; // 因为头节点不能动,因此定义一个辅助遍历指针
        while (true) {
            if (pointer.next == null) {
                System.out.printf("要删除的 %d 节点不存在\n", no);
                return;
            }
            if (pointer.next.no ==  no) { // 说明该节点的下一节点就是要删除的节点
                break;
            }
            pointer = pointer.next;
        }
        // pointer.next = null; // 没有必要,垃圾回收机制会自动回收
        pointer.next = pointer.next.next;
    }

    // 遍历输出所有的节点
    public void list() {
        Node pointer = head; // 因为头节点不能动,因此定义一个辅助遍历指针
        while (true) {
            if (pointer.next == null) { // 说明已经遍历到末尾节点,跳出循环
                break;
            }
            pointer = pointer.next;
            System.out.println(pointer);
        }
    }
}

public class MyTest {

    // 测试 addToRear() 增方法 与 list() 查方法
    @Test
    public void test01(){
        Node node1 = new Node(1, "");
        Node node2 = new Node(2, "");
        Node node3 = new Node(3, "");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addToRear(node1);
        singleLinkedList.addToRear(node2);
        singleLinkedList.addToRear(node3);
        singleLinkedList.list();
    }

    // 测试 addByOrder() 增方法 与 list() 查方法
    @Test
    public void test02(){
        Node node1 = new Node(1, "");
        Node node2 = new Node(2, "");
        Node node3 = new Node(3, "");
        Node node4 = new Node(5, "");
        Node node5 = new Node(5, "");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(node1);
        singleLinkedList.addByOrder(node4);
        singleLinkedList.addByOrder(node2);
        singleLinkedList.addByOrder(node3);
        singleLinkedList.addByOrder(node5);
        singleLinkedList.list();
    }

    // 测试 update() 查方法
    @Test
    public void test03(){
        Node node1 = new Node(1, "");
        Node node2 = new Node(2, "");
        Node node3 = new Node(3, "");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addToRear(node1);
        singleLinkedList.addToRear(node2);
        singleLinkedList.addToRear(node3);
        singleLinkedList.update(new Node(3, "修改后的 node3"));
        singleLinkedList.update(new Node(4, "修改后的 node3"));
        singleLinkedList.list();
    }

    // 测试 delete() 查方法
    @Test
    public void test04(){
        Node node1 = new Node(1, "");
        Node node2 = new Node(2, "");
        Node node3 = new Node(3, "");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addToRear(node1);
        singleLinkedList.addToRear(node2);
        singleLinkedList.addToRear(node3);
        singleLinkedList.delete(1);
        singleLinkedList.delete(4);
        singleLinkedList.list();
    }
}

4.2 双向链表

双向链表中内部节点 Node 类:

public class Node {

    public int no;
    public String name;
    public Node pre;
    public Node next;

    public Node(int no) {
        this.no = no;
        this.name = "";
    }

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

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

双向链表 DoubleLinkedList 类:

public class DoubleLinkedList {

    private Node head = new Node(0);

    // 添加节点(添加到双向链表的最后)
    public void addToRear(Node node) {
        Node pointer = head;
        while (true) {
            if (pointer.next == null) {
                break;
            }
            pointer = pointer.next;
        }
        pointer.next = node;  // 末尾节点的 next 指向新加入的节点
        node.pre = pointer; // 新插入节点的 pre 指向末尾节点
    }

    // 添加节点(按顺序添加)
    public void addByOrder(Node node) {
        Node pointer = head;
        while (pointer.next != null) { // pointer.next
            // 为空的时候说明已经遍历到最后一个元素了,新节点按顺序也应插在最后
            if (pointer.next.no > node.no) { // 下一节点的 no > 要插入节点的 no,说明该新节点应该插在该节点的后方
                break;
            } else if (pointer.next.no == node.no) {
                System.out.printf("准备插入的编号 %d 已经存在了, 不能加入\n", node.no);
                return;
            }
            pointer = pointer.next; // 指针后移
        }
        Node orginalNext = pointer.next; // 定义一个变量存储该节点 next 指向的节点
        pointer.next = node; // 现在该节点的 next 指向新插入的节点
        node.pre = pointer; // 新插入节点的 pre 指向该节点
        node.next = orginalNext; // 新插入的 next 指向原来该节点的 next
    }

    // 修改节点
    public void update(Node node) {
        Node pointer = head;
        while (pointer != null) {
            if (pointer.no == node.no) {
                pointer.name = node.name;
                return;
            }
            pointer = pointer.next;
        }
        System.out.printf("没有找到 编号 %d 的节点,不能修改\n", node.no);
    }

    // 删除节点
    public void delete(int no) {
        Node pointer = head;
        while (pointer.next != null) {
            if (pointer.next.no == no) { // 说明该节点的下一节点就是要删除的节点
                Node node = pointer.next.next;
                pointer.next = node;
                if (node != null) {
                    node.pre = pointer;
                }
                return;
            }
            pointer = pointer.next;
        }
        System.out.printf("要删除的 %d 节点不存在\n", no);
    }

    // 遍历节点(与单链表没有不同)
    public void list() {
        Node pointer = head;
        while (true) {
            if (pointer.next == null) {
                break;
            }
            System.out.println(pointer.next);
            pointer = pointer.next;
        }
    }
}

public class MyTest {

    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);
    DoubleLinkedList doubleLinkedList = new DoubleLinkedList();

    // 测试 addToRear() 增方法 与 list() 查方法
    @Test
    public void test01(){
        doubleLinkedList.addToRear(node1);
        doubleLinkedList.addToRear(node2);
        doubleLinkedList.addToRear(node4);
        doubleLinkedList.addToRear(node3);
        doubleLinkedList.addToRear(new Node(4));
        doubleLinkedList.list();
    }

    // 测试 addByOrder() 增方法 与 list() 查方法
    @Test
    public void test02(){
        doubleLinkedList.addByOrder(node4);
        doubleLinkedList.addByOrder(node1);
        doubleLinkedList.addByOrder(node2);
        doubleLinkedList.addByOrder(node3);
        doubleLinkedList.addByOrder(node5);
        doubleLinkedList.addByOrder(node5);
        doubleLinkedList.list();
    }

    // 测试 update() 方法
    @Test
    public void test03(){
        doubleLinkedList.addToRear(node1);
        doubleLinkedList.addToRear(node2);
        doubleLinkedList.addToRear(node3);
        System.out.println("原链表");
        doubleLinkedList.list();
        doubleLinkedList.update(new Node(2, "修改后的 node2"));
        doubleLinkedList.update(new Node(3, "修改后的 node3"));
        doubleLinkedList.update(new Node(4, "修改后的 node4"));
        System.out.println("现链表");
        doubleLinkedList.list();
    }

    // 测试 delete() 方法
    @Test
    public void test04(){
        doubleLinkedList.addToRear(node1);
        doubleLinkedList.addToRear(node2);
        doubleLinkedList.addToRear(node3);
        doubleLinkedList.delete(1);
        doubleLinkedList.delete(3);
        doubleLinkedList.delete(4);
        doubleLinkedList.list();
    }
}

4.3 单向环形链表

Josephu 约瑟夫问题:

设 n 个人围坐一圈,从编号为 k(1≤k≤n) 的人从1开始报数,数到 m 的士兵将被杀死,它的下一位又从1开始报数,以此类推,直到最后一名士兵存活。

遍历环形列表:

  1. 需求创建一个辅助指针 pointer,事先应该指向环形链表的最后这个节点
  2. 报数前,先让 firstNode和 pointer 移动 k-1 次
  3. 当报数时,让 firstNode和 pointer 指针同时移动 m-1 次,这时就可以将 firstNode 指向的节点移出

单向环形链表中内部节点 Node 类:

public class Node {

    public int no;
    public Node next;

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

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

单向环形链表 CircleSingleLinkedList 类:

public class CircleSingleLinkedList {

    public Node firstNode = null;
    public Node pointer = null;

    /**
     * 添加节点,构造一个单向环形链表
     * @param num 该链表所拥有的的节点数
     */
    public void add(int num) {
        if (num < 1) {
            throw new RuntimeException("输入错误,节点个数至少≥1");
        }
        for (int i = 1; i <= num; i++) {
            Node node = new Node(i);
            if (i == 1) { // 如果是第一个节点,就让当前指针指向第一个节点
                firstNode = node;
                pointer = node;
                continue;
            }
            // 执行到这说明不是第一个节点了,把当前节点的.next 指向新插入的节点,指针再后移指向新插入的节点
            pointer.next = node;
            pointer = node;
            // 说明是最后的节点了
            if (i == num) {
                pointer.next = firstNode;
            }
        }
    }

    /**
     * 遍历环形链表
     */
    public void list() {
        if (firstNode == null) {
            throw new RuntimeException("链表为空");
        }
        pointer = firstNode; // 执行完 add() 方法后的 pointer 原本指向最后节点,将他重新定义指向第一个节点开始遍历
        do {
            System.out.println(pointer);
            pointer = pointer.next;
        } while (pointer != firstNode); // 直到 pointer 和第一节点一致,说明已经遍历完一圈了
    }

    /**
     * 根据输入,计算出出圈的顺序
     * @param begin 从第几个节点开始数
     * @param count 数到第几个的时候出圈
     */
    public void outOfCircle(int begin, int count){
        if (begin < 1 || count < 1 || firstNode == null) {
            throw new RuntimeException("数据不合格");
        }
        // 辅助指针事先指向环形链表的最后节点
        pointer = firstNode; // 初始化指针指向第一个节点位置
        while (true) {
            if (pointer.next == firstNode) { // 说明 pointer 已经指向了最后的小孩节点
                break;
            }
            pointer = pointer.next;
        }
        // 报数前,先让 firstNode和 pointer 移动 k-1 次,也就是移动到第一个报数的节点位置
        for (int i = 0; i < begin - 1; i++) {
            firstNode = firstNode.next;
            pointer = pointer.next;
        }
        // 报数时,让 firstNode和 pointer 指针同时移动 m-1 次,这时就可以将 firstNode 指向的节点移出
        while (true) {
            if (pointer == firstNode) { // 说明圈中只有一个节点
                break;
            }
            for (int i = 0; i < count - 1; i++) {
                firstNode = firstNode.next;
                pointer = pointer.next;
            }
            // 此时 firstNode 指向的节点就是要出圈的节点
            System.out.printf("%d -> ", firstNode.no);
            firstNode = firstNode.next;
            pointer.next = firstNode;
        }
        System.out.println(firstNode.no);
    }
}

public class MyTest {

    @Test
    public void test01() {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.add(5);
        circleSingleLinkedList.list();
    }

    @Test
    public void test02(){
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.add(5);
        circleSingleLinkedList.outOfCircle(1, 2);
    }

    @Test
    public void test03(){
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.add(20);
        circleSingleLinkedList.outOfCircle(5, 5); 
    }
}

5、哈希表

也叫散列表,是根据键 Key 直接访问在内存存储位置的数据结构

  • 优点:如果关键字已知,则存取速度极快,插入快
  • 缺点:删除慢,如果不知道关键字则存取很慢,对存储空间使用不充分
  • 哈希表适用于那种查找性能要求高,数据元素之间无逻辑关系要求的情况。
    Hash表在海量数据处理中有着广泛应用

实现原理:通过哈希函数散列函数)将元素的键映射为数组下标(转化后的值叫做哈希值散列值),然后在对应下标位置存储记录值。当我们按照键查询元素时,就是用同样的哈希函数,将键转化数组下标,从对应的数组下标的位置取数据

常见的哈希函数

  1. 直接定址法:即 f(key) = a*key + b,f 表示哈希函数,a、b 是常量,key 是键值
  2. 数字分析法:即对数字做左移、右移、反转等操作获取散列值
  3. 除数留余法:即 f(key) = key % p,p 表示容器数量
  4. 随机数法: 即f(key) = random(key),比如负载均衡的random机制

设计再好的哈希函数也无法避免哈希冲突,原因是哈希值是非负整数,总量是有限的,但是现实世界中要处理的键值是无限的,将无限的数据映射到有限的集合,肯定避免不了冲突。事实上,如果不考虑哈希冲突,哈希表的查找效率是非常高的,时间复杂度是 O(1),比二分查找效率还要高,但是因为无法避免哈希冲突,所以哈希表查找的时间复杂度取决于哈希冲突

解决哈希冲突的常用方法

  1. 开放寻址法:
    • 线性探测:出现散列冲突之后,就去寻找下一个空的散列地址,线性寻址步长是1
    • 二次探测:线性寻址步长的2次方,其它逻辑一样
    • 随机探测:随机探测每次步长随机
  2. 再哈希法:发生散列冲突后,换一个散列函数计算散列值。这种方法不易产生聚集,但增加了计算时间
  3. 链地址法(拉链法):将所有哈希地址为 i 的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第 i 个单元中,适用于经常插入和删除的情况
  4. 建立公共溢出区:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表

5.1 链表模拟哈希表

HashTable 类:

public class HashTable {

    private EmpLinkedList[] empLinkedListArray;
    private int size; // 表示有多少条链表


    // 编写一个散列函数,使用一个简单的取模法
    public int hashFun(int id) {
        return id % size;
    }

    // 初始化构造方法
    public HashTable(int size) {
        this.size = size;
        // 初始化 empLinkedListArray
        empLinkedListArray = new EmpLinkedList[size];
        // 以上仅仅只是创建了一个数组,这时候还要分别初始化数组中每一个元素(链表)
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    // 添加雇员
    public void add(Emp emp) {
        // 根据员工的 id,得到员工应添加到哪条链表
        int empLinkedListNo = hashFun(emp.id);
        // 将 emp 添加到对应链表中
        empLinkedListArray[empLinkedListNo].add(emp);
    }

    //遍历所有的链表,遍历 HashTable
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }

    // 根据输入的id,查找雇员
    public void findEmpById(int id) {
        int empLinkedListNo = hashFun(id);
        Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id);
        if (emp != null) {//找到
            System.out.printf("在第%d条链表中找到 雇员 id = %d\n", (empLinkedListNo + 1), id);
        } else {
            System.out.println("在哈希表中,没有找到该雇员~");
        }
    }

    // 根据输入的 id,删除指定的雇员
    public void deleteEmpById(int id) {
        int empLinkedListNo = hashFun(id);
        empLinkedListArray[empLinkedListNo].delete(id);
    }
}

EmpLinkedList 类:

public class EmpLinkedList {

    //头指针,执行第一个Emp,因此我们这个链表的head 是直接指向第一个Emp
    private Emp head = new Emp(0, ""); //默认null

    // 假定,当添加雇员时,id 是自增长,即 id 的分配总是从小到大,因此我们将该雇员直接加入到本链表的最后即可
    public void add(Emp emp) {
        Emp curEmp = head;
        if (curEmp.next == null) {// 说明是添加的第一个员工
            curEmp.next = emp;
            return;
        }
        // 如果不是第一个雇员,则使用一个辅助指针,帮助定位到最后
        while (true) {
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next; // 后移
        }
        // 退出时直接将 emp 加入链表
        curEmp.next = emp;
    }

    // 遍历链表的雇员信息
    public void list(int no) {
        if (head.next == null) {
            System.out.println("第 " + (no + 1) + " 链表为空");
            return;
        }
        System.out.print("第 " + (no + 1) + " 链表的信息为");
        Emp curEmp = head;
        while (true) {
            if (curEmp.next == null) { // 说明 curEmp 已经是最后节点
                break;
            }
            System.out.printf("=> id=%d name=%s\t", curEmp.next.id, curEmp.next.name);
            curEmp = curEmp.next;
        }
        System.out.println();
    }

    // 根据 id 查找雇员,如果查找到,就返回 Emp, 如果没有找到,就返回 null
    public Emp findEmpById(int id) {
        // 判断链表是否为空
        if (head == null) {
            System.out.println("链表为空");
            return null;
        }
        // 辅助指针
        Emp curEmp = head;
        while (true) {
            if (curEmp.id == id) { // 找到
                break; // 这时curEmp就指向要查找的雇员
            }
            //退出
            if (curEmp.next == null) { // 说明遍历当前链表没有找到该雇员
                curEmp = null;
                break;
            }
            curEmp = curEmp.next; // 以后
        }
        return curEmp;
    }

    // 根据 id 删除雇员
    public void delete(int id) {
        Emp curEmp = head;
        boolean flag = false;
        while (true) {
            if (curEmp.next.id == id) { // 说明找到员工了
                flag = true;
                break;
            }
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next;
        }
        if (flag) {
            curEmp.next = curEmp.next.next;
        } else {
            System.out.println("未找到该员工");
        }
    }
}

Emp 类:

public class Emp {
    public int id;
    public String name;
    public Emp next;

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

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

public class MyTest {

    public static void main(String[] args) {
        //创建哈希表
        HashTable hashTab = new HashTable(7);

        //写一个简单的菜单
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add:  添加雇员");
            System.out.println("list: 显示雇员");
            System.out.println("find: 查找雇员");
            System.out.println("delete: 删除雇员");
            System.out.println("exit: 退出系统");

            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("输入id");
                    int id = scanner.nextInt();
                    System.out.println("输入名字");
                    String name = scanner.next();
                    //创建 雇员
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的id");
                    id = scanner.nextInt();
                    hashTab.findEmpById(id);
                    break;
                case "delete":
                    System.out.println("请输入要删除的id");
                    id = scanner.nextInt();
                    hashTab.deleteEmpById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}

6、树

6.1 树的基本介绍

为什么需要数这种数据结构?

  1. 数组存储方式的分析:
    • 优点:通过下标方式访问元素,速度快。对于有序数组,还可以使用二分查找提高检索速度
    • 缺点:想要在有序数组中插入 / 删除一个数据项,就必须先找到插入数据项的位置,然后将所有插入位置后面的数据项全部向后移动一位,来给新数据腾出空间,平均来讲要移动 N/2 次
  2. 链式存储方式的分析:
    • 优点:在一定程度上对数组存储方式有优化,只需要改变一些引用值就行了,
    • 缺点:在检索时,效率很低。比如,检索某个值需要从头节点开始遍历

我们就希望一种数据结构能同时具备数组查找快的优点以及链表插入和删除快的优点,于是诞生了。

image-20220531223810023

  1. 路径:顺着节点的边从一个节点走到另一个节点,所经过的节点的顺序排列就称为“路径”
  2. :树顶端的节点称为根。一棵树只有一个根,如果要把一个节点和边的集合称为树,那么从根到其他任何一个节点都必须有且只有一条路径。A是根节点
  3. 父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;B是D的父节点
  4. 子节点:一个节点含有的子树的根节点称为该节点的子节点;D是B的子节点
  5. 兄弟节点:具有相同父节点的节点互称为兄弟节点;比如上图的D和E就互称为兄弟节点
  6. 叶节点:没有子节点的节点称为叶节点,也叫叶子节点,比如上图的H、E、F、G都是叶子节点
  7. 子树:每个节点都可以作为子树的根,它和它所有的子节点、子节点的子节点等都包含在子树中。
  8. 节点的层次:从根开始定义,根为第一层,根的子节点为第二层,以此类推
  9. 深度:对于任意节点 n,n 的深度为从根到 n 的唯一路径长,根的深度为0
  10. 高度:对于任意节点 n,n 的高度为从 n 到一片树叶的最长路径长,所有树叶的高度为0

6.2 二叉树

  1. 每个节点最多只能有两个子节点的一种形式称为二叉树

    image-20220531230523176

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

    image-20220531230556549

  3. 如果该二叉树的所以叶子节点都在最后一层或倒数第二层,而且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,称为完全二叉树

    image-20220531231018612

关于二叉树的一些基本操作

image-20220601190238567

看输出父节点的顺序,就可以确定是前序、中序还是后序遍历:

  1. 前序遍历:先输出父节点,再遍历左子树和右子树
  2. 中序遍历:先遍历左子树,再输出父节点,再遍历右子树
  3. 后续遍历:先遍历左子树,再遍历右子树,最后输出父节点

自定义二叉树类 BinaryTree:

public class BinaryTree {

    private Node node;

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

    // 前序遍历
    public void preOrder() {
        if (this.node != null) {
            this.node.preOrder();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (this.node != null) {
            this.node.infixOrder();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }

    // 后序遍历
    public void postOrder() {
        if (this.node != null) {
            this.node.postOrder();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }
}

二叉树中的节点类 Node:

public class Node {

    private int no;
    private String name;
    private Node leftNode;
    private Node rightNode;

    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        if (this.leftNode != null) {
            this.leftNode.preOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.preOrder();
        }
    }

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

    /**
     * 后序遍历
     */
    public void postOrder() {
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }

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

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

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

测试用例 main 方法:

public class MyTest {

    public static void main(String[] args) {
        //先需要创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建需要的结点
        Node root = new Node(1, "宋江");
        Node node2 = new Node(2, "吴用");
        Node node3 = new Node(3, "卢俊义");
        Node node4 = new Node(4, "林冲");
        Node node5 = new Node(5, "关胜");
        Node node6 = new Node(6, "PendulumYe");
        Node node7 = new Node(7, "???");
        //说明,先手动创建该二叉树,后面我们学习递归的方式创建二叉树
        root.setLeftNode(node2);
        root.setRightNode(node3);
        node2.setLeftNode(node4);
        node2.setRightNode(node5);
        node3.setLeftNode(node6);
        node3.setRightNode(node7);
        binaryTree.setRoot(root);

        System.out.println("前序遍历:"); // 1,2,4,5,3,6,7
        binaryTree.preOrder();

        System.out.println("\n中序遍历:");
        binaryTree.infixOrder(); // 4,2,5,1,6,3,7

        System.out.println("\n后序遍历:");
        binaryTree.postOrder(); // 4,5,2,6,7,3,1
    }
}

  1. 前序查找:
    • 先判断当前节点是否为空,若不为空判断当前节点的 no 是否等于要查找的
    • 如果相等,则返回当前节点
    • 如果不等,则判断当前节点的左子节点是否为空,如果不为空,则递归前序查找
    • 如果左递归前序查找,找到节点,则返回,否则继续判断,当前节点的右子节点是否为空,如果不空,则继续向右递归前序查找
  2. 中序查找:
    • 判断当前节点是否为空,不为空;则判断当前节点的左子节点是否为空,左子节点不为空则中序递归遍历查找
    • 若找到了要查找的节点,则返回;若没找到,则判断当前节点,若找到了节点,则返回
    • 若不是,则判断当前节点的右子节点是否为空,右子节点不为空则中序递归遍历查找,若找到了节点,则返回,否则返回 null
  3. 后序查找:
    • 判断当前节点是否为空,不为空,则判断当前节点的左子节点是否为空,左子节点不为空则后序递归遍历查找,若找到了要查找的节点,则返回
    • 如果没找到,则判断当前节点的右子节点是否为空,右子节点不为空则后序递归遍历查找,若找到了节点,则返回
    • 若没找到,则与当前节点比较,如果是则返回,否则返回 null

自定义二叉树类 BinaryTree:

public class BinaryTree {

    /**
     * 前序遍历查询
     *
     * @param node 根节点
     * @param no   排名
     * @return
     */
    public static TreeNode preOrderTraversalSearch(TreeNode node, int no) {
        //判断当前节点是不是为空,若不为空
        if (node != null) {
            //则判断需要查询的排名,与当前节点的排名是否相等
            if (node.no == no) {
                return node;
            }
        }
        TreeNode resultNode = null;
        //向左遍历,如果左子节点不为空
        if (node.leftNode != null) {
            resultNode = preOrderTraversalSearch(node.leftNode, no);
            if (resultNode != null) {
                return resultNode;
            }
        }
        //向右遍历,如果左子节点不为空
        if (node.rightNode != null) {
            resultNode = preOrderTraversalSearch(node.rightNode, no);
            if (resultNode != null) {
                return resultNode;
            }
        }
        return resultNode;
    }

    /**
     * 中序遍历查询
     *
     * @param node 根节点
     * @param no   排名
     * @return
     */
    public static TreeNode inOrderTraversalSearch(TreeNode node, int no){
        if (node == null){
            return null;
        }
        TreeNode treeNode = null;
        if (node.leftNode != null){
            treeNode = inOrderTraversalSearch(node.leftNode,no);
            if (treeNode != null){
                return treeNode;
            }
        }
        if (node.no == no){
            return node;
        }
        if (node.rightNode != null){
            treeNode = inOrderTraversalSearch(node.rightNode,no);
            if (treeNode != null){
                return treeNode;
            }
        }

        return treeNode;
    }

    /**
     * 后序遍历查询
     *
     * @param node 根节点
     * @param no   排名
     * @return
     */
    public TreeNode postOrderTraversalSearch(TreeNode node, int no){
        if (node == null){
            return null;
        }
        TreeNode treeNode = null;
        if (node.leftNode != null){
            treeNode = postOrderTraversalSearch(node.leftNode,no);
            if (treeNode != null){
                return treeNode;
            }
        }
        if (node.rightNode != null){
            treeNode = postOrderTraversalSearch(node.rightNode,no);
            if (treeNode != null){
                return treeNode;
            }
        }
        if (node.no == no){
            return node;
        }
        return treeNode;
    }
}

二叉树中的节点类 TreeNode:

public class TreeNode {

    public int no;//排名
    public String name;//姓名
    public TreeNode leftNode;//左节点
    public TreeNode rightNode;

    public TreeNode(int no,String name){
        this.no = no;
        this.name = name;
    }

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

测试用例 main 方法:

public class MyTest {

    public static void main(String[] args) {

        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = new TreeNode(1, "宋江");
        TreeNode node2 = new TreeNode(2, "卢俊义");
        TreeNode node3 = new TreeNode(3, "吴用");
        TreeNode node4 = new TreeNode(4, "公孙胜");
        TreeNode node5 = new TreeNode(5, "关胜");
        TreeNode node6 = new TreeNode(6, "林冲");
        root.leftNode = node3;
        root.rightNode = node2;
        node2.rightNode = node4;
        node2.leftNode = node5;
        node3.rightNode = node6;

        TreeNode result1 = binaryTree.preOrderTraversalSearch(root, 5);
        System.out.println("前序查找获取到的节点: " + result1);

        TreeNode result2 = binaryTree.inOrderTraversalSearch(root, 5);
        System.out.println("中序查找获取到的节点: " + result2);

        TreeNode result3 = binaryTree.postOrderTraversalSearch(root, 5);
        System.out.println("后序查找获取到的节点: " + result3);
    }
}

  1. 判断根节点是否为空,若为空则插入的节点即为跟节点
  2. 若不为空,判断是否小于父节点,若小于,则插入到父节点左边;若大于,则插入父节点右边

自定义二叉树类 BinaryTree:

public class BinaryTree {

    /**
     * 插入一个节点
     * @param root
     * @param insertNode
     * @return
     */
    public TreeNode insert(TreeNode root, TreeNode insertNode) {
        // 树为空
        if (root == null) {
            root = insertNode;
            root.parentNode = null;
            return root;
        }

        TreeNode temp = root;
        // 树不为空,查找插入节点
        while (root != null) {
            // 插入到右侧
            if (temp.no < insertNode.no) {
                if (temp.rightNode != null) {
                    temp = temp.rightNode;
                } else {
                    temp.rightNode = new TreeNode();
                    temp.rightNode = insertNode;
                    temp.rightNode.parentNode = temp;
                    break;
                }
            }
            // 插入到左侧
            if (temp.no > insertNode.no) {
                if (temp.leftNode != null) {
                    temp = temp.leftNode;
                } else {
                    temp.leftNode = new TreeNode();
                    temp.leftNode = insertNode;
                    temp.leftNode.parentNode = temp;
                    break;
                }
            }
        }
        return root;
    }

    /**
     * 前序遍历
     */
    public void preOrder(TreeNode root) {
        System.out.println(root);
        if (root.leftNode != null) {
            preOrder(root.leftNode);
        }
        if (root.rightNode != null) {
            preOrder(root.rightNode);
        }
    }
}

二叉树中的节点类 TreeNode:

public class TreeNode {

    public int no;//排名
    public String name;//姓名
    public TreeNode parentNode;
    public TreeNode leftNode;//左节点
    public TreeNode rightNode;

    public TreeNode() {
    }

    public TreeNode(int no, String name){
        this.no = no;
        this.name = name;
    }

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

测试用例 main 方法:

public class MyTest {

    public static void main(String[] args) {

        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = new TreeNode(1, "宋江");
        TreeNode node2 = new TreeNode(2, "卢俊义");
        TreeNode node3 = new TreeNode(3, "吴用");
        TreeNode node4 = new TreeNode(4, "公孙胜");
        TreeNode node5 = new TreeNode(5, "关胜");
        TreeNode node6 = new TreeNode(6, "林冲");
        root.leftNode = node3;
        root.rightNode = node2;
        node2.rightNode = node4;
        node2.leftNode = node5;
        node3.rightNode = node6;

        binaryTree.insert(root, new TreeNode(7, "PendulumYe"));
        binaryTree.preOrder(root);
    }
}

6.3 顺序存储二叉树

二叉树的顺序存储结构是用一维数组存储二叉树中的结点,并用结点的存储位置表示结点间的逻辑关系(父子关系)

image-20220601163624448

顺序存储二叉树的特点:

  1. 顺序存储二叉树通常只考虑完全二叉树
  2. 第 n 个元素的左子节点为 2 * n + 1
  3. 第 n 个元素的右子节点为 2 * n + 2
  4. 第 n 个元素的左子节点为 (n-1 / 2)
  5. n:表示二叉树中的第 n 个元素(从0开始)

下面给出一个实例:一个数组 {1, 2, 3, 4, 5, 6, 7},要求以二叉树前序、中序、后序遍历的方式进行遍历。代码示例如下:

public class ArrBinaryTreeDemo {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        //创建一个 ArrBinaryTree
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        System.out.println("前序遍历:");
        arrBinaryTree.preOrder(0); // 1,2,4,5,3,6,7
        System.out.println("\n中序遍历:");
        arrBinaryTree.midOrder(0);// 4,2,5,1,6,3,7
        System.out.println("\n后序遍历:");
        arrBinaryTree.postOrder(0);// 4,5,2,6,7,3,1
    }
}

/**
 * 编写一个 ArrBinaryTree,实现顺序存储二叉树遍历
 */
class ArrBinaryTree {

    // 存储数据节点的数组
    private int[] arr;

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

    /**
     * 编写一个方法,完成顺序存储二叉树的前序遍历
     *
     * @param index 数组的下标
     */
    public void preOrder(int index) {
        // 如果数组为空,或者 arr.length = 0
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空,不能按照二叉树的前序遍历");
        }
        // 输出当前这个元素
        System.out.print(arr[index] + " ");
        // 向左递归遍历
        if ((index * 2 + 1) < arr.length) {
            preOrder(2 * index + 1);
        }
        // 向右递归遍历
        if ((index * 2 + 2) < arr.length) {
            preOrder(2 * index + 2);
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder(int index) {
        // 如果数组为空,或者 arr.length = 0
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空,不能按照二叉树的前序遍历");
        }
        if ((index * 2 + 1) < arr.length) {
            midOrder(index * 2 + 1);
        }

        System.out.print(arr[index] + " ");

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

    /**
     * 后序遍历
     */
    public void postOrder(int index) {
        // 如果数组为空,或者 arr.length = 0
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空,不能按照二叉树的前序遍历");
        }

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

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

        System.out.print(arr[index] + " ");
    }
}

6.4 线索化二叉树

在顺序存储二叉树的基础上出现这么一个问题:将数列 {1, 3, 6, 8, 10, 14},构建成一颗二叉树

image-20220601171821911

这个时候当对二叉树进行中序遍历的时候,数列为 {8, 3, 10, 1, 14, 6},而其中 6、8、10、14的左 / 右指针并没有充分利用上。为了充分的利用各个节点的左右指针,让各个节点可以指向自己的前后节点,因此出现了线索化二叉树:

  1. n个节点的二叉链表中含有 n + 1(公式:2n-(n-1))个空指针域。利用二叉表中空指针域,存放指向该结点在某种遍历次序下的前驱与后续节点的指针称为线索
  2. 这种加上了线索的二叉链表称为线索链表,相应的二叉树也称为线索二叉树,根据性质不同分别有前序、中序、后序等线索二叉树
  3. 一个结点的前一个节点,称为前驱节点
  4. 一个结点的后一个节点,称为后续节点

通过示例认识线索化二叉树

image-20220601172338528

  1. 中序遍历结果:{8, 3, 10, 1, 14, 6} 进行线索化,该怎么操作?
  2. 我们发现【节点八】的前驱节点为 Null,后继节点为【节点三】,要关联
  3. 而【节点三】的前驱节点为【节点八】,后继节点为【节点十】,但【节点三】已指向两子节点,则无需关联
  4. 而【节点十】的前驱节点为【节点三】,要关联,后继节点为【节点一】,要关联
  5. 而【节点一】的前驱节点为【节点十】,后继节点为【节点十四】,但【节点一】已指向两子节点,则无需关联
  6. 而【节点十四】的前驱节点为【节点一】,要关联,后继节点【节点六】,要关联
  7. 而【节点六】的前驱节点为【节点十四】,后继节点为 Null,则无需关联

线索化成功的二叉树是下面这样的:

image-20220601172921128

当线索化二叉树后,Node 节点的属性 left、right 会有以下情况:

  • left 指向的是左子树,也可能是指向的前驱节点,比如【节点一】的 left 指向的左子树,而【节点十】的 left 指向的就是前驱节点
  • right 指向的是右子树,也可能是指向后继节点,比如【节点一】right 指向的是右子树,而【节点十】的 right 指向的是后继节点

因此我们需要多加一个标志 type 代表当前是指向子树、还是节点

线索化某个节点 node 时,需要一个前驱节点 pre 构成关系关联,这样才可能实现线索化,如图:

image-20220601190851610

以线索化【节点八】为例:

image-20220601215247849

处理完后,让当前 node 成为下一个节点的前驱节点:pre = node

再然后线索化后继节点:

image-20220601215533038

下面给出一个完整的中序线索化二叉树代码实现:

自定义二叉树类 ThreadedBinaryTree:

public class ThreadedBinaryTree {

    private Node root;

    //为了实现线索化,需要创建要给指向当前结点的前驱结点的指针
    //在递归进行线索化时,pre 总是保留前一个结点
    private Node pre = null;

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

    public void threadedNode() {
        this.threadedNode(root);
    }

    /**
     * 对二叉树进行中序线索化
     */
    public void threadedNode(Node node) {
        if (node == null) {
            return;
        }

        // 先线索化左子树
        threadedNode(node.left);

        // 线索化当前节点
        if (node.left == null) {
            // 让当前节点的左指针指向前驱结点
            node.left = pre;
            // 修改当前节点的左指针的类型
            node.leftType = 1;
        }

        // 处理后继节点
        if (pre != null && pre.right == null) {
            //让前驱结点的右指针指向当前结点
            pre.right = node;
            //修改前驱结点的右指针类型
            pre.rightType = 1;
        }

        // 每处理完一个节点后,让当前节点是下一个节点的前驱节点
        pre = node;

        // 再线索化右子树
        threadedNode(node.right);
    }

    /**
     * 线索化中序遍历二叉树的方法
     */
    public void threadedList() {
        // 定义一个变量,存储当前遍历的结点,从root开始
        Node node = root;

        while (node != null) {
            // 循环的找到 leftType == 1 的结点,第一个找到就是8结点
            // 后面随着遍历而变化,因为当 leftType == 1 时,说明该结点是按照线索化处理后的有效结点
            while (node.leftType == 0) {
                node = node.left;
            }
            //打印当前这个结点
            System.out.println(node);
            //如果当前结点的右指针指向的是后继结点,就一直输出
            while (node.rightType == 1) {
                //获取到当前结点的后继结点
                node = node.right;
                System.out.println(node);
            }
            //替换这个遍历的结点
            node = node.right;
        }
    }
}

二叉树中的节点类 Node::

public class Node {

    public int no;
    public Node left;
    public Node right;
    public int leftType; // 0 表示指向的是左子树;1 表示指向的是前驱节点
    public int rightType; // 0 表示指向的是右子树;1 表示指向的是后驱节点

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

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

测试用例 main 方法:

public class MyTest {

    public static void main(String[] args) {
        // 测试一把中序线索二叉树的功能
        Node root = new Node(1) ;
        Node node2 = new Node(3);
        Node node3 = new Node(6);
        Node node4 = new Node(8);
        Node node5 = new Node(10);
        Node node6 = new Node(14);

        // 手动创建二叉树
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;

        // 测试中序线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNode();

        // 测试: 以10号节点测试
        Node leftNode = node5.left;
        Node rightNode = node5.right;
        System.out.println("10号结点的前驱结点是 ="  + leftNode); // 3
        System.out.println("10号结点的后继结点是="  + rightNode); // 1

        // 当线索化二叉树后,能在使用原来的遍历方法
        System.out.println("使用线索化的方式遍历 线索化二叉树");
        threadedBinaryTree.threadedList(); // 8, 3, 10, 1, 14, 6
    }
}

6.5 赫夫曼树

赫夫曼树相关的几个名词概念:

  1. 路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径
  2. 路径长度:在一条路径中,每经过一个结点,路径长度都要加 1
  3. 结点的权:将树中节点赋给一个有某种含义的数值,这个数值就成为该节点的权
  4. 结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积
  5. 树的带权路径长度:所有叶子结点的带权路径长度之和,记作 “WPL”

赫夫曼树

当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,有时也叫“赫夫曼树”或者“哈夫曼树

需要注意的是:同样叶子节点所构成的哈夫曼树可能不止一棵,下面这几棵树全都是哈夫曼树:

image-20220602130912940

在构建哈弗曼树时,要使树的带权路径长度最小,只需要遵循一个原则,那就是:权重越大的结点离树根越近

  1. 在 n 个权值中选出两个最小的权值,对应的两个结点组成一个新的二叉树,且新二叉树的根结点的权值为左右孩子权值的和
  2. 在原有的 n 个权值中删除那两个最小的权值,同时将新的权值加入到 n–2 个权值的行列中,以此类推
  3. 重复 1 和 2 ,直到所以的结点构建成了一棵二叉树为止,这棵树就是哈夫曼树

赫夫曼树中节点类 Node:

public class Node implements Comparable<Node>{

    public int value;  // 节点权值
    public Node leftNode;
    public Node rightNode;

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

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

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

赫夫曼树 HuffmanTree:

public class HuffmanTree {

    /**
     * 前序遍历
     */
    public static void preOrder(Node root) {
        if(root != null) {
            System.out.println(root);
            if (root.leftNode != null) {
                preOrder(root.leftNode);
            }
            if (root.rightNode != null) {
                preOrder(root.rightNode);
            }
        }
    }

    /**
     * 创建赫夫曼树
     */
    public static Node createHuffmanTree(int[] arr) {
        // 遍历数组,将数组中的每个元素构成 Node 节点放入集合中
        List<Node> nodeList = new ArrayList<>();
        for (int value : arr) {
            nodeList.add(new Node(value));
        }

        while (nodeList.size() > 1) {
            // 将集合中的 Node 节点排序
            Collections.sort(nodeList);

            // 取出集合中权值最小的两棵二叉树
            Node leftNode = nodeList.get(0);
            Node rightNode = nodeList.get(1);

            // 构建成一棵真的二叉树
            Node parentNode = new Node(leftNode.value + rightNode.value);
            parentNode.leftNode = leftNode;
            parentNode.rightNode = rightNode;

            // 将原本的两个老的二叉树从集合中删除
            nodeList.remove(leftNode);
            nodeList.remove(rightNode);

            //将新树放入集合中
            nodeList.add(parentNode);
        }
        return nodeList.get(0);
    }
}

public class MyTest {

    public static void main(String[] args) {
        int arr[] = { 13, 7, 8, 3, 29, 6, 1 };
        Node root = HuffmanTree.createHuffmanTree(arr);
        HuffmanTree.preOrder(root);
    }
}

6.5.1 赫夫曼编码

哈夫曼编码

哈夫曼编码是一种高效的编码方式,在信息存储和传输过程中,用于对信息的压缩,是一种不定长编码,这种编码方式实现了两个重要目标:

  1. 任何一个字符编码,都不是其他字符编码的前缀
  2. 信息编码的总长度最小

  1. 定长编码

    image-20220605213757631

  2. 变长编码

    image-20220606024706179

  3. 赫夫曼编码

    和前面的例子相似,字符出现的次数作为权值,构建一颗赫夫曼树

image-20220605191613148

赫夫曼树节点类:

public class Node implements Comparable<Node> {

    public Byte data;
    public int weight;
    public Node leftNode;
    public Node rightNode;

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

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }

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

    /**
     * 前序遍历
     */
    public void preSelect() {
        System.out.println(this);
        if (this.leftNode != null) {
            this.leftNode.preSelect();
        }
        if (this.rightNode != null) {
            this.rightNode.preSelect();
        }
    }
}

构建赫夫曼编码类:

public class HuffmanCode {

    /*
    生成赫夫曼树对应的赫夫曼编码:
    1. 将赫夫曼编码表存放在 Map<Byte,String> 形式
        生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
    2. 在生成赫夫曼编码表示,需要去拼接路径, 定义一个StringBuilder 存储某个叶子结点的路径
     */
    private static Map<Byte, String> huffmanCodes = new HashMap<>();
    private static StringBuilder stringBuilder = new StringBuilder();

    /**
     * 把字符串 byte 数组转为 List 集合
     *
     * @param byteList
     * @return 返回的就是 List 形式   [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......]
     */
    public static List<Node> getNodes(byte[] byteList) {
        // 创建一个集合
        List<Node> nodeList = new ArrayList<>();
        // 遍历传入的数组,统计每一个元素出现的次数
        Map<Byte, Integer> countMap = new HashMap<>();
        for (byte b : byteList) {
            Integer count = countMap.get(b);
            if (count == null) {
                countMap.put(b, 1);
            } else {
                countMap.put(b, count + 1);
            }
        }
        for (Map.Entry<Byte, Integer> entry : countMap.entrySet()) {
            nodeList.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodeList;
    }

    /**
     * 创建赫夫曼树方法
     *
     * @return
     */
    public static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //从小到大进行排序
            Collections.sort(nodes);
            System.out.println("集合中数据:" + nodes);
            //取出来根结点权值最小的两棵二叉树
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //构建一课新的二叉树
            Node root = new Node(null, leftNode.weight + rightNode.weight);
            root.leftNode = leftNode;
            root.rightNode = rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将root加入到nodes集合中
            nodes.add(root);
        }
        return nodes.get(0);
    }

    /**
     * 功能:将传入的 node 结点的所有叶子结点的赫夫曼编码得到,并放入到 huffmanCodes 集合
     *
     * @param node          传入结点
     * @param code          路径: 左子结点是 0, 右子结点 1
     * @param stringBuilder 用于拼接路径
     */
    private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        //将code 加入到 stringBuilder2
        stringBuilder2.append(code);
        if (node != null) { // 如果node == null不处理
            // 判断当前node 是叶子结点还是非叶子结点
            if (node.data == null) { // 非叶子结点
                // 向左递归
                getCodes(node.leftNode, "0", stringBuilder2);
                // 向右递归
                getCodes(node.rightNode, "1", stringBuilder2);
            } else { // 说明是一个叶子结点
                // 就表示找到某个叶子结点的最后
                huffmanCodes.put(node.data, stringBuilder2.toString());
            }
        }
    }

    public static Map<Byte, String> getCodes(Node root) {
        if (root == null) {
            return null;
        }
        //处理root的左子树
        getCodes(root.leftNode, "0", stringBuilder);
        //处理root的右子树
        getCodes(root.rightNode, "1", stringBuilder);
        return huffmanCodes;
    }

    //---------------------------------------------《数据压缩》------------------------------------------

    /**
     * 数据压缩
     *
     * @param bytes        原始的字符串对应的 byte[]
     * @param huffmanCodes 原始字符串对应 byte 数组转换成的赫夫曼编码
     * @return 返回赫夫曼编码处理后的 byte[]
     *
     * 举例: String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
     * 返回的是 字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
     * => 对应的 byte[] huffmanCodeBytes  ,即 8位对应一个 byte,放入到 huffmanCodeBytes
     * huffmanCodeBytes[0] =  10101000(补码) => byte  [推导  10101000=> 10101000 - 1 => 10100111(反码)=> 11011000= -88 ]
     * huffmanCodeBytes[1] = -88
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        // 将 byte 转换成赫夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }

        int length;
        if (stringBuilder.length() % 8 == 0) {
            length = stringBuilder.length() / 8;
        } else {
            length = stringBuilder.length() / 8 + 1;
        }
        // 创建存储压缩后的 byte 数组
        byte[] huffmanCodeBytes = new byte[length];
        int index = 0; //记录是第几个 byte
        for (int i = 0; i < stringBuilder.length(); i += 8) { // 因为是每8位对应一个byte,所以步长 +8
            String strByte;
            if (i + 8 > stringBuilder.length()) { //不够8位
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }
            // 将strByte 转成一个byte,放入到 huffmanCodeBytes
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }

    //---------------------------------------------《数据解压》------------------------------------------

    /**
     * 将一个 byte 转成一个二进制的字符串
     *
     * @param b    传入的 byte
     * @param flag 标志是否需要补高位如果是 true ,表示需要补高位,如果是 false 表示不补, 如果是最后一个字节,无需补高位
     * @return 是 b 对应的二进制的字符串,(注意是按补码返回)
     */
    private static String byteToBitString(boolean flag, byte b) {
        // 使用变量保存 b
        int temp = b; // 将 b 转成 int
        // 如果是正数我们还存在补高位
        if (flag) {
            temp |= 256; // 按位与 256  1 0000 0000  | 0000 0001 => 1 0000 0001
        }
        String str = Integer.toBinaryString(temp); // 返回的是temp对应的二进制的补码
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }

    /**
     * 数据解压
     *
     * @param huffmanCodes 赫夫曼编码表 map
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return 就是原来的字符串对应的数组
     */
    public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        // 1. 先得到 huffmanBytes 对应的二进制的字符串,形式 1010100010111...
        StringBuilder stringBuilder = new StringBuilder();
        // 将 byte 数组转成二进制的字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            // 判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, b));
        }
        // 把字符串安装指定的赫夫曼编码进行解码
        // 把赫夫曼编码表进行调换,因为反向查询 a->100 100->a
        Map<String, Byte> map = new HashMap<String, Byte>();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }

        // 创建要给集合,存放 byte
        List<Byte> list = new ArrayList<>();
        // i 可以理解成就是索引,扫描 stringBuilder
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1; // 小的计数器
            boolean flag = true;
            Byte b = null;
            while (flag) {
                // 1010100010111...
                // 递增的取出 key 1
                String key = stringBuilder.substring(i, i + count);// i 不动,让count移动,指定匹配到一个字符
                b = map.get(key);
                if (b == null) { // 说明没有匹配到
                    count++;
                } else {
                    // 匹配到
                    flag = false;
                }
            }
            list.add(b);
            i += count; // i 直接移动到 count
        }
        // 当for循环结束后,我们list中就存放了所有的字符  "i like like like java do you like a java"
        // 把list 中的数据放入到byte[] 并返回
        byte b[] = new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            b[i] = list.get(i);
        }
        return b;
    }

    //---------------------------------------------《文件压缩》------------------------------------------

    /**
     * @param bytes 原始的字符串对应的字节数组
     * @return 经过赫夫曼编码处理后的字节数组(压缩后的数组)
     */
    private static byte[] huffmanZip(byte[] bytes) {
        List<Node> nodes = getNodes(bytes);
        // 根据 nodes 创建的赫夫曼树
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        // 对应的赫夫曼编码(根据 赫夫曼树)
        Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
        // 根据生成的赫夫曼编码,压缩得到压缩后的赫夫曼编码字节数组
        byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
        return huffmanCodeBytes;
    }

    /**
     * 文件压缩
     *
     * @param srcFile 你传入的希望压缩的文件的全路径
     * @param dstFile 我们压缩后将压缩文件放到哪个目录
     */
    public static void zipFile(String srcFile, String dstFile) {
        // 创建输出流
        OutputStream os = null;
        ObjectOutputStream oos = null;
        // 创建文件的输入流
        FileInputStream is = null;
        try {
            //创建文件的输入流
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一样的byte[]
            byte[] b = new byte[is.available()];
            //读取文件
            is.read(b);
            //直接对源文件压缩
            byte[] huffmanBytes = huffmanZip(b);
            //创建文件的输出流, 存放压缩文件
            os = new FileOutputStream(dstFile);
            //创建一个和文件输出流关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            //把 赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanBytes); //我们是把
            //这里我们以对象流的方式写入 赫夫曼编码,是为了以后我们恢复源文件时使用
            //注意一定要把赫夫曼编码 写入压缩文件
            oos.writeObject(huffmanCodes);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            try {
                is.close();
                oos.close();
                os.close();
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
        }
    }

    //---------------------------------------------《文件解压》------------------------------------------

    /**
     * 文件解压
     *
     * @param zipFile 准备解压的文件
     * @param dstFile 将文件解压到哪个路径
     */
    public static void unZipFile(String zipFile, String dstFile) {
        //定义文件输入流
        InputStream is = null;
        //定义一个对象输入流
        ObjectInputStream ois = null;
        //定义文件的输出流
        OutputStream os = null;
        try {
            //创建文件输入流
            is = new FileInputStream(zipFile);
            //创建一个和  is关联的对象输入流
            ois = new ObjectInputStream(is);
            //读取byte数组  huffmanBytes
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();

            //解码
            byte[] bytes = decode(huffmanCodes, huffmanBytes);
            //将bytes 数组写入到目标文件
            os = new FileOutputStream(dstFile);
            //写数据到 dstFile 文件
            os.write(bytes);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (Exception e2) {
                System.out.println(e2.getMessage());
            }
        }
    }
}

测试方法:

public class MyTest {

    public static void main(String[] args) {
        String string ="I'm PendulumYe. What's your name";
        byte[] bytes = string.getBytes();
        System.out.println("bytes数组:"+Arrays.toString(bytes));
        System.out.println("字节数组长度:"+bytes.length);

        List<Node> nodes = HuffmanCode.getNodes(bytes);
        System.out.println("创建node集合:"+nodes);

        //创建赫夫曼树
        Node huffmanTree = HuffmanCode.createHuffmanTree(nodes);
        huffmanTree.preSelect();

        //生成赫夫曼编码
        Map<Byte, String> codes =HuffmanCode.getCodes(huffmanTree);
        System.out.println("生成赫夫曼编码:"+codes);

        //压缩测试
        byte[] zip = HuffmanCode.zip(bytes, codes);
        System.out.println("压缩后的数据:"+Arrays.toString(zip));

        //解压测试
        byte[] decode = HuffmanCode.decode(codes, zip);
        System.out.println("解压后的数据:" + Arrays.toString(decode));
    }
}

6.6 二叉排序树

二叉排序树也叫二叉搜索树,有以下特点:

  1. 二叉搜索树的左节点永远<父节点
  2. 二叉搜索树的右节点用于 > 父节点
  3. 它的左右子树也分别为二叉搜索树

关于二叉排序树的创建与删除

自定义二叉排序树类 BinaryTree:

public class BinarySortTree {

    private Node root;

    /**
     * 添加节点的方法
     */
    public void add(Node node) {
        if (root == null) {
            root = node; // 如果 root 为空,直接让 root 指向 node
        } else {
            root.add(node);
        }
    }

    /**
     * 中序遍历的方法
     */
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("当前二叉树为空,无法遍历");
        }
    }

}

二叉树中的节点类 Node:

public class Node {

    public int value;
    public Node left;
    public Node right;

    /**
     * 以递归的形式添加节点
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //判断传入的结点的值,和当前子树的根结点的值关系
        if (node.value < this.value) {
            //如果当前结点左子结点为null
            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();
        }
    }

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

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

测试用例 main 方法:

public class MyTest {

    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();
        // 循环的添加结点到二叉排序树
        for(int i = 0; i< arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }
        System.out.println("当前树的形状:\n" +
                "\t\t\t7\n" + "\t\t/" + "\t\t" + "\\" + "\n" +
                "\t3\t\t\t\t10\n" + "\t/" + "\t\t\t\t" + "\\" + "\n" +
                "1\t\t5\t\t9\t\t12\n" + "\t" + "\\" + "\n" +
                "\t2");

        // 中序遍历二叉排序树
        System.out.println("中序遍历二叉排序树:");
        binarySortTree.infixOrder(); // 1, 2, 3, 5, 7, 9, 10, 12
    }
}

image-20220601155958728

如果想从 BST(二叉排序树)中删除一个节点,基本有三种情况:

  1. 删除的节点是叶子节点

    例如,如果我们想从上面的 BST 示例中删除 19,我们可以通过删除节点并使其父节点指向 NULL(切断链接并清除内存)来简单地清除链接并回收内存。删除此节点后,BST 仍然有效。属性仍然保留。

  2. 删除的节点只有一个子树

    很明显,我们不能只删除 / 删除不是叶节点的节点。因为我们也会放弃它的子树。要删除只有 1 个子节点的节点,我们可以将其父节点链接到其唯一的子节点。

    比如我们想删除上面 BST 中的 7,可以把 5 链接到它唯一的子节点 9,去掉节点7 。也就是说,要删除的节点的子树会被重新附加并且 BST 的属性仍然有效。

  3. 删除的节点有两个子树

    image-20220601160209150

    如果我们想从上面的 BST 中删除 15,我们可以做一些技巧来将情况减少到情况 1 或情况 2:

    • 求其右子树的最小值

      如果我们找到它的右子树的最小值,它不应该是有两个子节点的节点,否则节点的左子节点会小于 1。给定上面的 BST,15 的子树的最小值将是 17。

      然后我们将要删除的值替换为 17,我们就得到了两个 17。所以接下来的任务是从原来的 15 的右子树中删除 17。所以这是删除只有 1 个子节点的节点的情况。

      为什么这有效?因为17在15的右子树上,所以它应该大于15,也大于15的左子树中的任何其他节点。17 也是 15 的右子树中的最小值,所以 17 小于或等于 15 的任何右子树。当然,在用值 17 替换 15 后,我们有一个重复的 17。

    • 求其左子树的最大值

      类似地,我们可以找到待删除节点的左子树的最大值,方法类似。另一个要注意的是,如果找到的值(最大值或最小值)没有子节点,那么我们将这种情况简化为从 BST 树中删除叶节点的情况 1

自定义二叉排序树类 BinaryTree:

public class BinarySortTree {

    private static Node root;

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

    /**
     * 查找要删除的节点
     */
    public static Node search(int no) {
        if (root == null) {
            return null;
        } else {
            return root.searchNode(no);
        }
    }

    /**
     * 查找要删除节点的父节点
     */
    public static Node searchParent(int no) {
        if (root == null) {
            return null;
        } else {
            return root.searchParentNode(no);
        }
    }

    /**
     * 删除以 node 为根节点的右子树中的最小节点
     * @param node 根节点
     * @return 返回的以 node为根结点的二叉排序树的最小结点的值
     */
    public static int delRightTreeMin(Node node) {
        Node target = node;
        // 循环的查找以 node 为根节点的左右子树中的最小节点
        while(target.left != null) {
            target = target.left;
        }
        // 这时 target 就指向了最小结点,删除最小结点
        delNode(target.no);
        return target.no;
    }

    /**
     * 删除节点
     * @param no 要删除节点的值
     */
    public static void delNode(int no) {
        if(root == null) {
            return;
        }else {
            // 先去找到要删除的结点 targetNode
            Node targetNode = search(no);
            if(targetNode == null) { // 如果没有找到要删除的结点,则直接返回
                return;
            }
            if(root.left == null && root.right == null) { // 如果我们发现当前这颗二叉排序树只有一个结点
                root = null;
                return;
            }

            // 再找到删除节点 targetNode 的父结点
            Node parent = searchParent(no);
            // 如果要删除的结点是叶子结点
            if(targetNode.left == null && targetNode.right == null) {
                //判断 targetNode 是父结点的左子结点,还是右子结点
                if(parent.left != null && parent.left.no == no) { // 是左子结点
                    parent.left = null;
                } else if (parent.right != null && parent.right.no == no) { // 是由子结点
                    parent.right = null;
                }

            } else if ((targetNode.left != null && targetNode.right == null) || (targetNode.left == null && targetNode.right != null)) { // 删除只有一颗子树的结点
                // 如果要删除的结点有左子结点
                if(targetNode.left != null) {
                    if(parent != null) {
                        // 如果 targetNode 是 parent 的左子结点
                        if(parent.left.no == no) {
                            parent.left = targetNode.left;
                        } else { //  targetNode 是 parent 的右子结点
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else { // 如果要删除的结点有右子结点
                    if(parent != null) {
                        // 如果 targetNode 是 parent 的左子结点
                        if(parent.left.no == no) {
                            parent.left = targetNode.right;
                        } else { // 如果 targetNode 是 parent 的右子结点
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }

            } else { // 删除有两颗子树的节点
                int minVal = delRightTreeMin(targetNode.right); // 求出右子树中节点最小的值
                targetNode.no = minVal;
            }
        }
    }

    /**
     * 中序遍历
     */
    public static void infixOrder() {
        if (root == null) {
            return;
        } else {
            root.infixOrder();
        }
    }
}

二叉树中的节点类 Node:

public class Node{

    public int no;
    public Node left;
    public Node right;

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

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

    /**
     * 查找要删除的节点
     * @param no 要删除的节点值
     * @return 如果存在该节点则返回,否则返回 null
     */
    public Node searchNode(int no) {
        if (no == this.no) {
            return this;
        } else if (no < this.no) { // 如果查找的值小于当前结点,向左子树递归查找
            if (this.left == null) {
                return null;
            }
            return this.left.searchNode(no);
        } else { // 如果查找的值不小于当前结点,向右子树递归查找
            if (this.right == null) {
                return null;
            }
            return this.right.searchNode(no);
        }
    }

    /**
     * 查找要删除节点的父节点
     * @param no 要删除节点的值
     * @return 如果存在该节点则返回,否则返回 null
     */
    public Node searchParentNode(int no) {
        // 如果当前节点就是要删除的节点的父节点,则直接返回
        if ((this.left != null && this.left.no == no) || (this.right != null && this.right.no == no)) {
            return this;
        } else {
            // 如果要查找的值小于当前节点的值,并且当前节点的左子节点不为空
            if (no < this.no && this.left != null) {
                return this.left.searchParentNode(no); // 向左子树递归查找
            } else if (no > this.no && this.right != null) {
                return this.right.searchParentNode(no); // 向右子树递归查找
            } else {
                return null;
            }
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder(){
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.print(this.no + " -> ");
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}

测试用例 main 方法:

public class MyTest {

    public static void main(String[] args) {
        Node root = new Node(7);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node5 = new Node(5);
        Node node3 = new Node(3);
        Node node10 = new Node(10);
        Node node12 = new Node(12);
        Node node9 = new Node(9);

        root.left = node3;
        root.right = node10;
        node3.left = node1;
        node3.right = node5;
        node10.left = node9;
        node10.right = node12;
        node1.right = node2;
        BinarySortTree.setRoot(root);

        System.out.println("当前树的形状:\n" +
                "\t\t\t7\n" + "\t\t/" + "\t\t" + "\\" + "\n" +
                "\t3\t\t\t\t10\n" + "\t/ \\" + "\t\t\t\t" + "/ \\" + "\n" +
                "1\t\t5\t\t9\t\t12\n" + "\t" + "\\" + "\n" +
                "\t2");

        System.out.println("删除节点前(中序遍历):");
        BinarySortTree.infixOrder();

        BinarySortTree.delNode(12);
        System.out.println("\n删除叶子节点12后(中序遍历):");
        BinarySortTree.infixOrder();

        BinarySortTree.delNode(1);
        System.out.println("\n删除只有一个子树的非叶子节点1后(中序遍历):");
        BinarySortTree.infixOrder();

        BinarySortTree.delNode(3);
        System.out.println("\n删除有两个个子树的非叶子节点3后(中序遍历)——");
        BinarySortTree.infixOrder();
    }
}

6.7 平衡二叉树

若数据构成的二叉排序树只有左子树或者只有右子树,例如 {1, ,2, 3, 4, ,5, 6} 这种数据的时候,二叉树就会将一个链表一样,搜索效率低下,因此引出了平衡二叉树

相关概念

  • 判断平衡二叉树
    1. 是二叉排序树
    2. 任意节点的子树的高度差都小于等于 1
    3. 任何一个节点的左子树或者右子树都是平衡二叉树
  • 平衡因子
    1. 定义:左子树和右子树的高度差
    2. 别名:简称 BF
  • 最小不平衡子树
    1. 距离插入节点最近的,并且 BF 绝对值大于 1 的节点为根节点的子树
    2. 旋转只需要纠正最小不平衡子树即可

image-20220604115706123

平衡二叉树的插入过程的前半部分与二叉排序树相同,但在新结点插入后,若造成查找路径上的某个结点不再平衡,则需要做出相应的调整。可将调整的规律归纳为下列 3 种情况:

前提条件:右子树的高度减去左子树的高度大于1,即:rightHeight() - leftHeight() > 1

  1. 创建一个新的结点newNode,使其值等于当前根结点的值;
  2. 将新结点的左子树设置为当前结点的左子树:newNode.left = left
  3. 将新结点的右子树设置为当前结点的右子树的左子树:newNode.right = right.left
  4. 将当前结点的值换为右子结点的值:value = right.value
  5. 将当前结点的右子树设置成右子树的右子树:right = right.right
  6. 将当前结点的左子树设置成新结点:left = newNode

image-20220604122048098

private void leftRotate() {
    Node newNode =new Node(value); // 创建一个新的结点newNode
    newNode.left=left; // 将新结点的左子树设置为当前结点的左子树
    newNode.right=right.left; // 将新结点的右子树设置为当前结点的右子树的左子树
    value=right.value; // 将当前结点的值换为右子结点的值
    right=right.right; // 将当前结点的右子树设置成右子树的右子树
    left=newNode; // 将当前结点的左子树设置成新结点
}

前提条件:左子树的高度减去右子树的高度大于1,即:leftHeight() - rightHeight() > 1

  1. 创建一个新的结点newNode,使其值等于当前根结点的值
  2. 将新结点的右子树设置为当前结点的右子树:newNode.right = right
  3. 将新结点的左子树设置为当前结点的左子树的右子树:newNode.left = left.right
  4. 将当前结点的值换为左子结点的值:value = left.value
  5. 将当前结点的左子树设置成左子树的左子树:left = left.left
  6. 将当前结点的右子树设置成新结点:right = newNode

image-20220604122709548

private void rightRotate() {
    Node newNode =new Node(value); // 创建一个新的结点newNode
    newNode.right=right; // 将新结点的右子树设置为当前结点的右子树
    newNode.left=left.right; // 将新结点的左子树设置为当前结点的左子树的右子树
    value=left.value; // 将当前结点的值换为左子结点的值
    left=left.left; // 将当前结点的左子树设置成左子树的左子树
    right=newNode; // 将当前结点的右子树设置成新结点
}

  • LR平衡旋转(先左后右双旋转)

    1. 前提条件:符合 RR 平衡旋转(左单旋转)前提下,当前结点的左子树的右子树高度大于它的左子树的左子树的高度,即:left.rightHeight() > left.leftHeight()

    2. 先对当前结点的左结点进行左单旋转;再对当前结点进行右单旋转即可

      if(leftHeight()-rightHeight()>1) { // 当添加完一个结点后,如果 :(左子树的高度 - 右子树的高度) > 1, 右旋转
          if(left!=null&&left.rightHeight()>left.leftHeight()) { // 若它的左子树的右子树高度大于它的左子树的左子树的高度
              left.leftRotate(); // LR平衡旋转(先左后右双旋转)
              rightRotate();
          }else {
              rightRotate(); // LL平衡旋转(右单旋转)
          }
      }
  • RL平衡旋转(先右后左双旋转)

    1. 前提条件:符合 LL 平衡旋转(右单旋转)前提下,当前结点的右子树的左子树的高度大于它的右子树的右子树的高度,即: right.leftHeight() > right.rightHeight()

    2. 先对当前结点的右结点进行右单旋转;再对当前结点进行左单旋转即可

      if(rightHeight()-leftHeight()>1) { // 当添加完一个结点后,如果: (右子树的高度-左子树的高度) > 1 ,左旋转
          if(right!=null&&right.leftHeight()>right.rightHeight()) { // 若它的右子树的左子树的高度大于它的右子树的右子树的高度
              right.rightRotate(); // RL平衡旋转(先右后左双旋转)
              leftRotate();
          }else {
              leftRotate(); // RR平衡旋转(左单旋转)
          }
          return;
      }

平衡二叉树 AVLTree类:

public class AVLTree {

    private Node root;

    public Node getRoot() {
        return root;
    }

    // 添加结点的方法
    public void add(Node node) {
        if (root == null) {
            root = node;// 如果root为空则直接让root指向node
        } else {
            root.add(node);
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序树为空,不能遍历");
        }
    }
}

树节点 Node 类:

public class Node {

    public int value;
    public Node left;
    public Node right;

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

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

    /**
     * 以该节点为根节点的树的高度
     */
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

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

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

    /**
     * 左旋
     */
    private void leftRotate() {
        Node newNode =new Node(value); // 创建一个新的结点newNode
        newNode.left=left; // 将新结点的左子树设置为当前结点的左子树
        newNode.right=right.left; // 将新结点的右子树设置为当前结点的右子树的左子树
        value=right.value; // 将当前结点的值换为右子结点的值
        right=right.right; // 将当前结点的右子树设置成右子树的右子树
        left=newNode; // 将当前结点的左子树设置成新结点
    }


    /**
     * 右旋
     */
    private void rightRotate() {
        Node newNode =new Node(value); // 创建一个新的结点newNode
        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) {
            //如果当前结点左子结点为null
            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(rightHeight() - leftHeight() > 1) {
            // 如果它的右子树的左子树的高度大于它的右子树的右子树的高度
            if(right != null && right.leftHeight() > right.rightHeight()) {
                // 先对右子结点进行右旋转
                right.rightRotate();
                // 然后在对当前结点进行左旋转
                leftRotate(); //左旋转..
            } else {
                // 直接进行左旋转即可
                leftRotate();
            }
            return ; // 必须要!!!
        }

        // 当添加完一个结点后,如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
        if(leftHeight() - rightHeight() > 1) {
            // 如果它的左子树的右子树高度大于它的左子树的高度
            if(left != null && left.rightHeight() > left.leftHeight()) {
                // 先对当前结点的左结点(左子树)->左旋转
                left.leftRotate();
                // 再对当前结点进行右旋转
                rightRotate();
            } else {
                // 直接进行右旋转即可
                rightRotate();
            }
        }
    }

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

测试类:

public class MyTest {

    public static void main(String[] args) {
        int[] arr = { 10, 11, 7, 6, 8, 9 };
        //创建一个 AVLTree对象
        AVLTree avlTree = new AVLTree();
        //添加结点
        for(int i=0; i < arr.length; i++) {
            avlTree.add(new Node(arr[i]));
        }

        //遍历
        System.out.println("中序遍历");
        avlTree.infixOrder();

        System.out.println("在平衡处理~~");
        System.out.println("树的高度=" + avlTree.getRoot().height()); //3
        System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight()); // 2
        System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight()); // 2
        System.out.println("当前的根结点=" + avlTree.getRoot());//8
    }
}

6.8 红黑树

有了平衡二叉树,为什么还需要红黑树?

  • AVL 的左右子树高度差不能超过 1,每次进行插入/删除操作时,几乎都需要通过旋转操作保持平衡
  • 在频繁进行插入/删除的场景中,频繁的旋转操作使得 AVL 的性能大打折扣
  • 红黑树通过牺牲严格的平衡,换取插入/删除时少量的旋转操作,整体性能优于 AVL
  • 红黑树插入时的不平衡,不超过两次旋转就可以解决;删除时的不平衡,不超过三次旋转就能解决
  • 红黑树的红黑规则,保证最坏的情况下,也能在 O(log~2~N) 时间内完成查找操作。

image-20220730215249378

红黑规则:

  1. 节点非黑即红
  2. 根节点为黑色
  3. 叶子节点为黑色(叶子节点是指末梢的空节点 NilNull
  4. 一个节点为红色,则其两个子节点必须是黑色的(根到叶子的所有路径,不可能存在两个连续的红色节点)
  5. 每个节点到叶子节点的所有路径,都包含相同数目的黑色节点(相同的黑色高度)

6.9 多叉树

二叉树的操作效率很高,但是依旧存在着问题,因为二叉树是需要加载到内存中的,当二叉树的节点少,不会出现什么问题,但是如果二叉树的节点很多(比如 1 亿), 就存在如下问题:

  1. 如果我们二叉树的结点中存放的数据是从文件中获取到的,那么在构建二叉树时,需要多次进行 i/o 操作(海量数据存在数据库或文件中),构建二叉树时,速度有影响
  2. 节点海量,也会造成二叉树的高度很大,会降低操作速度

多叉树介绍

在二叉树中,每个节点有数据项,最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点,就是多叉树

比如 2-3 树,2-3-4 树就是多叉树,多叉树通过重新组织节点,减少树的高度,能对二叉树进行优化

  1. 2-3 树的所有叶子节点都在同一层(只要是 B 树都满足这个条件)
  2. 有两个子节点的节点叫二节点,二节点要么没有节点,要么有两个子节点
  3. 有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点
  4. 对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则

image-20220604203116154

6.10 B 树、B+ 树、B* 树

B-tree 树即 B 树,B 即 Balanced,平衡的意思。也就是说 B 树是一个平衡树,也是一个排序树

image-20220604231830597

B 树说明:

  1. B 树的阶:结点的最多子结点个数,比如 2-3 树的阶就是 3,2-3-4 树的阶是 4
  2. B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点
  3. 关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据
  4. 搜索有可能在非叶子结点结束
  5. 其搜索性能等价于在关键字全集内做一次二分查找

B+ 树是 B 树的变体,也是一种多路搜索树,它和 B 树的区别是,它的所有数据都放到了叶子节点上

image-20220604232350191

B+ 树说明:

  1. B+ 树的搜索与 B 树也基本相同,区别是 B+ 树只有达到叶子结点才命中(B 树可以在非叶子结点命中,命中的意思就是找到对应的数据),其性能也等价于在关键字全集做一次二分查找
  2. 所有关键字都出现在叶子结点的链表中(即数据只能在叶子节点【也叫稠密索引】),且链表中的关键字(数据)恰好是有序的。
  3. 不可能在非叶子结点命中
  4. 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层
  5. 更适合文件索引系统
  6. B 树和 B+ 树各有自己的应用场景,不能说 B+ 树完全比 B 树好,反之亦然

B* 树是 B+ 树的变体,在 B+ 树的非根和非叶子节点再增加指向兄弟的指针

image-20220604232753894

B* 树说明:

  1. B* 树定义了非叶子结点关键字个数至少为 (2/3)M,即块的最低使用率为 2/3,而 B+ 树的块的最低使用率为 B+ 树的 1/2。
  2. 从第 1 个特点我们可以看出,B* 树分配新结点的概率比 B+ 树要低,空间使用率更高

7、堆

堆的定义如下:n 个元素的序列 {k1, k2, ki, …, kn} 当且仅当满足下关系时,称之为堆

  1. 小顶堆ki <= k2i && ki <= k2i+1,即每个结点的值都大于或等于其左右孩子结点的值
  2. 大顶堆ki >= k2i && ki >= k2i+1,即每个结点的值都小于或等于其左右孩子结点的值
    image-20220601230240474

堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值
  • 堆总是一棵完全二叉树

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等

因为堆有序的特点,一般用来做数组中的排序,一般升序采用大顶堆,降序采用小顶堆

8、图

前面的线性表和树,线性表局限于一个直接前驱和一个直接后继的关系;树也只能有一个直接前驱也就是父节点。当需要表示多对多的关系,就需要用到图

图的一些常用概念:

  1. 顶点

  2. 路径

  3. 无向图

    image-20220604235057155

  4. 有向图

  5. 带权图

    image-20220604235116658

8.1 图的表现方式

表示图的一种简单方式是使用二维数组,称为邻接矩阵表示法。图中的每条边(v, w),设置 A[v][w]=1;若不存在边 (v, w),则 A[v][w] = 0;如果边上带权值,那么可以设置 A[v][w] 等于该权值,同时使用一个很大或者很小的权值来表示不存在的边。如图,展示了无向图、有向图、有向网和它们的邻接矩阵
image-20220605032556213

  1. 邻接矩阵需要为每个顶点都分配 n 个边的空间,其实有很多边都是不存在的,会造成空间的一定损失
  2. 邻接表的实现只关心存在的边,不关心不存在的边,因此没有空间浪费,邻接表由数组 + 链表组成

image-20220605000207581

邻接列表只描述了指向外部的边。A 有一条边到 B,但是 B 没有边到 A,所以 A 没有出现在 B 的邻接列表中。查找两个顶点之间的边或者权重会比较费时,因为遍历邻接列表直到找到为止

8.2 图的深度优先与广度优先

深度优先遍历(Depth-First-Search),从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问,第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点, 可以这样理解每次都在访问完当前结点后首先访问当前结点的第一个邻接结点

这样的访问策略是优先往纵向挖掘深入,而不是对一个节点的所有邻接节点进行横向访问

深度优先搜索是一个递归的过程

  1. 访问初始顶点 x,访问后需要标记 x 已经访问过,不能再次重读访问

  2. 查找顶点 x 的第一个邻接点 y

  3. 如果 y 存在,则继续执行下面步骤,如果 y 不存在,则回到第 1 步,将从 x 的下一个顶点继续

  4. 如果 y 未被访问过,对 y 进行深度优先遍历,则是把 y 当做另一个 x,然后执行 123 步

  5. 查找顶点 x 的 y 邻接点的下一个邻接点,转到步骤 3

类似于一个 分层搜索的过程,广度优先遍历(Breadth-First-Search)需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点

  1. 访问初始结点 v 并标记结点 v 为已访问。
  2. 结点 v 入队列
  3. 当队列非空时,继续执行,否则算法结束。
  4. 出队列,取得队头结点 u。
  5. 查找结点 u 的第一个邻接结点 w。
  6. 若结点 u 的邻接结点 w 不存在,则转到步骤 3;否则循环执行以下三个步骤
    • 若结点 w 尚未被访问,则访问结点 w 并标记为已访问。
    • 结点 w 入队列
    • 查找结点 u 的继 w 邻接结点后的下一个邻接结点 w,转到步骤 6

image-20220605163756838

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {

    private ArrayList<String> vertexList; // 存储顶点集合
    private int[][] edges; // 存储图对应的邻接矩阵
    private int numOfEdges; // 表示边的数目
    private boolean[] isVisited; // 记录某个顶点是否被访问过

    public Graph(int n) {
        // 初始化矩阵和 vertexList
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;
        isVisited = new boolean[n];
    }

    /**
     * 插入节点
     */
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 添加边
     * @param v1 表示点的下标即第几个顶点
     * @param v2 第二个顶点对应的下标
     * @param weight
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    /**
     * 返回节点的个数
     */
    public int getNumOfVertex() {
        return vertexList.size();
    }

    /**
     * 得到边的数目
     */
    public int getNumOfEdges() {
        return numOfEdges;
    }

    /**
     * 返回节点 i (下标)对应的数据
     */
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    /**
     * 返回 v1 和 v2 的权值
     */
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    /**
     * 显示图对应的矩阵
     */
    public void showGraph() {
        for(int[] link : edges) {
            System.err.println(Arrays.toString(link));
        }
    }

    /**
     * 得到传入节点第一个邻接节点的下标 w
     * @param index 要求邻接节点下标的点
     * @return 如果存在就返回对应下标,不存在返回-1
     */
    public int getFirstNeighbor(int index) {
        for (int j = 0; j < vertexList.size(); j++) {
            if (edges[index][j] > 0){
                return j;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻接节点的下标来获取下一个邻接节点
     * @param v1 前一邻接节点的行下标
     * @param v2 前一邻接节点的列下标
     * @return
     */
    public int getNextNeighbor(int v1, int v2) {
        for(int j = v2 + 1; j < vertexList.size(); j++) {
            if(edges[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 深度优先遍历算法
     * @param isVisited 用于判断节点是否已经被访问过的数组
     * @param i 第一次就是 0
     */
    private void dfs(boolean[] isVisited, int i) {
        // 首先我们访问该结点,输出
        System.out.print(getValueByIndex(i) + "->");
        // 将结点设置为已经访问
        isVisited[i] = true;
        // 查找结点 i 的第一个邻接结点 w
        int w = getFirstNeighbor(i);
        while(w != -1) {// 说明有
            if(!isVisited[w]) {
                dfs(isVisited, w);
            }
            // 如果w结点已经被访问过
            w = getNextNeighbor(i, w);
        }
    }

    public void dfs() {
        isVisited = new boolean[vertexList.size()];
        for(int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
    }

    /**
     * 广度优先遍历算法
     * @param isVisited 用于判断节点是否已经被访问过的数组
     * @param i 第一次就是 0
     */
    private void bfs(boolean[] isVisited, int i) {
        int u ; // 表示队列的头结点对应下标
        int w ; // 邻接结点w
        // 队列,记录结点访问的顺序
        LinkedList queue = new LinkedList();
        // 访问结点,输出结点信息
        System.out.print(getValueByIndex(i) + "=>");
        // 标记为已访问
        isVisited[i] = true;
        // 将结点加入队列
        queue.addLast(i);

        while( !queue.isEmpty()) {
            // 取出队列的头结点下标
            u = (Integer)queue.removeFirst();
            // 得到第一个邻接结点的下标 w
            w = getFirstNeighbor(u);
            while(w != -1) { // 找到
                //是否访问过
                if(!isVisited[w]) {
                    System.out.print(getValueByIndex(w) + "=>");
                    // 标记已经访问
                    isVisited[w] = true;
                    // 入队
                    queue.addLast(w);
                }
                // 以u为前驱点,找w后面的下一个邻结点
                w = getNextNeighbor(u, w); // 体现出我们的广度优先
            }
        }

    }

    public void bfs() {
        isVisited = new boolean[vertexList.size()];
        for(int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }
}

测试方法:

public class MyTest {

    @Test
    public void test01() {
        //测试一把图是否创建ok
        int n = 5;  //结点的个数
        String Vertexs[] = {"A", "B", "C", "D", "E"};
        //创建图对象
        Graph graph = new Graph(n);
        //循环的添加顶点
        for(String vertex: Vertexs) {
            graph.insertVertex(vertex);
        }
        // 添加边:A-B A-C B-C B-D B-E
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);

        //显示一把邻结矩阵
        graph.showGraph();

        System.out.println("深度遍历");
        graph.dfs(); // A->B->C->D->E
        System.out.println("\n广度优先!");
        graph.bfs(); // A->B->C->D-E
    }

    @Test
    public void test02() {
        //测试一把图是否创建ok
        int n = 8;  //结点的个数
        String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
        //创建图对象
        Graph graph = new Graph(n);
        //循环的添加顶点
        for(String vertex: Vertexs) {
            graph.insertVertex(vertex);
        }
        //更新边的关系
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);
        //显示一把邻结矩阵
        graph.showGraph();

        System.out.println("深度遍历");
        graph.dfs(); // 1->2->4->8->5->3->6->7
        System.out.println("\n广度优先!");
        graph.bfs(); // 1->2->3->4->5->6->7->8
    }
}


END

本文作者:
文章标题:常用八大数据结构
本文地址:https://www.pendulumye.com/data-structure-and-algorithm/56.html
版权说明:若无注明,本文皆PendulumYe原创,转载请保留文章出处。
最后修改:2022 年 07 月 30 日
千山万水总是情,给个一毛行不行💋