原创

    数据结构入门教程

    内容概要:

    线性表和链表

    链表与单链表介绍

    单链表的应用

    基本介绍

    代码实现

    单链表的 创建、遍历、插入以及顺序插入 代码如下:

    public class SingleLinkedListTest {
        public static void main(String[] args) {
    
            // 01-创建几个节点
            HeroNode heroNode1 = new HeroNode(1, "松江", "及时雨");
            HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
            HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
            HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
    
            // 02-创建一个链表
            SingleLinkedList singleLinkedList = new SingleLinkedList();
    //        singleLinkedList.add(heroNode1);
    //        singleLinkedList.add(heroNode4);
    //        singleLinkedList.add(heroNode3);
    //        singleLinkedList.add(heroNode2);
    
            // 按照顺序加入
            singleLinkedList.addByOrder(heroNode1);
            singleLinkedList.addByOrder(heroNode4);
            singleLinkedList.addByOrder(heroNode3);
            singleLinkedList.addByOrder(heroNode2);
            singleLinkedList.addByOrder(heroNode2);
    
            // 03-显示单链表
            singleLinkedList.showList();
        }
    }
    
    /**
     * 定义 SingleLinkedList 单链表管理我们的英雄
     */
    class SingleLinkedList {
        // 01-初始化一个头节点,头节点不要动,不存放具体的数据
        private HeroNode head = new HeroNode(0, "", "");
    
        public HeroNode getHead() {
            return head;
        }
    
        // 02-添加节点到单向链表,直接添加到链表尾部
    
        /**
         * 思路分析:当不考虑编号顺序时
         * 1. 找到当前链表的最后节点
         * 2. 将最后这个节点的 next 指向新的节点
         */
        public void add(HeroNode heroNode) {
            // 因为头节点不能动,所以我们需要一个辅助变量 temp
            HeroNode temp = head;
    
            // 遍历链表
            while (true) {
                // 找到链表的最后
                if (temp.next == null) {
                    break;
                }
                // 如果没有找到最后,将 temp 后移
                temp = temp.next;
            }
            // 当退出 while 循环时,temp 就指向了链表的最后
            temp.next = heroNode;
        }
    
    
        // 根据排名将英雄添加到指定位置,即按照顺序添加
        public void addByOrder(HeroNode heroNode){
            HeroNode temp = head;
            boolean flag = false;    // 标志添加的编号是否存在,默认为 false
    
            while (true){
                if (temp.next == null){    // 说明 temp 已经在链表最后
                    break;
                }
                if(temp.next.no > heroNode.no){
                    break;
                } else if(temp.next.no == heroNode.no){    // 编号已经存在
                    flag = true;    // 说明编号存在
                    break;
                }
                temp = temp.next;
            }
    
            if(flag){    // 不能添加,编号存在
                System.out.printf("待插入的英雄编号 %d 已经存在了,不能加入!", heroNode.no);
            } else {
                heroNode.next = temp.next;
                temp.next = heroNode;
            }
        }
    
    
        // 显示链表[遍历]
        public void showList() {
            // 判断链表是否为空
            if (head.next == null) {
                System.out.println("链表为空");
                return;
            }
            HeroNode temp = head.next;
            while (true) {
                if (temp == null) {
                    break;
                }
                System.out.println(temp);
                // 将 temp 后移,否则是死循环
                temp = temp.next;
            }
        }
    
    }
    
    
    /**
     * 单链表
     */
    class HeroNode {
        public int no;
        public String name;
        public String nickname;
        public HeroNode next;   // 指向下一个节点
    
        // 构造器
        public HeroNode(int no, String name, String nickname) {
            this.no = no;
            this.name = name;
            this.nickname = nickname;
    
        }
    
        // 为了显示方便,重写 toString
        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickname='" + nickname + '\'' +
                    '}';
        }
    }
    

    单链表的节点信息的 修改操作 ,代码如下:

    /* 以下三行代码加入到 main 方法里面 */
    
    // 04-测试修改节点的代码
    HeroNode heroNode = new HeroNode(2,"小卢","玉麒麟~~~");
    singleLinkedList.update(heroNode);
    singleLinkedList.showList();
    
    
    
    /* 以下 update 方法加入到 SingleLinkedList 类里面 */
    
    // 修改节点的信息,根据 no 编号来修改
    public void update(HeroNode heroNode) {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空!!!");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;    // 到达了链表的最后
            }
            if (temp.no == heroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
    
        if (flag) {
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        } else {
            System.out.printf("没有找到编号为 %d 的节点,不能修改!!!", heroNode.no);
        }
    
    }
    

    单链表的节点信息的 删除操作 ,代码如下:

    /* 以下四行代码加入到 main 方法里面 */
    
    // 05-删除一个节点
    singleLinkedList.delete(1);
    singleLinkedList.delete(5);
    System.out.println("删除后链表的情况~~~~~");
    singleLinkedList.showList();
    
    
    
    /* 以下 delete 方法加入到 SingleLinkedList 类里面 */
    
    // 根据 no 删除节点
    public void delete(int no) {
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {    // 找到待删除结点的前一个结点 temp
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }
    }
    

    单链表面试题

    解决 第一个 题目:求单链表中有效节点的个数 ,代码如下:

    /* 以下三行代码加入到 main 方法里面 */
    
    HeroNode head = singleLinkedList.getHead();
    int length = SingleLinkedList.getLength(head);
    System.out.println("有效节点个数为:" + length);
    
    
    
    /* 以下 getLength 方法加入到 SingleLinkedList 类里面 */
    // 获取单链表的节点个数(如果是带头节点的单链表,则不统计头节点)
    public static int getLength(HeroNode heroNode) {
        if (heroNode.next == null) {
            return 0;
        }
    
        int length = 0;
        // 定义一个辅助遍历,这里就体现了没有统计头节点
        HeroNode cur = heroNode.next;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
    
        return length;
    }
    

    解决 第二个 题目:查找单链表中的倒数第 k 个节点【新浪面试题】 ,代码如下:

    /* 以下四行代码加入到 main 方法里面 */
    
    HeroNode res1 = SingleLinkedList.findNode(singleLinkedList.getHead(), 2);
    System.out.println("res = " + res1);
    HeroNode res2 = SingleLinkedList.findNode(singleLinkedList.getHead(), 5);
    System.out.println("res = " + res2);
    
    
    
    // 查找单链表中的倒数第 k 个节点 【新浪面试题】
    
    /**
     * 思路分析:
     * 1. 编写一个方法,接收 head 节点,同时接收一个 index
     * 2. index 表示是倒数第 index 个节点
     * 3. 先把链表从头到尾遍历,得到链表的总长度,使用 getLength 方法
     * 4. 得到 size 后,我们从链表的第一个车开始遍历 (size-index) 个,就可以得到
     * 5. 如果找到了,则返回该节点,否则返回 null
     */
    public static HeroNode findNode(HeroNode head, int index) {
        if (head.next == null) {
            return null;
        }
        int length = getLength(head);
        if (index <= 0 || index > length) {
            return null;
        }
        HeroNode cur = head.next;
        for (int i = 0; i < (length - index); i++) {
            cur = cur.next;
        }
        return cur;
    }
    

    解决 第三个 题目:单链表的反转【腾讯面试题】 ,代码如下:

    /* 以下五行代码加入到 main 方法里面 */
    
    // 单链表的反转测试
    System.out.println("原来链表的情况~~~");
    singleLinkedList.showList();
    System.out.println("反转后链表的情况~~~");
    SingleLinkedList.reverseList(head);
    singleLinkedList.showList();
    
    
    
    // 将单链表反转
    public static void reverseList(HeroNode head) {
        // 如果当前链表为空,或者只有一个节点,无需反转,直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }
    
        // 定义一个辅助变量,帮助遍历原先的链表
        HeroNode cur = head.next;
        HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0, "", "");
    
        // 遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表 reverseHead 的最前端
        while (cur != null) {
            next = cur.next;
            cur.next = reverseHead.next;    // 将 cur 的下一个节点指向新的链表的最前端
            reverseHead.next = cur;    // 将 cur 连接到新的链表
            cur = next;    // 让 cur 后移
        }
        // 将 head.next 指向 reverseHead.next ,实现单链表的反转
        head.next = reverseHead.next;
    }
    

    解决 第四个 题目:从尾到头打印单链表【百度面试题:要求方式1:反向遍历。要求方式2:Stack 栈】 ,代码如下:

    // 逆序打印,以下一行加入到 main方法中
    SingleLinkedList.revesrePrint(head);
    
    
    
    // 实现逆序打印
    public static void revesrePrint(HeroNode head){
        if(head.next == null){
            return;
        }
    
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
    
        // 压栈
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }
    
        // 出栈
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }
    

    双向链表

    基本介绍

    学完单链表发现,单链表只能从头结点开始访问链表中的数据元素,如果需要逆序访问单链表中的数据元素将极其低效。因而出现了 双链表结构双链表 是链表的一种,由节点组成,每个数据结点中都有两个指针,分别指向 直接后继直接前驱 。双链表结构如下图:

    双链表结构 双链表插入 双链表删除

    应用实现

    使用 双链表 对上述单链表的功能进行再次实现,代码如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/5/27 12:51
     * @Description: 双向链表案例
     */
    public class DoubleLinkedListTest {
        public static void main(String[] args) {
    
            System.out.println("双向链表测试~~~");
    
            // 01-创建几个节点
            HeroDoubleNode heroNode1 = new HeroDoubleNode(1, "松江", "及时雨");
            HeroDoubleNode heroNode2 = new HeroDoubleNode(2, "卢俊义", "玉麒麟");
            HeroDoubleNode heroNode3 = new HeroDoubleNode(3, "吴用", "智多星");
            HeroDoubleNode heroNode4 = new HeroDoubleNode(4, "林冲", "豹子头");
    
            DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
            doubleLinkedList.add(heroNode1);
            doubleLinkedList.add(heroNode2);
            doubleLinkedList.add(heroNode3);
            doubleLinkedList.add(heroNode4);
    
            doubleLinkedList.showList();
    
            // 修改测试
            HeroDoubleNode newNode = new HeroDoubleNode(4, "Jack", "Jacky");
            doubleLinkedList.update(newNode);
            System.out.println("修改后双向链表~~~");
            doubleLinkedList.showList();
    
            // 删除测试
            doubleLinkedList.delete(3);
            System.out.println("删除后双向链表~~~");
            doubleLinkedList.showList();
    
        }
    }
    
    
    class DoubleLinkedList {
    
        // 01-初始化一个头节点,头节点不要动,不存放具体的数据
        private HeroDoubleNode head = new HeroDoubleNode(0, "", "");
    
        // 02-返回头节点
        public HeroDoubleNode getHead() {
            return head;
        }
    
        // 03-显示链表[遍历]
        public void showList() {
            // 判断链表是否为空
            if (head.next == null) {
                System.out.println("链表为空");
                return;
            }
            HeroDoubleNode temp = head.next;
            while (true) {
                if (temp == null) {
                    break;
                }
                System.out.println(temp);
                // 将 temp 后移,否则是死循环
                temp = temp.next;
            }
        }
    
        // 04-添加节点到双向链表最后
    
        /**
         * 思路分析:当不考虑编号顺序时
         * 1. 找到当前链表的最后节点
         * 2. 将最后这个节点的 next 指向新的节点
         */
        public void add(HeroDoubleNode heroNode) {
            // 因为头节点不能动,所以我们需要一个辅助变量 temp
            HeroDoubleNode temp = head;
    
            // 遍历链表
            while (true) {
                // 找到链表的最后
                if (temp.next == null) {
                    break;
                }
                // 如果没有找到最后,将 temp 后移
                temp = temp.next;
            }
            // 当退出 while 循环时,temp 就指向了链表的最后
            temp.next = heroNode;
            heroNode.pre = temp;
        }
    
        // 05-修改节点的信息,根据 no 编号来修改
        public void update(HeroDoubleNode heroNode) {
            // 判断链表是否为空
            if (head.next == null) {
                System.out.println("链表为空!!!");
                return;
            }
            HeroDoubleNode temp = head.next;
            boolean flag = false;
            while (true) {
                if (temp == null) {
                    break;    // 到达了链表的最后
                }
                if (temp.no == heroNode.no) {
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
    
            if (flag) {
                temp.name = heroNode.name;
                temp.nickname = heroNode.nickname;
            } else {
                System.out.printf("没有找到编号为 %d 的节点,不能修改!!!", heroNode.no);
            }
    
        }
    
        /**
         * 06-删除节点思路分析:
         * 1. 对于双向链表,我们可以直接找到要删除的这个节点
         * 2. 找到后,自我删除节点即可
         */
        public void delete(int no) {
            if (head.next == null){
                System.out.println("链表为空,无法删除!!!");
                return;
            }
    
            HeroDoubleNode temp = head.next;
            boolean flag = false;
    
            while (true) {
                if (temp == null) {
                    break;
                }
                if (temp.no == no) {    // 找到待删除结点的前一个结点 temp
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
    
            if (flag) {
                temp.pre.next = temp.next;
                if (temp.next != null){
                    temp.next.pre = temp.pre;
                }
    
            } else {
                System.out.printf("要删除的 %d 节点不存在\n", no);
            }
        }
    }
    
    
    class HeroDoubleNode {
        public int no;
        public String name;
        public String nickname;
        public HeroDoubleNode next;   // 指向下一个节点
        public HeroDoubleNode pre;    // 指向前一个节点
    
        // 构造器
        public HeroDoubleNode(int no, String name, String nickname) {
            this.no = no;
            this.name = name;
            this.nickname = nickname;
        }
    
        // 为了显示方便,重写 toString
        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickname='" + nickname + '\'' +
                    '}';
        }
    }
    

    环形链表

    基本介绍

    环形链表 ,类似于单链表,也是一种链式存储结构,环形链表由单链表演化过来。单链表的最后一个结点的链域指向 NULL ,而环形链表则 首位相连 ,组成环状数据结构。如下图:

    约瑟夫环问题

    而在环形链表中,最为著名的即是 约瑟夫环问题 ,也称之为 丢手帕问题 。介绍如下图:

    解决 约瑟夫环问题 代码如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/5/27 18:22
     * @Description: 约瑟夫问题
     */
    public class Josephu {
        public static void main(String[] args) {
    
            // 创建链表
            CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
            circleSingleLinkedList.addBoy(5);    // 加入 5 个节点
            circleSingleLinkedList.showNode();
    
            // 出圈操作
            circleSingleLinkedList.countBoyNode(1, 2, 5);
        }
    }
    
    
    /**
     * 创建一个环形单项链表
     */
    class CircleSingleLinkedList {
        // 创建一个 first 节点
        private BoyNode first = null;
    
        // 添加节点,构建一个环形链表
        public void addBoy(int num) {
            if (num < 1) {
                System.out.println("参数小于 1 ,不正确!!!");
                return;
            }
    
            // 辅助节点,用于构建环形链表
            BoyNode curNode = null;
    
            // 使用 for 循环构建环形链表
            for (int i = 1; i <= num; i++) {
                // 根据编号创建节点
                BoyNode boyNode = new BoyNode(i);
    
                // 如果三第一个节点
                if (i == 1) {
                    first = boyNode;
                    first.setNext(first);
                    curNode = first;    // 让 curNode 指向第一个节点
    
                } else {
                    curNode.setNext(boyNode);
                    boyNode.setNext(first);
                    curNode = boyNode;
                }
    
            }
        }
    
        // 遍历当前的环形链表
        public void showNode() {
            if (first == null) {
                System.out.println("链表为空,没有节点~~~");
            }
    
            BoyNode temp = first;
    
            while (true) {
                System.out.printf("节点的编号 %d \n", temp.getNo());
                if (temp.getNext() == first) {
                    break;
                }
                temp = temp.getNext();
            }
        }
    
        // 根据用户的输入,计算节点出圈顺序
    
        /**
         * @param startsNo 表示从第几个节点开始数数
         * @param countNum 表示数几下
         * @param nums 表示最初有多少个节点在圈中
         */
        public void countBoyNode(int startsNo, int countNum, int nums) {
            // 对参数进行校验
            if (first == null || startsNo < 1 || startsNo > nums) {
                System.out.println("参数输入有误,请重新输入!!!");
                return;
            }
    
            // 创建辅助变量
            BoyNode helper = first;
            while (true) {
                if (helper.getNext() == first) {
                    break;
                }
                helper = helper.getNext();
            }
    
            // 节点报数前,先让 first 和 helper 移动 k-1 次
            for (int i = 0; i < (startsNo - 1); i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
    
            // 出圈操作
            while (true) {
                // 说明圈中只有一个节点
                if (helper == first) {
                    break;
                }
    
                for (int i = 0; i < (countNum - 1); i++) {
                    first = first.getNext();
                    helper = helper.getNext();
                }
                // 这是 first 着指向的节点就是要出圈节点
                System.out.printf("%d 节点出圈\n", first.getNo());
                first = first.getNext();
                helper.setNext(first);
            }
            System.out.printf("最后留在圈中的节点是 %d \n", first.getNo());
        }
    }
    
    
    /**
     * 创建一个 BoyNode 类,表示一个节点
     */
    class BoyNode {
    
        private int no;          // 编号
        private BoyNode next;    // 指向下一个节点,默认为 null
    
        public int getNo() {
            return no;
        }
    
        public void setNo(int no) {
            this.no = no;
        }
    
        public BoyNode getNext() {
            return next;
        }
    
        public void setNext(BoyNode next) {
            this.next = next;
        }
    
        public BoyNode(int no) {
            this.no = no;
        }
    
    }
    

    栈和队列

    栈的知识

    认识栈

    栈的介绍 出栈和入栈 栈的应用场景

    数组模拟栈

    数组模拟栈的 思路分析 如下图:

    数组模拟栈的 代码实现 如下:

    
    /**
     * @Author: guoshizhan
     * @Create: 2020/5/27 21:46
     * @Description: 栈的知识
     */
    public class ArrayStackTest {
        public static void main(String[] args) {
    
            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("push: 压栈");
                System.out.println("pop: 出栈");
                System.out.println("exit: 退出程序");
                System.out.println("请输入相关操作:");
                key = scanner.next();
    
                switch (key) {
                    case "show":
                        stack.showStack();
                        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("程序退出了!!!");
    
        }
    }
    
    
    // 定义一个 ArrayStack 表示栈
    class ArrayStack {
    
        private int maxSize;    // 栈的大小
        private int[] stack;    // 数组模拟栈,数据就放在该数组中
        private int top = -1;   // top 表示栈顶,初始值为 -1
    
        // 构造器
        public ArrayStack(int maxSize) {
            this.maxSize = maxSize;
            stack = new int[maxSize];
        }
    
        // 栈满
        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;
        }
    
        // 出栈-pop
        public int pop() {
            if (isEmpty()) {
                throw new RuntimeException("栈空,没有数据!!!");
            }
            int value = stack[top];
            top--;
            return value;
        }
    
        // 遍历栈
        public void showStack() {
            if (isEmpty()) {
                System.out.println("栈空,没有数据!!!");
                return;
            }
    
            for (int i = top; i >= 0; i--) {
                System.out.printf("stack[%d] = %d\n", i, stack[i]);
            }
        }
    
    }
    

    栈实现计算器

    /**
     * @Author: guoshizhan
     * @Create: 2020/5/28 10:28
     * @Description: 实现计算器【中缀表达式】
     */
    public class Calculator {
        public static void main(String[] args) {
    
            // 定义需要扫描的表达式
            String expression = "30+50*6-2";
    
            // 创建数栈和符号栈
            ArrayStack numStack = new ArrayStack(10);
            ArrayStack operStack = new ArrayStack(10);
    
            // 定义相关变量
            int index = 0;
            int num1;
            int num2;
            int oper;
            int res = 0;
            char ch;
            String keepNum = "";
    
            while (true) {
                // 得到表达式的每一个字符
                ch = expression.substring(index, index + 1).charAt(0);
                // 判断 ch 是数字还是运算符
                if (operStack.isOper(ch)) {    // 如果是运算符
                    // 判断当前符号栈是否为空
                    if (!operStack.isEmpty()) {
                        if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                            num1 = numStack.pop();
                            num2 = numStack.pop();
                            oper = operStack.pop();
                            res = numStack.cal(num1, num2, oper);
    
                            // 把运算结果如符号栈
                            numStack.push(res);
                            // 将当前操作符如符号栈
                            operStack.push(ch);
                        } else {
                            // 如果当前的操作符的优先级大于栈中的操作符,就直接入符号栈
                            operStack.push(ch);
                        }
                    } else {
                        // 如果为空,直接入符号栈
                        operStack.push(ch);
                    }
                } else {    // 如果是数,则直接入数栈
    //                numStack.push(ch - 48);    // 不能发现一个数时就直接入栈,如果是多位数,则运算出错
                    keepNum += ch;
    
                    if (index == expression.length() - 1) {
                        numStack.push(Integer.parseInt(keepNum));
                    } else {
                        // 判断后一位是否是操作符
                        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;
                }
            }
            while (true) {
                // 如果符号栈为空,则计算到最后的结果
                if (operStack.isEmpty()) {
                    break;
                } else {
                    num1 = numStack.pop();
                    num2 = numStack.pop();
                    oper = operStack.pop();
                    res = numStack.cal(num1, num2, oper);
                    numStack.push(res);
                }
            }
            // 输出最终结果
            System.out.println("表达式最终结果:" + res);
        }
    }
    
    
    // 定义一个 ArrayStack 表示栈
    class ArrayStack {
    
        private int maxSize;    // 栈的大小
        private int[] stack;    // 数组模拟栈,数据就放在该数组中
        private int top = -1;   // top 表示栈顶,初始值为 -1
    
        // 构造器
        public ArrayStack(int maxSize) {
            this.maxSize = maxSize;
            stack = new int[maxSize];
        }
    
        // 栈满
        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;
        }
    
        // 出栈-pop
        public int pop() {
            if (isEmpty()) {
                throw new RuntimeException("栈空,没有数据!!!");
            }
            int value = stack[top];
            top--;
            return value;
        }
    
        // 遍历栈
        public void showStack() {
            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;
            switch (oper) {
                case '+':
                    res = num1 + num2;
                    break;
                case '-':
                    res = num2 - num1;
                    break;
                case '*':
                    res = num2 * num1;
                    break;
                case '/':
                    res = num2 / num1;
                    break;
                default:
                    break;
            }
            return res;
        }
    
        // 获取栈顶的值
        public int peek() {
            return stack[top];
        }
    }
    

    前、中、后缀表达式

    前缀表达式 基本介绍如下:

    中缀表达式 基本介绍如下:

    后缀表达式 基本介绍如下:

    逆波兰计算器

    /**
     * @Author: guoshizhan
     * @Create: 2020/5/28 15:03
     * @Description: 逆波兰计算器
     */
    public class PolandNotation {
        public static void main(String[] args) {
    
            // 先定义逆波兰表达式 (3+4)*5-6 ==> 3 4 + 5 * 6 -
            String suffixExpression = "3 4 + 5 * 6 -";
    
            /**
             * 思路分析:
             * 1. 先将 suffixExpression 放到 ArrayList 中
             * 2. 将 ArrayList 传递给一个方法,然后遍历 ArrayList,配合栈完成计算
             */
            List<String> list = getListstring(suffixExpression);
            System.out.println(list);
    
            int res = calculate(list);
            System.out.println("逆波兰表达式最终结果:" + res);
            System.out.println();
    
            // 定义逆波兰表达式 4*5-8+60+8/2 ==> 4 5 * 8 - 60 + 8 2 / +
            String suffixExp = "4 5 * 8 - 60 + 8 2 / +";
            List<String> stringList = getListstring(suffixExp);
            System.out.println(stringList);
            int calculate = calculate(stringList);
            System.out.println("逆波兰表达式最终结果:" + calculate);
    
        }
    
        public static List<String> getListstring(String suffixExpression) {
            // 将 suffixExpression 分割
            String[] strings = suffixExpression.split(" ");
            List<String> list = new ArrayList<>();
            for (String string : strings) {
                list.add(string);
            }
            return list;
        }
    
        // 完成逆波兰表达式的运算
        public static int calculate(List<String> ls) {
            // 创建栈
            Stack<String> strings = new Stack<>();
            for (String item : ls) {
                if (item.matches("\\d+")) {    //匹配多位数
                    strings.push(item);
                } else {
                    // pop 出两个数并运算,然后入栈
                    int num2 = Integer.parseInt(strings.pop());
                    int num1 = Integer.parseInt(strings.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 入栈
                    strings.push(res + "");
                }
            }
            // 最后留在栈中的数就是结果
            return Integer.parseInt(strings.pop());
        }
    }
    

    中缀转后缀

    中缀表达式 转化为 后缀表达式 ,难度有点大,详情如下图:

    中缀表达式 转化为 后缀表达式 代码实现如下:

    // 以下七行代码是 main 方法中代码
    // 将中缀表达式转化为后缀表达式
    String expression = "1+((20+3)*4)-5";
    List<String> list1 = toInfixExpressionList(expression);
    System.out.println(list1);
    
    List<String> list2 = parseSuffixExpressionList(list1);
    System.out.println(list2);
    
    int calculate1 = calculate(list2);
    System.out.println(calculate1);
    
    
    
    // 将中缀表达式转化成对应的 List
    public static List<String> toInfixExpressionList(String s) {
        // 定义一个 List,存放中缀表达式对应的内容
        List<String> ls = new ArrayList<>();
        int i = 0;    // 这是一个指针,用于遍历中缀表达式字符串
        String str;
        char c;
        do {
            // 如果 c 是一个非数字
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                ls.add("" + c);
                i++;
            } else {
                str = "";
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                ls.add(str);
            }
    
        } while (i < s.length());
        return ls;
    }
    
    // 转化成后缀表达式操作:ArrayList [1, +, (, (, 20, +, 3, ), *, 4, ), -, 5]  ==>  ArrayList [1,20,3,+,4,*,+,5,-]
    public static List<String> parseSuffixExpressionList(List<String> ls) {
        Stack<String> chStack = new Stack<>();    // 符号栈
        List<String> list = new ArrayList<>();
    
        // 遍历 ls
        for (String item : ls) {
            if (item.matches("\\d+")) {
                list.add(item);
            } else if (item.equals("(")) {
                chStack.push(item);
            } else if (item.equals(")")) {
                while (!chStack.peek().equals("(")) {
                    list.add(chStack.pop());
                }
                chStack.pop();    // 消除小括号
            } else {
                while (chStack.size() != 0 && Operaation.getValue(chStack.peek()) >= Operaation.getValue(item)) {
                    list.add(chStack.pop());
                }
                chStack.push(item);
            }
        }
        while (chStack.size() != 0) {
            list.add(chStack.pop());
        }
        return list;
    }
    
    

    逆波兰计算器完整版

    逆波兰计算器完整版 代码如下:

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Stack;
    import java.util.regex.Pattern;
    
    public class ReversePolishMultiCalc {
    
         /**
         * 匹配 + - * / ( ) 运算符
         */
        static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";
    
        static final String LEFT = "(";
        static final String RIGHT = ")";
        static final String ADD = "+";
        static final String MINUS= "-";
        static final String TIMES = "*";
        static final String DIVISION = "/";
    
        public static void main(String[] args) {
            //String math = "9+(3-1)*3+10/2";
            String math = "12.8 + (2 - 3.55)*4+10/5.0";
            try {
                doCalc(doMatch(math));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    
        /**
         * 加減 + -
         */
        static final int LEVEL_01 = 1;
        /**
         * 乘除 * /
         */
        static final int LEVEL_02 = 2;
    
        /**
         * 括号
         */
        static final int LEVEL_HIGH = Integer.MAX_VALUE;
    
    
        static Stack<String> stack = new Stack<>();
        static List<String> data = Collections.synchronizedList(new ArrayList<String>());
    
        /**
         * 去除所有空白符
         * @param s
         * @return
         */
        public static String replaceAllBlank(String s ){
            // \\s+ 匹配任何空白字符,包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
            return s.replaceAll("\\s+","");
        }
    
        /**
         * 判断是不是数字 int double long float
         * @param s
         * @return
         */
        public static boolean isNumber(String s){
            Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");
            return pattern.matcher(s).matches();
        }
    
        /**
         * 判断是不是运算符
         * @param s
         * @return
         */
        public static boolean isSymbol(String s){
            return s.matches(SYMBOL);
        }
    
        /**
         * 匹配运算等级
         * @param s
         * @return
         */
        public static int calcLevel(String s){
            if("+".equals(s) || "-".equals(s)){
                return LEVEL_01;
            } else if("*".equals(s) || "/".equals(s)){
                return LEVEL_02;
            }
            return LEVEL_HIGH;
        }
    
        /**
         * 匹配
         * @param s
         * @throws Exception
         */
        public static List<String> doMatch (String s) throws Exception{
            if(s == null || "".equals(s.trim())) throw new RuntimeException("data is empty");
            if(!isNumber(s.charAt(0)+"")) throw new RuntimeException("data illeagle,start not with a number");
    
            s = replaceAllBlank(s);
    
            String each;
            int start = 0;
    
            for (int i = 0; i < s.length(); i++) {
                if(isSymbol(s.charAt(i)+"")){
                    each = s.charAt(i)+"";
                    //栈为空,(操作符,或者 操作符优先级大于栈顶优先级 && 操作符优先级不是( )的优先级 及是 ) 不能直接入栈
                    if(stack.isEmpty() || LEFT.equals(each)
                            || ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)){
                        stack.push(each);
                    }else if( !stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())){
                        //栈非空,操作符优先级小于等于栈顶优先级时出栈入列,直到栈为空,或者遇到了(,最后操作符入栈
                        while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek()) ){
                            if(calcLevel(stack.peek()) == LEVEL_HIGH){
                                break;
                            }
                            data.add(stack.pop());
                        }
                        stack.push(each);
                    }else if(RIGHT.equals(each)){
                        // ) 操作符,依次出栈入列直到空栈或者遇到了第一个)操作符,此时)出栈
                        while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())){
                            if(LEVEL_HIGH == calcLevel(stack.peek())){
                                stack.pop();
                                break;
                            }
                            data.add(stack.pop());
                        }
                    }
                    start = i ;    //前一个运算符的位置
                }else if( i == s.length()-1 || isSymbol(s.charAt(i+1)+"") ){
                    each = start == 0 ? s.substring(start,i+1) : s.substring(start+1,i+1);
                    if(isNumber(each)) {
                        data.add(each);
                        continue;
                    }
                    throw new RuntimeException("data not match number");
                }
            }
            //如果栈里还有元素,此时元素需要依次出栈入列,可以想象栈里剩下栈顶为/,栈底为+,
            //应该依次出栈入列,可以直接翻转整个stack 添加到队列
            Collections.reverse(stack);
            data.addAll(new ArrayList<>(stack));
    
            System.out.println(data);
            return data;
        }
    
        /**
         * 算出结果
         * @param list
         * @return
         */
        public static Double doCalc(List<String> list){
            Double d = 0d;
            if(list == null || list.isEmpty()){
                return null;
            }
            if (list.size() == 1){
                System.out.println(list);
                d = Double.valueOf(list.get(0));
                return d;
            }
            ArrayList<String> list1 = new ArrayList<>();
            for (int i = 0; i < list.size(); i++) {
                list1.add(list.get(i));
                if(isSymbol(list.get(i))){
                    Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
                    list1.remove(i);
                    list1.remove(i-1);
                    list1.set(i-2,d1+"");
                    list1.addAll(list.subList(i+1,list.size()));
                    break;
                }
            }
            doCalc(list1);
            return d;
        }
    
        /**
         * 运算
         * @param s1
         * @param s2
         * @param symbol
         * @return
         */
        public static Double doTheMath(String s1,String s2,String symbol){
            Double result ;
            switch (symbol){
                case ADD : result = Double.valueOf(s1) + Double.valueOf(s2); break;
                case MINUS : result = Double.valueOf(s1) - Double.valueOf(s2); break;
                case TIMES : result = Double.valueOf(s1) * Double.valueOf(s2); break;
                case DIVISION : result = Double.valueOf(s1) / Double.valueOf(s2); break;
                default : result = null;
            }
            return result;
    
        }
    
    }
    
    

    队列知识

    认识队列

    队列 是一种 先进先出 的数据结构,也是常见的数据结构之一。日常生活中的 排队买东西 就是一种典型的队列。

    数组模拟队列

    public class ArrayQueueTest {
        public static void main(String[] args) {
            // 创建一个队列
            ArrayQueue arrayQueue = new ArrayQueue(3);
            char key = ' ';    // 接收用户输入
            Scanner scanner = new Scanner(System.in);
            boolean loop = true;
            while (loop) {
    
                System.out.println("s :显示队列(show)");
                System.out.println("e :退出程序(exit)");
                System.out.println("a :添加数据到队列(add)");
                System.out.println("g :从队列取出数据(get)");
                System.out.println("h :查看队列头数据(head)");
    
                key = scanner.next().charAt(0);    // 接收一个字符
                switch (key) {
                    case 's':
                        arrayQueue.showQueue();
                        break;
                    case 'e':
                        scanner.close();
                        loop = false;
                        System.out.println("程序已经退出!!!");
                        System.exit(0);
                        break;
                    case 'a':
                        System.out.println("请输入一个整数:");
                        int value = scanner.nextInt();
                        arrayQueue.addQueue(value);
                        break;
                    case 'g':
                        try {
                            int queue = arrayQueue.getQueue();
                            System.out.printf("取出的数据是:%d\n", queue);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h':
                        try {
                            int res = arrayQueue.headQueue();
                            System.out.printf("队列头的数据是:%d\n", res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    default:
                        break;
    
                }
            }
        }
    }
    
    /**
     * 使用数组模拟队列
     */
    class ArrayQueue {
    
        private int maxSize;    // 表示数组最大容量
        private int front;      // 队列头
        private int rear;       // 队列尾
        private int[] arr;      // 此数组用于存放数据,模拟队列
    
    
        // 01-创建队列构造器
        public ArrayQueue(int arrMaxSize) {
            maxSize = arrMaxSize;
            arr = new int[maxSize];
            front = -1;    // 指向队列头部,即队列头的前一个位置
            rear = -1;     // 指向队列尾部,即队列最后一个数据
        }
    
    
        // 02-判断队列是否满
        public boolean isFull() {
            return rear == maxSize - 1;
        }
    
    
        // 03-判断队列是否为空
        public boolean isEmpty() {
            return rear == front;
        }
    
    
        // 04-添加数据到队列
        public void addQueue(int num) {
            // 判断队列是否满
            if (isFull()) {
                System.out.println("队列满了,无法加入数据!!!");
                return;
            }
            rear++;    // rear 后移一位
            arr[rear] = num;
        }
    
    
        // 05-获取队列的数据,即出队列
        public int getQueue() {
            // 判断队列是否为空
            if (isEmpty()) {
                throw new RuntimeException("队列为空,不能取数据!!!");
            }
            front++;
            return arr[front];
        }
    
    
        // 06-显示队列的所有数据
        public void showQueue() {
            if (isEmpty()) {
                System.out.println("队列为空,没有数据!!!");
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.printf("arr[%d] = %d\n", i, arr[i]);
            }
        }
    
    
        // 07-显示队列的头数据
        public int headQueue() {
            if (isEmpty()) {
                throw new RuntimeException("队列为空,没有数据!!!");
            }
            return arr[++front];
        }
    
    }
    

    数组模拟队列 会出现一个小问题:数组不能够重复使用 。比如队列最大值为 3 ,添加 3 个数之后然后取出,再次添加就出现了队列满的情况。为了解决这个问题,就有了环形队列。接着往下看!!!

    环形队列

    环形队列 就是一个环,队列头和队列尾可以循环重合 ,且避免了普通队列的缺点,就是有点难理解而已,其实它的本质仍然是一个队列,一样有队列头,队列尾。它的特点一样是 先进先出(FIFO)

    public class ArrayCircleQueueTest {
        public static void main(String[] args) {
    
            // 创建一个队列,构造方法里面的参数4代表队列的有效数据最大是 3
            ArrayCircleQueue arrayQueue = new ArrayCircleQueue(4);
            char key = ' ';    // 接收用户输入
            Scanner scanner = new Scanner(System.in);
            boolean loop = true;
            while (loop) {
    
                System.out.println("s :显示队列(show)");
                System.out.println("e :退出程序(exit)");
                System.out.println("a :添加数据到队列(add)");
                System.out.println("g :从队列取出数据(get)");
                System.out.println("h :查看队列头数据(head)");
    
                key = scanner.next().charAt(0);    // 接收一个字符
                switch (key) {
                    case 's':
                        arrayQueue.showQueue();
                        break;
                    case 'e':
                        scanner.close();
                        loop = false;
                        System.out.println("程序已经退出!!!");
                        System.exit(0);
                        break;
                    case 'a':
                        System.out.println("请输入一个整数:");
                        int value = scanner.nextInt();
                        arrayQueue.addQueue(value);
                        break;
                    case 'g':
                        try {
                            int queue = arrayQueue.getQueue();
                            System.out.printf("取出的数据是:%d\n", queue);
                        } catch (Exception e) {
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h':
                        try {
                            int res = arrayQueue.headQueue();
                            System.out.printf("队列头的数据是:%d\n", res);
                        } catch (Exception e) {
                            System.out.println(e.getMessage());
                        }
                        break;
                    default:
                        break;
    
                }
            }
        }
    }
    
    /**
     * 使用数组模拟环形队列
     */
    class ArrayCircleQueue {
    
        private int maxSize;    // 表示数组最大容量
        private int front;      // 队列头
        private int rear;       // 队列尾
        private int[] arr;      // 此数组用于存放数据,模拟队列
    
    
        // 01-创建队列构造器
        public ArrayCircleQueue(int arrMaxSize) {
            maxSize = arrMaxSize;
            arr = new int[maxSize];
            front = 0;    // 指向队列头部,即队列头的前一个位置,可以不写,默认就是0
            rear = 0;     // 指向队列尾部,即队列最后一个数据,可以不写,默认就是0
        }
    
    
        // 02-判断队列是否满
        public boolean isFull() {
            return (rear + 1) % maxSize == front;
        }
    
    
        // 03-判断队列是否为空
        public boolean isEmpty() {
            return rear == front;
        }
    
    
        // 04-添加数据到队列
        public void addQueue(int num) {
            // 判断队列是否满
            if (isFull()) {
                System.out.println("队列满了,无法加入数据!!!");
                return;
            }
            arr[rear] = num;
            rear = (rear + 1) % maxSize;    // rear 后移一位,但是必须考虑取模
        }
    
    
        // 05-获取队列的数据,即出队列
        public int getQueue() {
            // 判断队列是否为空
            if (isEmpty()) {
                throw new RuntimeException("队列为空,不能取数据!!!");
            }
            /**
             * 这里需要进行分析:
             * 1. front 是指向队列的第一个元素
             * 2. 需要先把 front 的值保存到一个临时变量
             * 3. 然后再将 front 后移,这里需要考虑取模,否则会报数组越界异常
             * 4. 将临时保存的变量返回
             */
            int value = arr[front];
            front = (front + 1) % maxSize;
            return value;
        }
    
    
        // 06-显示队列的所有数据
        public void showQueue() {
            if (isEmpty()) {
                System.out.println("队列为空,没有数据!!!");
            }
            /**
             * 如何遍历环形队列?
             * 1. 从 front 开始遍历
             * 2. 遍历 (rear + maxSize - front) % maxSize 个
             */
            for (int i = front; i < front + size(); i++) {
                System.out.printf("arr[%d] = %d\n", i % maxSize, arr[i % maxSize]);
            }
        }
    
    
        // 07-显示队列的头数据
        public int headQueue() {
            if (isEmpty()) {
                throw new RuntimeException("队列为空,没有数据!!!");
            }
            return arr[front];
        }
    
    
        // 08-求出当前队列有效数据的个数
        public int size() {
            return (rear + maxSize - front) % maxSize;
        }
    
    }
    

    递归和回溯

    迷宫问题

    迷宫问题 代码实现如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/5/29 12:03
     * @Description: 迷宫问题
     */
    public class Maze {
        public static void main(String[] args) {
    
            // 01-创建二维数组,模拟模拟迷宫
            int[][] maze = new int[8][7];
    
            // 02-初始化迷宫,使用 1 表示墙
            for (int i = 0; i < 7; i++) {
                maze[0][i] = 1;
                maze[7][i] = 1;
            }
            for (int i = 0; i < 8; i++) {
                maze[i][0] = 1;
                maze[i][6] = 1;
            }
            maze[3][1] = 1;
            maze[3][2] = 1;
    
            // 03-打印迷宫看一下
            for (int i = 0; i < maze.length; i++) {
                for (int j = 0; j < 7; j++) {
                    System.out.print(maze[i][j] + " ");
                }
                System.out.println();
            }
    
            // 04-找迷宫出口
            findWay(maze, 1, 1);
    
            // 05-打印新迷宫
            System.out.println("--------------");
            for (int i = 0; i < maze.length; i++) {
                for (int j = 0; j < 7; j++) {
                    System.out.print(maze[i][j] + " ");
                }
                System.out.println();
            }
    
        }
    
    
        /**
         * 使用递归回溯来使小球走出迷宫
         *
         * @param maze 表示迷宫
         * @param i    j 表示坐标,即从那个位置出发 (1,1)
         * @return 如果找到通路,就返回 true ,否则返回 false
         * <p>
         * 补充说明:
         * 1. 如果小球能到达 maze[6][5], 则说明通路找到
         * 2. 约定:当 maze[i][j] 为 0 表示该点没有走过,1 表示墙,2 表示可以走,3 表示高点走过,但是走不通
         * 3. 走迷宫时,需要确定一个策略 :下->右->上->左,如果该点走不通,再回溯
         */
        public static boolean findWay(int[][] maze, int i, int j) {
            if (maze[6][5] == 2) {    // 通路已经找到,OK
                return true;
            } else {
                if (maze[i][j] == 0) {    // 如果当前这个点没有走过
                    // 按照策略走:下->右->上->左
                    maze[i][j] = 2;    // 假定该店可以走通
                    if (findWay(maze, i + 1, j)) {    // 向下走
                        return true;
                    } else if (findWay(maze, i, j + 1)) {    // 向右走
                        return true;
                    } else if (findWay(maze, i - 1, j)) {    // 向上走
    
                    } else if (findWay(maze, i, j - 1)) {    // 向左走
                        return true;
                    } else {
                        // 说明该店走不通,是死路
                        maze[i][j] = 3;
                        return false;
                    }
                } else {
                    // 如果 maze[i][j] != 0,那么可能情况为 1,2,3,那么直接返回 false
                    return false;
                }
            }
            return false;
        }
    }
    

    八皇后问题

    思路分析

    八皇后问题 问题代码实现如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/5/29 17:12
     * @Description: 八皇后问题
     */
    public class Queue8 {
    
        // 定义一个 max 表示右多少个皇后
        int max = 8;
    
        // 定义数组 array,保存处理结果,例如:arr = {0, 4, 7, 5, 2, 6, 1, 3}
        int[] array = new int[max];
    
        // 用于记录解法个数
        static int count = 0;
    
        // 用于记录冲突次数
        static int judgeCount = 0;
    
        public static void main(String[] args) {
    
            Queue8 queue8 = new Queue8();
            queue8.check(0);
            System.out.println("一共有 " + count + " 种解法!!!");
            System.out.println("一共有 " + judgeCount + " 次冲突!!!");
    
        }
    
    
        // 放置第 n 个皇后
        private void check(int n) {
            if (n == max) {
                print();
                return;
            }
    
            // 依此放入皇后,并判断是否冲突
            for (int i = 0; i < max; i++) {
                // 先把当前这个皇后 n ,放到该行第 1 列
                array[n] = i;
                // 判断放置第 n 个皇后到 i 列是否冲突
                if (judge(n)) {
                    check(n + 1);
                }
                // 如果冲突,就继续执行 array[n] == i;
    
            }
        }
    
    
        // 检测当前皇后是否和前面已经摆好的皇后冲突,n 表示第 n 个皇后
        private boolean judge(int n) {
            judgeCount++;
            for (int i = 0; i < n; i++) {
                if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                    return false;
                }
            }
            return true;
        }
    
    
        // 将皇后摆放的位置输出
        public void print() {
            count++;
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
            System.out.println();
        }
    
    }
    

    数组和广义表

    稀疏数组

    基本介绍

    稀疏数组 可以看做是 普通数组的压缩 ,当一个数组中 大部分元素为 0 或者为同一个值 的数组时,可以使用稀疏数组来保存该数组。

    应用案例

    棋盘存档案例 就是一个 稀疏数组 的实际应用案例。参考下图:

    案例分析

    代码实现

    使用 稀疏数组 实现的 棋盘存档案例 如下:

    public class SparseArray {
        public static void main(String[] args) throws Exception {
    
            // 01-创建一个原始的二维数组 11 * 11 , 0 表示没有棋子, 1 表示黑子 ,  2 表示蓝子
            int chessArray[][] = new int[11][11];
            chessArray[1][2] = 1;
            chessArray[2][3] = 2;
            chessArray[4][5] = 2;
    
    
            // 02-输出原始的二维数组
            System.out.println("原始的二维数组:\n-----------------------------------------");
            for (int[] row : chessArray) {
                for (int data : row) {
                    System.out.printf("%d\t", data);
                }
                System.out.println();
            }
    
    
            // 03-遍历二维数组 得到非0数据的个数
            int sum = 0;
            for (int i = 0; i < chessArray.length; i++) {
                for (int j = 0; j < chessArray.length; j++) {
                    if (chessArray[i][j] != 0) {
                        sum++;
                    }
                }
            }
    
    
            // 04-创建对应的稀疏数组并赋值
            int sparseArr[][] = new int[sum + 1][3];
            sparseArr[0][0] = chessArray.length;
            sparseArr[0][1] = chessArray[0].length;
            sparseArr[0][2] = sum;
    
    
            // 05-遍历原始二维数组,将非0的值存放到 sparseArr 中
            int count = 0;    // count 对应稀疏数组的行,用来记录第几个非0数据
            for (int i = 0; i < chessArray.length; i++) {
                for (int j = 0; j < chessArray.length; j++) {
                    if (chessArray[i][j] != 0) {
                        count++;
                        sparseArr[count][0] = i;
                        sparseArr[count][1] = j;
                        sparseArr[count][2] = chessArray[i][j];
                    }
                }
            }
    
    
            // 06-输出稀疏数组
            System.out.println();
            System.out.println("原始二维数组转为稀疏数组后:\n-----------------------------------------");
            for (int i = 0; i < sparseArr.length; i++) {
                System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
            }
            System.out.println();
    
    
            // 07-将稀疏数组恢复成原始的二维数组,思路见案例分析
            int chessArr[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
            for (int i = 1; i < sparseArr.length; i++) {
                chessArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
            }
    
    
            // 08-输出恢复后的二维数组
            System.out.println("从稀疏数组恢复到原始二维数组:\n-----------------------------------------");
            for (int[] row : chessArr) {
                for (int data : row) {
                    System.out.printf("%d\t", data);
                }
                System.out.println();
            }
            System.out.println();
    
    
            // 09-将稀疏数组保存到磁盘
            File file = new File("data.txt");
            sparseToDisk(file, sparseArr);
    
    
            // 10-从磁盘读取稀疏数组并打印
            System.out.println("从磁盘读取稀疏数组并打印:\n-----------------------------------------");
            int[][] ints = diskToSparse(file, sparseArr);
            for (int[] anInt : ints) {
                for (int i : anInt) {
                    System.out.printf("%d\t", i);
                }
                System.out.println();
            }
    
        }
    
    
        /**
         * 将稀疏数组存入磁盘(文件)
         */
        public static void sparseToDisk(File file, int[][] arr) throws IOException {
            if (!file.exists()) {
                file.createNewFile();
            }
    
            FileWriter writer = new FileWriter(file);
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < 3; j++) {
                    int num = arr[i][j];
                    // 把 num 装箱,方便后面的写入以及读取文件
                    Integer integer = new Integer(num);
                    // 拼接空的字符串的目的:更方便读取文件,即从文件读取并还原稀疏数组
                    writer.write(integer.toString() + " ");
                }
                writer.write("\r\n");
            }
            writer.flush();
            writer.close();
        }
    
    
        /**
         * 从文件获取稀疏数组
         */
        public static int[][] diskToSparse(File file, int[][] arr) throws Exception {
            BufferedReader reader = new BufferedReader(new FileReader(file));
            int[][] sparseArray = new int[arr.length][3];
            for (int i = 0; i < arr.length; i++) {
                // 读取一整行
                String s = reader.readLine();
                // 以空格分割字符串
                String[] split = s.split(" ");
                int j = 0;
                for (String s1 : split) {
                    sparseArray[i][j++] = Integer.valueOf(s1);
    
                }
            }
            reader.close();
            return sparseArray;
        }
    }
    

    树和二叉树

    树的初识

    为什么需要树

    树的常用术语

    二叉树

    二叉树的概念

    二叉树的遍历

    二叉树的 前序遍历中序遍历后序遍历 代码实现如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/6/29 12:50
     * @Description: 二叉树的前序遍历、中序遍历和后序遍历
     */
    public class BinaryTreeTest {
        public static void main(String[] args) {
    
            // 创建二叉树
            BinaryTree binaryTree = new BinaryTree();
    
            // 创建结点
            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, "后羿");
            Node node6 = new Node(6, "女娲");
            Node node7 = new Node(7, "张良");
            Node node8 = new Node(8, "刘备");
    
            // 构建结点之间的关系
            node1.setLeft(node2);
            node1.setRight(node3);
            node2.setLeft(node4);
            node2.setRight(node5);
            node3.setLeft(node6);
            node3.setRight(node7);
            node4.setLeft(node8);
    
            // 形成二叉树
            binaryTree.setRoot(node1);
    
            System.out.println("前序遍历:");
            binaryTree.preOrder();
            System.out.println("=======================");
    
            System.out.println("中序遍历:");
            binaryTree.infixOrder();
            System.out.println("=======================");
    
            System.out.println("后序遍历:");
            binaryTree.postOrder();
    
        }
    }
    
    // 编写二叉树类
    class BinaryTree {
    
        private Node root;
    
        public void setRoot(Node root) {
            this.root = root;
        }
    
        // 前序遍历
        public void preOrder() {
            if (this.root != null) {
                this.root.preOrder();
            } else {
                System.out.println("The Binary Tree is null !!!");
            }
        }
    
        // 中序遍历
        public void infixOrder() {
            if (this.root != null) {
                this.root.infixOrder();
            } else {
                System.out.println("The Binary Tree is null !!!");
            }
        }
    
        // 后序遍历
        public void postOrder() {
            if (this.root != null) {
                this.root.postOrder();
            } else {
                System.out.println("The Binary Tree is null !!!");
            }
        }
        
    }
    
    // 编写结点类
    class Node {
        
        private int no;
        private String name;
        private Node left;
        private Node right;
    
        public Node(int no, String name) {
            this.no = no;
            this.name = name;
        }
    
        public int getNo() {
            return no;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }
    
        public void setNo(int no) {
            this.no = no;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public Node getLeft() {
            return left;
        }
    
        public void setLeft(Node left) {
            this.left = left;
        }
    
        public Node getRight() {
            return right;
        }
    
        public void setRight(Node right) {
            this.right = right;
        }
    
        // 编写前序遍历方法
        public void preOrder() {
    
            // 输出父结点
            System.out.println(this);
    
            // 递归向左子树前序遍历
            if (this.left != null) {
                this.left.preOrder();
            }
    
            // 递归向右子树前序遍历
            if (this.right != null) {
                this.right.preOrder();
            }
    
        }
    
        // 编写中序遍历方法
        public void infixOrder() {
    
            // 递归向左子树前序遍历
            if (this.left != null) {
                this.left.infixOrder();
            }
    
            // 输出父结点
            System.out.println(this);
    
            // 递归向右子树前序遍历
            if (this.right != null) {
                this.right.infixOrder();
            }
    
        }
    
        // 编写后序遍历方法
        public void postOrder() {
    
            // 递归向左子树前序遍历
            if (this.left != null) {
                this.left.postOrder();
            }
    
            // 递归向右子树前序遍历
            if (this.right != null) {
                this.right.postOrder();
            }
    
            // 输出父结点
            System.out.println(this);
    
        }
        
    }
    

    二叉树的查找

    查找要求:
    1、请编写前序查找,中序查找和后序查找的方法。 2、分别使用三种查找方式,查找 heroNO = 5 的节点 3、分析各种查找方式,分别比较了多少次

    二叉树的 三种查找方式 代码如下:

    /**
     * 以下三种遍历查找的方法写在 Node 类中
     */
     
    // 前序遍历查找
    public Node preOrderSearch(int no) {
    
        System.out.println("前序遍历次数~~~");
    
        if (this.no == no) {
            return this;
        }
    
        // 判断当前结点的左子结点是否为空,如果不为空,则递归前序遍历。找到结点则返回
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
    
        // 如果找到,就返回 resNode
        if (resNode != null) {
            return resNode;
        }
    
        // 如果没有找到,则向右递归
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
    
        return resNode;
    
    }
    
    // 中序遍历查找
    public Node infixOrderSearch(int no) {
    
        // 判断当前结点的左子结点是否为空,如果不为空,则递归前序遍历。找到结点则返回
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
    
        // 如果找到,就返回 resNode
        if (resNode != null) {
            return resNode;
        }
    
        System.out.println("中序遍历次数~~~");
        if (this.no == no) {
            return this;
        }
    
        // 如果没有找到,则向右递归
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
    
        return resNode;
    
    }
    
    // 后序遍历查找
    public Node postOrderSearch(int no) {
    
        // 判断当前结点的左子结点是否为空,如果不为空,则递归前序遍历。找到结点则返回
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
    
        // 如果找到,就返回 resNode
        if (resNode != null) {
            return resNode;
        }
    
        // 如果没有找到,则向右递归
        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
    
        // 如果左右子树都没有找到,就比较当前结点
        System.out.println("后序遍历次数~~~");
        if (this.no == no) {
            return this;
        }
    
        return resNode;
    
    }
    
    
    
    
    
    /**
     * 以下三种遍历查找的方法写在 BinaryTree 类中
     */
    // 前序遍历查找
    public Node preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }
    
    // 前序遍历查找
    public Node infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    
    // 前序遍历查找
    public Node postOrderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        } else {
            return null;
        }
    }
    
    
    
    
    
    /**
     * 以下代码写在 BinaryTreeTest 类的 main 方法中
     */
    // 前序遍历查找
    System.out.println("前序遍历查找:");
    int findNum = 5;
    Node resNode1 = binaryTree.preOrderSearch(findNum);
    if (resNode1 != null) {
        System.out.printf("查找成功,信息为:no = %d , name = %s", resNode1.getNo(), resNode1.getName());
    } else {
        System.out.printf("没有找到编号为 %d 的结点!!!", findNum);
    }
    System.out.println("\n====================================");
    
    // 中序遍历查找
    System.out.println("中序遍历查找:");
    Node resNode2 = binaryTree.infixOrderSearch(findNum);
    if (resNode2 != null) {
        System.out.printf("查找成功,信息为:no = %d , name = %s", resNode2.getNo(), resNode2.getName());
    } else {
        System.out.printf("没有找到编号为 %d 的结点!!!", findNum);
    }
    System.out.println("\n====================================");
    
    // 后序遍历查找
    System.out.println("后序遍历查找:");
    Node resNode3 = binaryTree.postOrderSearch(findNum);
    if (resNode3 != null) {
        System.out.printf("查找成功,信息为:no = %d , name = %s", resNode3.getNo(), resNode3.getName());
    } else {
        System.out.printf("没有找到编号为 %d 的结点!!!", findNum);
    }
    

    二叉树的删除

    注意: 非叶子结点的 删除操作 遵照上图的规定,不同的删除策略会导致结果不同。

    二叉树的 删除操作 代码如下:

    // 删除结点,此方法加入到 Node 类中
    public void delNode(int no) {
    
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
    
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
    
        if (this.left != null) {
            this.left.delNode(no);
        }
    
        if (this.right != null) {
            this.right.delNode(no);
        }
    
    }
    
    
    
    // 删除结点,此方法加入到 BinaryTree 类中
    public void delNode(int no) {
        if (root != null) {
            if (root.getNo() == no) {
                root = null;
            } else {
                root.delNode(no);
            }
        } else {
            System.out.println("空树,不能删除!!!");
        }
    }
    
    
    
    // 以下代码加入到 BinaryTreeTest 类中的 main方法中
    System.out.println("删除前:");
    binaryTree.preOrder();
    binaryTree.delNode(findNum);
    System.out.println("删除后:");
    binaryTree.preOrder();
    

    顺序存储二叉树

    顺序存储二叉树 代码实现如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/6/29 20:56
     * @Description: 顺序存储二叉树的遍历
     */
    public class ArrayBinaryTreeTest {
        public static void main(String[] args) {
    
            int[] arr = {1, 2, 3, 4, 5, 6, 7};
            ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
            arrayBinaryTree.preOrder();
    
        }
    }
    
    // 编写 ArrayBinaryTree 类,实现顺序存储二叉树的遍历
    class ArrayBinaryTree {
    
        // 存储数据结点的数组
        private int[] arr;
    
        public ArrayBinaryTree(int[] arr) {
            this.arr = arr;
        }
    
        // 重载 preOrder 方法
        public void preOrder() {
            this.preOrder(0);
        }
    
        // 编写一个方法,完成顺手二叉树的前序遍历,index 是数组的索引
        public void preOrder(int index) {
    
            if (arr == null || arr.length == 0) {
                System.out.println("The array is empty !!!");
            }
    
            System.out.println(arr[index]);
            // 向左递归
            if ((index * 2 + 1) < arr.length) {
                preOrder(2 * index + 1);
            }
    
            // 向右递归
            if ((index * 2 + 2) < arr.length) {
                preOrder(2 * index + 2);
            }
    
        }
    }
    
    /** 输出结果:
     * 1
     * 2
     * 4
     * 5
     * 3
     * 6
     * 7
     */
    

    线索化二叉树

    在二叉树的结点上加上线索的二叉树 称为 线索二叉树 ,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历,使其变为线索二叉树的过程称为对二叉树进行线索化。 【———— 百度百科】

    线索化应用案例 代码如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/4 14:35
     * @Description: 线索化二叉树
     */
    public class ThreadedBinaryTreeTest {
        public static void main(String[] args) {
    
            // 测试中序线索二叉树
            Node node1 = 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, "亚瑟");
    
            node1.setLeft(node2);
            node1.setRight(node3);
            node2.setLeft(node4);
            node2.setRight(node5);
            node3.setLeft(node6);
    
            ThreadedBinaryTree tbt = new ThreadedBinaryTree();
            tbt.setRoot(node1);
            tbt.threadedNode();
    
            // 查看结果,以 10 号节点为例
            Node leftNode = node5.getLeft();
            Node rightNode = node5.getRight();
            System.out.println("10 号节点的前驱结点是: " + leftNode);
            System.out.println("10 号节点的后继结点是: " + rightNode);
    
        }
    }
    
    
    // 编写线索化二叉树类
    class ThreadedBinaryTree {
    
        private Node root;
        private Node pre = null;    // 指向当前节点的前驱结点
    
        public void setRoot(Node root) {
            this.root = root;
        }
    
        public void threadedNode() {
            this.threadedNode(root);
        }
    
        // 编写 “中序线索化” 方法,node 表示需要线索化的结点
        public void threadedNode(Node node) {
    
            // 如果 node == null ,无法线索化
            if (node == null) {
                System.out.println("node is null, so it is not be operated !!!");
                return;
            }
    
            /**
             * 中序线索化思路分析:
             * 1、先线索化左子树
             * 2、再线索化当前节点【这是重点,也是难点】
             * 3、最后线索化右子树
             */
            // 1、先线索化左子树
            threadedNode(node.getLeft());
            // 2、再线索化当前节点【这是重点,也是难点】
            if (node.getLeft() == null) {
                node.setLeft(pre);      // 让节点的左指针指向前驱结点
                node.setLeftType(1);    // 修改当前节点的左指针类型,指向前驱结点
            }
            // 处理后继节点
            if (pre != null && pre.getRight() == null) {
                pre.setRight(node);
                pre.setRightType(1);
            }
            // 每处理一个节点,就让当前节点成为下一个节点的前驱结点
            pre = node;
            // 3、最后线索化右子树
            threadedNode(node.getRight());
    
        }
    
        // 前序遍历
        public void preOrder() {
            if (this.root != null) {
                this.root.preOrder();
            } else {
                System.out.println("The Binary Tree is null !!!");
            }
        }
    
        // 中序遍历
        public void infixOrder() {
            if (this.root != null) {
                this.root.infixOrder();
            } else {
                System.out.println("The Binary Tree is null !!!");
            }
        }
    
        // 后序遍历
        public void postOrder() {
            if (this.root != null) {
                this.root.postOrder();
            } else {
                System.out.println("The Binary Tree is null !!!");
            }
        }
    
        // 前序遍历查找
        public Node preOrderSearch(int no) {
            if (root != null) {
                return root.preOrderSearch(no);
            } else {
                return null;
            }
        }
    
        // 前序遍历查找
        public Node infixOrderSearch(int no) {
            if (root != null) {
                return root.infixOrderSearch(no);
            } else {
                return null;
            }
        }
    
        // 前序遍历查找
        public Node postOrderSearch(int no) {
            if (root != null) {
                return root.postOrderSearch(no);
            } else {
                return null;
            }
        }
    
        // 删除结点
        public void delNode(int no) {
            if (root != null) {
                if (root.getNo() == no) {
                    root = null;
                } else {
                    root.delNode(no);
                }
            } else {
                System.out.println("空树,不能删除!!!");
            }
        }
    
    }
    
    
    // 编写结点类
    class Node {
    
        private int no;
        private String name;
        private Node left;
        private Node right;
        /**
         * 定义说明:
         * 1、leftType == 0 表示指向的是左子树,leftType == 1 表示指向的是前驱结点
         * 2、rightType == 0 表示指向的是右子树,rightType == 1 表示指向的是后继结点
         */
        private int leftType;
        private int rightType;
    
        public int getLeftType() {
            return leftType;
        }
    
        public void setLeftType(int leftType) {
            this.leftType = leftType;
        }
    
        public int getRightType() {
            return rightType;
        }
    
        public void setRightType(int rightType) {
            this.rightType = rightType;
        }
    
        public Node(int no, String name) {
            this.no = no;
            this.name = name;
        }
    
        public int getNo() {
            return no;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }
    
        public void setNo(int no) {
            this.no = no;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public Node getLeft() {
            return left;
        }
    
        public void setLeft(Node left) {
            this.left = left;
        }
    
        public Node getRight() {
            return right;
        }
    
        public void setRight(Node right) {
            this.right = right;
        }
    
        // 编写前序遍历方法
        public void preOrder() {
    
            // 输出父结点
            System.out.println(this);
    
            // 递归向左子树前序遍历
            if (this.left != null) {
                this.left.preOrder();
            }
    
            // 递归向右子树前序遍历
            if (this.right != null) {
                this.right.preOrder();
            }
    
        }
    
        // 编写中序遍历方法
        public void infixOrder() {
    
            // 递归向左子树前序遍历
            if (this.left != null) {
                this.left.infixOrder();
            }
    
            // 输出父结点
            System.out.println(this);
    
            // 递归向右子树前序遍历
            if (this.right != null) {
                this.right.infixOrder();
            }
    
        }
    
        // 编写后序遍历方法
        public void postOrder() {
    
            // 递归向左子树前序遍历
            if (this.left != null) {
                this.left.postOrder();
            }
    
            // 递归向右子树前序遍历
            if (this.right != null) {
                this.right.postOrder();
            }
    
            // 输出父结点
            System.out.println(this);
    
        }
    
        // 前序遍历查找
        public Node preOrderSearch(int no) {
    
            System.out.println("前序遍历次数~~~");
    
            if (this.no == no) {
                return this;
            }
    
            // 判断当前结点的左子结点是否为空,如果不为空,则递归前序遍历。找到结点则返回
            Node resNode = null;
            if (this.left != null) {
                resNode = this.left.preOrderSearch(no);
            }
    
            // 如果找到,就返回 resNode
            if (resNode != null) {
                return resNode;
            }
    
            // 如果没有找到,则向右递归
            if (this.right != null) {
                resNode = this.right.preOrderSearch(no);
            }
    
            return resNode;
    
        }
    
        // 中序遍历查找
        public Node infixOrderSearch(int no) {
    
            // 判断当前结点的左子结点是否为空,如果不为空,则递归前序遍历。找到结点则返回
            Node resNode = null;
            if (this.left != null) {
                resNode = this.left.infixOrderSearch(no);
            }
    
            // 如果找到,就返回 resNode
            if (resNode != null) {
                return resNode;
            }
    
            System.out.println("中序遍历次数~~~");
            if (this.no == no) {
                return this;
            }
    
            // 如果没有找到,则向右递归
            if (this.right != null) {
                resNode = this.right.infixOrderSearch(no);
            }
    
            return resNode;
    
        }
    
        // 后序遍历查找
        public Node postOrderSearch(int no) {
    
            // 判断当前结点的左子结点是否为空,如果不为空,则递归前序遍历。找到结点则返回
            Node resNode = null;
            if (this.left != null) {
                resNode = this.left.postOrderSearch(no);
            }
    
            // 如果找到,就返回 resNode
            if (resNode != null) {
                return resNode;
            }
    
            // 如果没有找到,则向右递归
            if (this.right != null) {
                resNode = this.right.postOrderSearch(no);
            }
    
            // 如果左右子树都没有找到,就比较当前结点
            System.out.println("后序遍历次数~~~");
            if (this.no == no) {
                return this;
            }
    
            return resNode;
    
        }
    
    
        // 删除结点
        public void delNode(int no) {
    
            if (this.left != null && this.left.no == no) {
                this.left = null;
                return;
            }
    
            if (this.right != null && this.right.no == no) {
                this.right = null;
                return;
            }
    
            if (this.left != null) {
                this.left.delNode(no);
            }
    
            if (this.right != null) {
                this.right.delNode(no);
            }
    
        }
    
    }
    

    线索化二叉树构建好了,那么如何遍历呢。如下图:

    线索化二叉树的遍历 代码如下:

    /**
     * 把以下语句写在 ThreadedBinaryTreeTest 类的 main 方法里面
     */
     
    tbt.threadedList();
    
    
    
    /**
     * 把以下方法写在 ThreadedBinaryTree 类里面
     */
     
    // 遍历中序线索化二叉树
    public void threadedList() {
    
        // 定义一个变量,存储当前遍历的节点,从 root 开始
        Node temp = root;
        while (temp != null) {
            // 1、一直循环,直到找到 leftType == 1 的结点,第一个找到的是 8 号结点
            // 2、后面随着遍历而变化,因为当 leftType == 1 时,说明该节点是线索化的
            while (temp.getLeftType() == 0) {
                temp = temp.getLeft();
            }
    
            // 打印当前节点
            System.out.println(temp);
    
            // 如果当前节点的右指针指向的是后继结点,就一直输出
            while (temp.getRightType() == 1){
                // 获取当前节点的后继节点
                temp = temp.getRight();
                System.out.println(temp);
            }
    
            // 替换这个遍历的节点
            temp = temp.getRight();
        }
    
    }
    
    
    /**
     * 输出结果:
     * Node{no=8, name='刘备'}
     * Node{no=3, name='廉颇'}
     * Node{no=10, name='妲己'}
     * Node{no=1, name='典韦'}
     * Node{no=14, name='亚瑟'}
     * Node{no=6, name='女娲'}
     */
    

    树的应用-堆

    堆的介绍

    堆(Heap) 是计算机科学中一类特殊的数据结构的统称。 通常是一个可以被看做一棵 完全二叉树 的数组对象。【———— 百度百科】


    堆的算法思想: 不必将值一个个地插入堆中,通过交换形成堆。假设一个小根堆的左、右子树都已是堆,并且根的元素名为 root ,其左右子节点为 leftright ,这种情况下,有两种可能:


    • root <= left 并且 root <= right ,此时堆已完成;
    • root >= left 或者 root >= right ,此时 root 应与两个子女中值较小的一个交换,结果得到一个堆,除非 root 仍然大于其新子女的一个或全部的两个。这种情况下,我们只需简单地继续这种将 root “拉下来”的过程,直至到达某一个层使它小于它的子女,或者它成了叶结点。

    堆排序

    堆排序 是一种选择排序 ,是利用 这种数据结构而设计的一种排序算法。具体介绍如下图:

    堆排序 的代码实现如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/4 22:53
     * @Description: 堆排序
     */
    public class HeapSort {
        public static void main(String[] args) {
    
            // 要求堆数组进行升序排序
            int[] arr = {4, 6, 8, 5, 9};
            heapSort(arr);
    
        }
    
        // 编写一个堆排序方法
        public static void heapSort(int[] arr) {
    
            int temp = 0;
            System.out.println("堆排序!");
    
            // 将无序序列构成堆
            for (int i = arr.length / 2 - 1; i >= 0; i--) {
                adjustHeap(arr, i, arr.length);
            }
    
            for (int j = arr.length - 1; j > 0; j--) {
                temp = arr[j];
                arr[j] = arr[0];
                arr[0] = temp;
                adjustHeap(arr, 0, j);
            }
    
            System.out.println(Arrays.toString(arr));  // [4, 5, 6, 8, 9]
    
        }
    
        /**
         * 将一个数组(二叉树)调整成大顶堆
         *
         * @param arr    代表待调整数组
         * @param i      代表非叶子节点再数组中的索引
         * @param length 表示堆多少个数组继续调整,length 是逐渐减少的
         */
        public static void adjustHeap(int[] arr, int i, int length) {
    
            int temp = arr[i];    // 取出当前元素的值,保存于 temp 中
    
            // 开始调整。k 是 i 节点的左子节点
            for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
                if ((k + 1) < length && arr[k] < arr[k + 1]) { // 说明左子节点小于右子节点
                    k++;
                }
                if (arr[k] > temp) {     // 如果子节点大于父节点
                    arr[i] = arr[k];   // 把较大的值赋给当前节点
                    i = k;             // i 指向 k ,继续比较
                } else {
                    break;
                }
            }
            // 当 for 循环结束后,我们已经将以 i 为父节点的树的最大值放到了最顶(局部,还不一定是大顶堆)
    
            arr[i] = temp;
    
        }
    }
    

    堆排序的性能测试 代码如下:

    public static void main(String[] args) {
    
        // 要求堆数组进行升序排序
        int[] arr = new int[8000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random() * 100000 + 1);
        }
    
        long start = System.currentTimeMillis();
        heapSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("排序 800 万个数据需要 " + (end - start) / 1000 + " 秒 " + (end - start) % 1000 + " 毫秒");
    
    }
    
    /**
     * 测试结果(平均时间:2s~3s):
     * 堆排序!
     * 排序 800 万个数据需要 2 秒 441 毫秒
     */
    

    赫夫曼树

    基本介绍

    赫夫曼树的基本介绍 如下图:

    赫夫曼树的构建

    赫夫曼树的构建 的代码实现如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/5 9:26
     * @Description: 哈夫曼树的构建
     */
    public class HuffmanTree {
        public static void main(String[] args) {
    
            int[] arr = {13, 7, 8, 3, 29, 6, 1};
            Node root = createHuffmanTree(arr);
            preOrder(root);
    
        }
    
        public static void preOrder(Node root) {
            if (root != null) {
                root.preOrder();
            } else {
                System.out.println("该赫夫曼树是空树,无法遍历~~~");
            }
        }
    
        // 创建赫夫曼树的方法
        public static Node createHuffmanTree(int[] arr) {
    
            List<Node> nodes = new ArrayList<>();
    
            for (int value : arr) {
                nodes.add(new Node(value));
            }
    
            while (nodes.size() > 1) {
    
                Collections.sort(nodes);
                Node leftNode = nodes.get(0);    // 取出权值最小的节点
                Node rightNode = nodes.get(1);   // 取出权值第二小的节点
    
                Node parent = new Node(leftNode.value + rightNode.value);
                parent.left = leftNode;
                parent.right = rightNode;
    
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                nodes.add(parent);
    
            }
    
            return nodes.get(0);
    
        }
    }
    
    // 创建 Node 节点类。为了能够持续排序,需要实现 Comparable 接口
    class Node implements Comparable<Node> {
    
        int value;    // 节点权值
        Node left;    // 指向左子树或左子节点
        Node right;   // 指向右子树或右子节点
    
        // 前序遍历
        public void preOrder() {
    
            System.out.println(this);
    
            if (this.left != null) {
                this.left.preOrder();
            }
    
            if (this.right != null) {
                this.right.preOrder();
            }
    
        }
    
        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }
    
        public Node(int value) {
            this.value = value;
        }
    
        @Override
        public int compareTo(Node o) {
            // 表示从小到大排序
            return this.value - o.value;
        }
    
    }
    

    赫夫曼编码

    基本介绍和原理

    赫夫曼编码的基本介绍和原理 如下图:

    赫夫曼应用-数据压缩

    数据压缩第一步: 把字符串转化为赫夫曼树。 代码如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/5 17:07
     * @Description: 赫夫曼应用之数据压缩
     */
    public class HuffmanCode {
        public static void main(String[] args) {
    
            String str = "i like like like java do you like a java";
            byte[] bytes = str.getBytes();
            System.out.println(bytes.length);
    
            List<Node> nodes = getNodes(bytes);
            Node root = createHuffmanTree(nodes);
            root.preOrder();
    
        }
    
        public static List<Node> getNodes(byte[] bytes) {
    
            List<Node> nodes = new ArrayList<>();
            Map<Byte, Integer> map = new HashMap<>();
    
            // 遍历 bytes ,统计每一个 byte 出现的次数
            for (byte val : bytes) {
                Integer count = map.get(val);
                if (count == null) {
                    map.put(val, 1);
                } else {
                    map.put(val, count + 1);
                }
            }
    
            // 把每一个键值对转换成 Node 对象,并加入到 nodes 集合
            for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
                nodes.add(new Node(entry.getKey(), entry.getValue()));
            }
    
            return nodes;
    
        }
    
        // 通过 list 创建对应的赫夫曼树
        public static Node createHuffmanTree(List<Node> nodes) {
    
            while (nodes.size() > 1) {
    
                Collections.sort(nodes);
                Node leftNode = nodes.get(0);    // 取出权值最小的节点
                Node rightNode = nodes.get(1);   // 取出权值第二小的节点
    
                Node parent = new Node(null, leftNode.weight + rightNode.weight);
                parent.left = leftNode;
                parent.right = rightNode;
    
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                nodes.add(parent);
    
            }
    
            return nodes.get(0);
    
        }
    }
    
    class Node implements Comparable<Node> {
    
        Byte data;    // 存放字符本身,比如 'a' => 97
        int weight;   // 存放权值,表示字符出现的个数
        Node left;    // 指向左子树或左子节点
        Node right;   // 指向右子树或右子节点
    
        public Node(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    
        @Override
        public String toString() {
            return "Node{" + "data=" + data + ", weight=" + weight + '}';
        }
    
        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    
        // 前序遍历
        public void preOrder() {
    
            System.out.println(this);
    
            if (this.left != null) {
                this.left.preOrder();
            }
    
            if (this.right != null) {
                this.right.preOrder();
            }
    
        }
    
    }
    

    数据压缩第二步: 根据赫夫曼树生成赫夫曼编码。 代码如下:

    /**
     * 以下所有方法都写在 HuffmanCode 类中
     */
    
    
    public static void main(String[] args) {
    
        String str = "i like like like java do you like a java";
        byte[] bytes = str.getBytes();
        System.out.println(bytes.length);
    
        List<Node> nodes = getNodes(bytes);
        Node root = createHuffmanTree(nodes);
        root.preOrder();
    
        getCodes(root);
        System.out.println(huffmanCodes);
    
    }
    
    // 重载 getCodes 方法,方便使用
    public static Map<Byte, String> getCodes(Node root) {
    
        if (root == null) {
            return null;
        }
    
        // 处理 root 左子树
        getCodes(root.left, "0", stringBuilder);
        // 处理 root 右子树
        getCodes(root.right, "1", stringBuilder);
    
        return huffmanCodes;
    
    }
    
    // 生成赫夫曼树对应的赫夫曼编码,将赫夫曼编码放在 Map<Byte, String> 中
    static Map<Byte, String> huffmanCodes = new HashMap<>();
    // 在生成的赫夫曼编码表时,需要拼接路径,所以定义一个 StringBuilder
    static StringBuilder stringBuilder = new StringBuilder();
    
    /**
     * 得到赫夫曼编码,并存入 huffmanCodes 集合中
     * @param node          传入的节点
     * @param code          表示路径:左子节点是 0 ,右子节点是 1
     * @param stringBuilder 用于拼接路径
     */
    public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
    
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);  // 将 code 加入到 stringBuilder1
    
        if (node != null) {  // 如果 node == null ,那么就不处理
            if (node.data == null) {  // 非叶子节点
                // 向左递归
                getCodes(node.left, "0", stringBuilder1);
                // 向右递归
                getCodes(node.right, "1", stringBuilder1);
            } else {  // 说明是一个叶子节点
                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }
    
    }
    

    数据压缩第三步: 根据赫夫曼编码压缩数据(无损压缩)。 完整的代码如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/5 17:07
     * @Description: 赫夫曼应用之数据压缩
     */
    public class HuffmanCode {
        public static void main(String[] args) {
    
            String str = "i like like like java do you like a java";
            byte[] bytes = str.getBytes();
            System.out.println("压缩前的长度是:" + bytes.length);
    
            /*List<Node> nodes = getNodes(bytes);
            Node root = createHuffmanTree(nodes);
            root.preOrder();
    
            getCodes(root);
            System.out.println(huffmanCodes);
    
            byte[] zip = zip(bytes, huffmanCodes);
            System.out.println(Arrays.toString(zip));*/
    
            byte[] huffmanBytes = huffmanZip(bytes);
            System.out.println("压缩后的结果是:" + Arrays.toString(huffmanBytes));
            System.out.println("压缩后的长度是:" + huffmanBytes.length);
            System.out.println("求出的压缩率是:" + (float) (bytes.length - huffmanBytes.length) / bytes.length * 100 + "%");
    
        }
    
        public static byte[] huffmanZip(byte[] bytes) {
    
            List<Node> nodes = getNodes(bytes);
    
            // 根据 nodes 创建的赫夫曼树
            Node root = createHuffmanTree(nodes);
    
            // 对应的赫夫曼编码
            Map<Byte, String> huffmanCodes = getCodes(root);
    
            // 根据赫夫曼编码,压缩得到压缩后的赫夫曼编码字节数组
            byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
    
            // 返回字节数组
            return huffmanCodeBytes;
    
        }
    
    
        /**
         * 将字符串对应的 byte[] 数组,通过生成的赫夫曼编码表,返回一个压缩后的 byte[]
         * @param bytes        原始的字符串对应的 byte[]
         * @param huffmanCodes 生成的赫夫曼编码 map
         * @return 返回赫夫曼编码处理后的 byte[]
         */
        public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
    
            // 利用 huffmanCodes 将 bytes 转成赫夫曼编码对应的字符串
            StringBuilder stringBuilder = new StringBuilder();
    
            // 遍历 bytes 数组
            for (byte aByte : bytes) {
                stringBuilder.append(huffmanCodes.get(aByte));
            }
    
            /*// 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
            System.out.println(stringBuilder.toString());*/
    
            // 统计返回 byte[] huffmanCodeBytes 的长度
            int len;
            if (stringBuilder.length() % 8 == 0) {
                len = stringBuilder.length() / 8;
            } else {
                len = stringBuilder.length() / 8 + 1;
            }
    
            // 创建存储压缩后的 byte 数组 huffmanCodeBytes
            byte[] huffmanCodeBytes = new byte[len];
            int index = 0;
    
            for (int i = 0; i < stringBuilder.length(); i += 8) {
                String strByte;
                if (i + 8 > stringBuilder.length()) {
                    strByte = stringBuilder.substring(i);
                } else {
                    strByte = stringBuilder.substring(i, i + 8);
                }
    
                // 将 strByte 转成一个 byte ,放入到 huffmanCodeBytes 数组中
                huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
                index++;
            }
    
            return huffmanCodeBytes;
    
        }
    
        // 重载 getCodes 方法,方便使用
        public static Map<Byte, String> getCodes(Node root) {
    
            if (root == null) {
                return null;
            }
    
            // 处理 root 左子树
            getCodes(root.left, "0", stringBuilder);
            // 处理 root 右子树
            getCodes(root.right, "1", stringBuilder);
    
            return huffmanCodes;
    
        }
    
        // 生成赫夫曼树对应的赫夫曼编码,将赫夫曼编码放在 Map<Byte, String> 中
        static Map<Byte, String> huffmanCodes = new HashMap<>();
        // 在生成的赫夫曼编码表时,需要拼接路径,所以定义一个 StringBuilder
        static StringBuilder stringBuilder = new StringBuilder();
    
        /**
         * 得到赫夫曼编码,并存入 huffmanCodes 集合中
         * @param node          传入的节点
         * @param code          表示路径:左子节点是 0 ,右子节点是 1
         * @param stringBuilder 用于拼接路径
         */
        public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
    
            StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
            stringBuilder1.append(code);  // 将 code 加入到 stringBuilder1
    
            if (node != null) {  // 如果 node == null ,那么就不处理
                if (node.data == null) {  // 非叶子节点
                    // 向左递归
                    getCodes(node.left, "0", stringBuilder1);
                    // 向右递归
                    getCodes(node.right, "1", stringBuilder1);
                } else {  // 说明是一个叶子节点
                    huffmanCodes.put(node.data, stringBuilder1.toString());
                }
            }
    
        }
    
        public static List<Node> getNodes(byte[] bytes) {
    
            List<Node> nodes = new ArrayList<>();
            Map<Byte, Integer> map = new HashMap<>();
    
            // 遍历 bytes ,统计每一个 byte 出现的次数
            for (byte val : bytes) {
                Integer count = map.get(val);
                if (count == null) {
                    map.put(val, 1);
                } else {
                    map.put(val, count + 1);
                }
            }
    
            // 把每一个键值对转换成 Node 对象,并加入到 nodes 集合
            for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
                nodes.add(new Node(entry.getKey(), entry.getValue()));
            }
    
            return nodes;
    
        }
    
        // 通过 list 创建对应的赫夫曼树
        public static Node createHuffmanTree(List<Node> nodes) {
    
            while (nodes.size() > 1) {
    
                Collections.sort(nodes);
                Node leftNode = nodes.get(0);    // 取出权值最小的节点
                Node rightNode = nodes.get(1);   // 取出权值第二小的节点
    
                Node parent = new Node(null, leftNode.weight + rightNode.weight);
                parent.left = leftNode;
                parent.right = rightNode;
    
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                nodes.add(parent);
    
            }
    
            return nodes.get(0);
    
        }
    }
    
    class Node implements Comparable<Node> {
    
        Byte data;    // 存放字符本身,比如 'a' => 97
        int weight;   // 存放权值,表示字符出现的个数
        Node left;    // 指向左子树或左子节点
        Node right;   // 指向右子树或右子节点
    
        public Node(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    
        @Override
        public String toString() {
            return "Node{" + "data=" + data + ", weight=" + weight + '}';
        }
    
        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    
        // 前序遍历
        public void preOrder() {
    
            System.out.println(this);
    
            if (this.left != null) {
                this.left.preOrder();
            }
    
            if (this.right != null) {
                this.right.preOrder();
            }
    
        }
    
    }
    

    赫夫曼应用-数据解压

    数据的解压 的代码如下:

    /**
     * 将以下代码全部写入到 HuffmanCode 类中,main 方法将替换原先的 main 方法
     */
    
    
    public static void main(String[] args) {
    
        String str = "i like like like java do you like a java";
        byte[] bytes = str.getBytes();
        System.out.println("压缩前的长度是:" + bytes.length);
    
        /*List<Node> nodes = getNodes(bytes);
        Node root = createHuffmanTree(nodes);
        root.preOrder();
    
        getCodes(root);
        System.out.println(huffmanCodes);
    
        byte[] zip = zip(bytes, huffmanCodes);
        System.out.println(Arrays.toString(zip));*/
    
        byte[] huffmanBytes = huffmanZip(bytes);
        System.out.println("压缩后的结果是:" + Arrays.toString(huffmanBytes));
        System.out.println("压缩后的长度是:" + huffmanBytes.length);
        System.out.println("求出的压缩率是:" + (float) (bytes.length - huffmanBytes.length) / bytes.length * 100 + "%");
    
        byte[] sourceStr = decode(huffmanCodes, huffmanBytes);
        System.out.println(new String(sourceStr));
    
    }
    
    /**
     * 数据的解压:
     * 1、将压缩后的字节数组转化成二进制字符串
     * 2、将二进制字符串转化成对应的赫夫曼编码
     * 3、将赫夫曼编码转化成最开始的数据,即 i like like ……
     * 4、huffmanCodes 表示赫夫曼编码表 map ,huffmanBytes 表示赫夫曼编码后得到的压缩数组
     * 5、返回值就是初始字符串所对应的数组
     */
    public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
    
        StringBuilder stringBuilder = new StringBuilder();
        // 将 byte 数组转成二进制的字符串
    
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte huffmanByte = huffmanBytes[i];
            // 判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, huffmanByte));
        }
        
        System.out.println(stringBuilder.toString());
    
        // 把字符串按照指定的赫夫曼编码进行节码
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
        
        System.out.println(map);
    
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length();) {
            int count = 1;
            boolean flag = true;
            Byte b = null;
    
            while (flag) {
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if (b == null) {
                    // 没有匹配到
                    count++;
                } else {
                    // 匹配到了
                    flag = false;
                }
            }
    
            list.add(b);
            i += count;
        }
    
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = list.get(i);
        }
    
        return bytes;
    
    }
    
    // 将一个 byte 转成一个二进制的字符串
    public static String byteToBitString(boolean flag, byte b) {
    
        // 使用变量保存 b ,将 b 转成 int 类型
        int temp = b;
    
        // 如果是整数,存在补高位。这里和 原码、反码和补码有关
        if (flag) {
            temp |= 256;
        }
    
        String str = Integer.toBinaryString(temp);
    
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    
    }
    

    赫夫曼应用-文件压缩

    课件图片下载 课件图片下载

    文件压缩 代码如下:

    /**
     * 将以下代码全部写入到 HuffmanCode 类中,main 方法将替换原先的 main 方法
     */
    
    
    public static void main(String[] args) {
    
        String str = "i like like like java do you like a java";
        byte[] bytes = str.getBytes();
        System.out.println("压缩前的长度是:" + bytes.length);
    
        /*List<Node> nodes = getNodes(bytes);
        Node root = createHuffmanTree(nodes);
        root.preOrder();
    
        getCodes(root);
        System.out.println(huffmanCodes);
    
        byte[] zip = zip(bytes, huffmanCodes);
        System.out.println(Arrays.toString(zip));*/
    
        /*byte[] huffmanBytes = huffmanZip(bytes);
        System.out.println("压缩后的结果是:" + Arrays.toString(huffmanBytes));
        System.out.println("压缩后的长度是:" + huffmanBytes.length);
        System.out.println("求出的压缩率是:" + (float) (bytes.length - huffmanBytes.length) / bytes.length * 100 + "%");
    
        byte[] sourceStr = decode(huffmanCodes, huffmanBytes);
        System.out.println(new String(sourceStr));*/
    
        String src = "F:\\src.jpg";
        String desc = "F:\\dest.zip";
        zipFile(src, desc);
    
    }
    
    /**
     * 将一个文件进行压缩
     *
     * @param srcFile  需要压缩的文件的全路径
     * @param destFile 压缩后,压缩文件的保存目录
     */
    public static void zipFile(String srcFile, String destFile) {
    
        // 创建文输出流
        OutputStream os = null;
        ObjectOutputStream oos = null;
        // 创建文件输入流
        FileInputStream fis = null;
    
        try {
    
            fis = new FileInputStream(srcFile);
            // 创建一个和源文件大小一样的 byte[] 数组
            byte[] bytes = new byte[fis.available()];
            // 读取文件
            fis.read(bytes);
            // 对文件压缩
            byte[] huffmanBytes = huffmanZip(bytes);
            // 创建文件输出流,存放压缩文件
            os = new FileOutputStream(destFile);
            // 创建一个和文件输出流关联的 ObjectOutputStream
            oos = new ObjectOutputStream(os);
            // 把赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanBytes);
            // 这里我们以对象流的方式写入赫夫曼编码,是为了以后我们恢复源文件时使用。注意:一定要把赫夫曼编码写入压缩文件
            oos.writeObject(huffmanCodes);
    
        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            try {
                oos.close();
                os.close();
                fis.close();
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
        }
    
    }
    

    赫夫曼应用-文件解压

    文件解压 代码如下:

    /**
     * 将以下代码全部写入到 HuffmanCode 类中,main 方法将替换原先的 main 方法
     */
    
    
    public static void main(String[] args) {
    
        String str = "i like like like java do you like a java";
        byte[] bytes = str.getBytes();
        System.out.println("压缩前的长度是:" + bytes.length);
    
        /*List<Node> nodes = getNodes(bytes);
        Node root = createHuffmanTree(nodes);
        root.preOrder();
    
        getCodes(root);
        System.out.println(huffmanCodes);
    
        byte[] zip = zip(bytes, huffmanCodes);
        System.out.println(Arrays.toString(zip));*/
    
        /*byte[] huffmanBytes = huffmanZip(bytes);
        System.out.println("压缩后的结果是:" + Arrays.toString(huffmanBytes));
        System.out.println("压缩后的长度是:" + huffmanBytes.length);
        System.out.println("求出的压缩率是:" + (float) (bytes.length - huffmanBytes.length) / bytes.length * 100 + "%");
    
        byte[] sourceStr = decode(huffmanCodes, huffmanBytes);
        System.out.println(new String(sourceStr));*/
    
        String src = "F:\\src.jpg";
        String desc = "F:\\dest.zip";
        //zipFile(src, desc);
        unZipFile(desc, src);
    
    }
    
    /**
     * 将一个文件进行解压操作
     *
     * @param zipFile  准备解压的文件
     * @param destFile 将文件解压到哪个路径
     */
    public static void unZipFile(String zipFile, String destFile) {
    
        // 定义文件输入流
        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(destFile);
            // 写数据到 destFile 文件
            os.write(bytes);
    
        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (Exception e) {
                System.out.println(e.getMessage());
            }
        }
    }
    

    赫夫曼编码注意事项

    赫夫曼编码部分的所有完整代码如下:

    import java.io.*;
    import java.util.*;
    
    /**
     * @Author: guoshizhan
     * @Create: 2020/7/5 17:07
     * @Description: 赫夫曼应用之数据压缩
     */
    public class HuffmanCode {
    
        // 生成赫夫曼树对应的赫夫曼编码,将赫夫曼编码放在 Map<Byte, String> 中
        static Map<Byte, String> huffmanCodes = new HashMap<>();
        // 在生成的赫夫曼编码表时,需要拼接路径,所以定义一个 StringBuilder
        static StringBuilder stringBuilder = new StringBuilder();
    
        public static void main(String[] args) {
    
            String str = "i like like like java do you like a java";
            byte[] bytes = str.getBytes();
            System.out.println("压缩前的长度是:" + bytes.length);
    
            /*List<Node> nodes = getNodes(bytes);
            Node root = createHuffmanTree(nodes);
            root.preOrder();
    
            getCodes(root);
            System.out.println(huffmanCodes);
    
            byte[] zip = zip(bytes, huffmanCodes);
            System.out.println(Arrays.toString(zip));*/
    
            /*byte[] huffmanBytes = huffmanZip(bytes);
            System.out.println("压缩后的结果是:" + Arrays.toString(huffmanBytes));
            System.out.println("压缩后的长度是:" + huffmanBytes.length);
            System.out.println("求出的压缩率是:" + (float) (bytes.length - huffmanBytes.length) / bytes.length * 100 + "%");
    
            byte[] sourceStr = decode(huffmanCodes, huffmanBytes);
            System.out.println(new String(sourceStr));*/
    
            String src = "F:\\src2.jpg";
            String desc = "F:\\dest.zip";
            //zipFile(src, desc);
            unZipFile(desc, src);
    
        }
    
        /**
         * 将一个文件进行解压操作
         *
         * @param zipFile  准备解压的文件
         * @param destFile 将文件解压到哪个路径
         */
        public static void unZipFile(String zipFile, String destFile) {
    
            // 定义文件输入流
            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(destFile);
                // 写数据到 destFile 文件
                os.write(bytes);
    
            } catch (Exception e) {
                System.out.println(e.getMessage());
            } finally {
                try {
                    os.close();
                    ois.close();
                    is.close();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
            }
        }
    
        /**
         * 将一个文件进行压缩
         *
         * @param srcFile  需要压缩的文件的全路径
         * @param destFile 压缩后,压缩文件的保存目录
         */
        public static void zipFile(String srcFile, String destFile) {
    
            // 创建文输出流
            OutputStream os = null;
            ObjectOutputStream oos = null;
            // 创建文件输入流
            FileInputStream fis = null;
    
            try {
    
                fis = new FileInputStream(srcFile);
                // 创建一个和源文件大小一样的 byte[] 数组
                byte[] bytes = new byte[fis.available()];
                // 读取文件
                fis.read(bytes);
                // 对文件压缩
                byte[] huffmanBytes = huffmanZip(bytes);
                // 创建文件输出流,存放压缩文件
                os = new FileOutputStream(destFile);
                // 创建一个和文件输出流关联的 ObjectOutputStream
                oos = new ObjectOutputStream(os);
                // 把赫夫曼编码后的字节数组写入压缩文件
                oos.writeObject(huffmanBytes);
                // 这里我们以对象流的方式写入赫夫曼编码,是为了以后我们恢复源文件时使用。注意:一定要把赫夫曼编码写入压缩文件
                oos.writeObject(huffmanCodes);
    
            } catch (Exception e) {
                System.out.println(e.getMessage());
            } finally {
                try {
                    oos.close();
                    os.close();
                    fis.close();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
            }
    
        }
    
        /**
         * 数据的解压:
         * 1、将压缩后的字节数组转化成二进制字符串
         * 2、将二进制字符串转化成对应的赫夫曼编码
         * 3、将赫夫曼编码转化成最开始的数据,即 i like like ……
         * 4、huffmanCodes 表示赫夫曼编码表 map ,huffmanBytes 表示赫夫曼编码后得到的压缩数组
         * 5、返回值就是初始字符串所对应的数组
         */
        public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
    
            StringBuilder stringBuilder = new StringBuilder();
            // 将 byte 数组转成二进制的字符串
    
            for (int i = 0; i < huffmanBytes.length; i++) {
                byte huffmanByte = huffmanBytes[i];
                // 判断是不是最后一个字节
                boolean flag = (i == huffmanBytes.length - 1);
                stringBuilder.append(byteToBitString(!flag, huffmanByte));
            }
    
            System.out.println(stringBuilder.toString());
    
            // 把字符串按照指定的赫夫曼编码进行节码
            Map<String, Byte> map = new HashMap<>();
            for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
                map.put(entry.getValue(), entry.getKey());
            }
    
            System.out.println(map);
    
            List<Byte> list = new ArrayList<>();
            for (int i = 0; i < stringBuilder.length(); ) {
                int count = 1;
                boolean flag = true;
                Byte b = null;
    
                while (flag) {
                    String key = stringBuilder.substring(i, i + count);
                    b = map.get(key);
                    if (b == null) {
                        // 没有匹配到
                        count++;
                    } else {
                        // 匹配到了
                        flag = false;
                    }
                }
    
                list.add(b);
                i += count;
            }
    
            byte[] bytes = new byte[list.size()];
            for (int i = 0; i < bytes.length; i++) {
                bytes[i] = list.get(i);
            }
    
            return bytes;
    
        }
    
        // 将一个 byte 转成一个二进制的字符串
        public static String byteToBitString(boolean flag, byte b) {
    
            // 使用变量保存 b ,将 b 转成 int 类型
            int temp = b;
    
            // 如果是整数,存在补高位。这里和 原码、反码和补码有关
            if (flag) {
                temp |= 256;
            }
    
            String str = Integer.toBinaryString(temp);
    
            if (flag) {
                return str.substring(str.length() - 8);
            } else {
                return str;
            }
    
        }
    
        public static byte[] huffmanZip(byte[] bytes) {
    
            List<Node> nodes = getNodes(bytes);
    
            // 根据 nodes 创建的赫夫曼树
            Node root = createHuffmanTree(nodes);
    
            // 对应的赫夫曼编码
            Map<Byte, String> huffmanCodes = getCodes(root);
    
            // 根据赫夫曼编码,压缩得到压缩后的赫夫曼编码字节数组
            byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
    
            // 返回字节数组
            return huffmanCodeBytes;
    
        }
    
    
        /**
         * 将字符串对应的 byte[] 数组,通过生成的赫夫曼编码表,返回一个压缩后的 byte[]
         *
         * @param bytes        原始的字符串对应的 byte[]
         * @param huffmanCodes 生成的赫夫曼编码 map
         * @return 返回赫夫曼编码处理后的 byte[]
         */
        public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
    
            // 利用 huffmanCodes 将 bytes 转成赫夫曼编码对应的字符串
            StringBuilder stringBuilder = new StringBuilder();
    
            // 遍历 bytes 数组
            for (byte aByte : bytes) {
                stringBuilder.append(huffmanCodes.get(aByte));
            }
    
            // 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
            System.out.println(stringBuilder.toString());
    
            // 统计返回 byte[] huffmanCodeBytes 的长度
            int len;
            if (stringBuilder.length() % 8 == 0) {
                len = stringBuilder.length() / 8;
            } else {
                len = stringBuilder.length() / 8 + 1;
            }
    
            // 创建存储压缩后的 byte 数组 huffmanCodeBytes
            byte[] huffmanCodeBytes = new byte[len];
            int index = 0;
    
            for (int i = 0; i < stringBuilder.length(); i += 8) {
                String strByte;
                if (i + 8 > stringBuilder.length()) {
                    strByte = stringBuilder.substring(i);
                } else {
                    strByte = stringBuilder.substring(i, i + 8);
                }
    
                // 将 strByte 转成一个 byte ,放入到 huffmanCodeBytes 数组中
                huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
                index++;
            }
    
            return huffmanCodeBytes;
    
        }
    
        // 重载 getCodes 方法,方便使用
        public static Map<Byte, String> getCodes(Node root) {
    
            if (root == null) {
                return null;
            }
    
            // 处理 root 左子树
            getCodes(root.left, "0", stringBuilder);
            // 处理 root 右子树
            getCodes(root.right, "1", stringBuilder);
    
            return huffmanCodes;
    
        }
    
        /**
         * 得到赫夫曼编码,并存入 huffmanCodes 集合中
         *
         * @param node          传入的节点
         * @param code          表示路径:左子节点是 0 ,右子节点是 1
         * @param stringBuilder 用于拼接路径
         */
        public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
    
            StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
            stringBuilder1.append(code);  // 将 code 加入到 stringBuilder1
    
            if (node != null) {  // 如果 node == null ,那么就不处理
                if (node.data == null) {  // 非叶子节点
                    // 向左递归
                    getCodes(node.left, "0", stringBuilder1);
                    // 向右递归
                    getCodes(node.right, "1", stringBuilder1);
                } else {  // 说明是一个叶子节点
                    huffmanCodes.put(node.data, stringBuilder1.toString());
                }
            }
    
        }
    
        public static List<Node> getNodes(byte[] bytes) {
    
            List<Node> nodes = new ArrayList<>();
            Map<Byte, Integer> map = new HashMap<>();
    
            // 遍历 bytes ,统计每一个 byte 出现的次数
            for (byte val : bytes) {
                Integer count = map.get(val);
                if (count == null) {
                    map.put(val, 1);
                } else {
                    map.put(val, count + 1);
                }
            }
    
            // 把每一个键值对转换成 Node 对象,并加入到 nodes 集合
            for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
                nodes.add(new Node(entry.getKey(), entry.getValue()));
            }
    
            return nodes;
    
        }
    
        // 通过 list 创建对应的赫夫曼树
        public static Node createHuffmanTree(List<Node> nodes) {
    
            while (nodes.size() > 1) {
    
                Collections.sort(nodes);
                Node leftNode = nodes.get(0);    // 取出权值最小的节点
                Node rightNode = nodes.get(1);   // 取出权值第二小的节点
    
                Node parent = new Node(null, leftNode.weight + rightNode.weight);
                parent.left = leftNode;
                parent.right = rightNode;
    
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                nodes.add(parent);
    
            }
    
            return nodes.get(0);
    
        }
    }
    
    class Node implements Comparable<Node> {
    
        Byte data;    // 存放字符本身,比如 'a' => 97
        int weight;   // 存放权值,表示字符出现的个数
        Node left;    // 指向左子树或左子节点
        Node right;   // 指向右子树或右子节点
    
        public Node(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    
        @Override
        public String toString() {
            return "Node{" + "data=" + data + ", weight=" + weight + '}';
        }
    
        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    
        // 前序遍历
        public void preOrder() {
    
            System.out.println(this);
    
            if (this.left != null) {
                this.left.preOrder();
            }
    
            if (this.right != null) {
                this.right.preOrder();
            }
    
        }
    
    }
    

    二叉排序树(BST)

    基本介绍

    二叉排序树 整合了 数组链表 的优点 ,从而对数据的 CRUD 操作更为高效。详情如下:

    创建和遍历

    二叉排序树的创建和遍历 代码如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/6 16:17
     * @Description: 二叉排序树(BST)的创建和遍历
     */
    public class BinarySortTreeTest {
        public static void main(String[] args) {
    
            int[] arr = {7, 3, 10, 12, 5, 1, 9};
            BinarySortTree binarySortTree = new BinarySortTree();
    
            for (int i = 0; i < arr.length; i++) {
                binarySortTree.add(new Node(arr[i]));
            }
    
            binarySortTree.infixOrder();
    
        }
    }
    
    
    // 创建二叉排序树类 BinarySortTree
    class BinarySortTree {
    
        // 定义根节点
        private Node root;
    
        // 添加节点的方法
        public void add(Node node) {
            if (root == null) {
                root = node;
            } else {
                root.add(node);
            }
        }
    
        // 中序遍历的方法
        public void infixOrder() {
            if (root != null) {
                root.infixOrder();
            } else {
                System.out.println("The Binary Sort Tree is empty, so it can not be traversal!!!");
            }
        }
    
    }
    
    // 创建 Node 节点类
    class Node {
    
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        // 添加节点:使用递归的方式添加节点。注意:需要满足二叉排序树的要求
        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 {  // 添加的节点大于当前节点的值
                // 如果当前节点的左子节点为 null
                if (this.right == null) {
                    this.right = node;
                } else {
                    // 递归向左子树添加
                    this.right.add(node);
                }
            }
    
        }
    
        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }
    
        // 中序遍历
        public void infixOrder() {
    
            if (this.left != null) {
                this.left.infixOrder();
            }
    
            System.out.println(this);
    
            if (this.right != null) {
                this.right.infixOrder();
            }
    
        }
    
    }
    

    删除节点

    二叉排序树删除节点的情况和思路分析 如下图:

    第一种情况: 删除叶子节点 。相关代码如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/6 16:17
     * @Description: 二叉排序树(BST)的创建和遍历
     */
    public class BinarySortTreeTest {
        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]));
            }
    
            binarySortTree.infixOrder();
            binarySortTree.delNode(12);
            System.out.println("======================");
            binarySortTree.infixOrder();
    
        }
    }
    
    
    // 创建二叉排序树类 BinarySortTree
    class BinarySortTree {
    
        // 定义根节点
        private Node root;
    
        // 查找要删除的节点
        public Node search(int value) {
            if (root == null) {
                return null;
            } else {
                return root.search(value);
            }
        }
    
        // 查找父节点
        public Node searchParent(int value) {
            if (root == null) {
                return null;
            } else {
                return root.searchParent(value);
            }
        }
    
        // 删除节点,这个方法才是核心
        public void delNode(int value) {
    
            if (root == null) {
                return;
            } else {
    
                // 先找到要删除的节点 targetNode
                Node targetNode = search(value);
    
                // 如果没有找到
                if (targetNode == null) {
                    return;
                }
    
                // 如果这颗二叉树只有一个节点
                if (root.left == null && root.right == null) {
                    root = null;
                    return;
                }
    
                // 去找 targetNode 的父节点
                Node parent = searchParent(value);
    
                // 如果要删除的节点是叶子节点
                if (targetNode.left == null && targetNode.right == null) {
                    // 判断 targetNode 是父节点的左子节点还是右子节点
                    if (parent.left != null && parent.left.value == value) {  // 是左子节点
                        parent.left = null;
                    } else if (parent.right != null && parent.right.value == value) {  // 是右子节点
                        parent.right = null;
                    }
                }
    
            }
    
        }
    
        // 添加节点的方法
        public void add(Node node) {
            if (root == null) {
                root = node;
            } else {
                root.add(node);
            }
        }
    
        // 中序遍历的方法
        public void infixOrder() {
            if (root != null) {
                root.infixOrder();
            } else {
                System.out.println("The Binary Sort Tree is empty, so it can not be traversal!!!");
            }
        }
    
    }
    
    // 创建 Node 节点类
    class Node {
    
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        /**
         * 查找要删除的节点
         * @param value 需要删除的节点的值
         * @return 如果找到,则返回该节点,否则返回 null
         */
        public Node search(int value) {
            if (value == this.value) {
                return this;
            } else if (value < this.value) {  // 向左子树递归查找
                // 如果左子节点为空
                if (this.left == null) {
                    return null;
                }
                return this.left.search(value);
            } else {  // 向右子树递归查找
                if (this.right == null) {
                    return null;
                }
                return this.right.search(value);
            }
        }
    
        /**
         * 查找要删除节点的父节点
         * @param value 要查找节点的值
         * @return 找到就返回父节点,否则返回 null
         */
        public Node searchParent(int value) {
            // 如果当前节点就是要删除的节点的父节点,就返回
            if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
                return this;
            } else {
    
                // 如果查找的值小于当前节点的值,并且当前节点的左子节点不为空
                if (value < this.value && this.left != null) {
                    return this.left.searchParent(value);  // 向左子树递归查找
                } else if (value >= this.value && this.right != null) {
                    return this.right.searchParent(value); // 向右子树递归查找
                } else {
                    return null;  // 没有找到父节点
                }
            }
        }
    
        // 添加节点:使用递归的方式添加节点。注意:需要满足二叉排序树的要求
        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 {  // 添加的节点大于当前节点的值
                // 如果当前节点的左子节点为 null
                if (this.right == null) {
                    this.right = node;
                } else {
                    // 递归向左子树添加
                    this.right.add(node);
                }
            }
    
        }
    
        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }
    
        // 中序遍历
        public void infixOrder() {
    
            if (this.left != null) {
                this.left.infixOrder();
            }
    
            System.out.println(this);
    
            if (this.right != null) {
                this.right.infixOrder();
            }
    
        }
    
    }
    

    第二种情况: 删除只有一颗子树的节点 。相关代码如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/6 16:17
     * @Description: 二叉排序树(BST)的创建和遍历
     */
    public class BinarySortTreeTest {
        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]));
            }
    
            binarySortTree.infixOrder();
            binarySortTree.delNode(1);
            System.out.println("======================");
            binarySortTree.infixOrder();
    
        }
    }
    
    
    // 创建二叉排序树类 BinarySortTree
    class BinarySortTree {
    
        // 定义根节点
        private Node root;
    
        // 查找要删除的节点
        public Node search(int value) {
            if (root == null) {
                return null;
            } else {
                return root.search(value);
            }
        }
    
        // 查找父节点
        public Node searchParent(int value) {
            if (root == null) {
                return null;
            } else {
                return root.searchParent(value);
            }
        }
    
        // 删除节点,这个方法才是核心
        public void delNode(int value) {
    
            if (root == null) {
                return;
            } else {
    
                // 先找到要删除的节点 targetNode
                Node targetNode = search(value);
    
                // 如果没有找到
                if (targetNode == null) {
                    return;
                }
    
                // 如果这颗二叉树只有一个节点
                if (root.left == null && root.right == null) {
                    root = null;
                    return;
                }
    
                // 去找 targetNode 的父节点
                Node parent = searchParent(value);
    
                // 如果要删除的节点是叶子节点
                if (targetNode.left == null && targetNode.right == null) {
    
                    // 判断 targetNode 是父节点的左子节点还是右子节点
                    if (parent.left != null && parent.left.value == value) {  // 是左子节点
                        parent.left = null;
                    } else if (parent.right != null && parent.right.value == value) {  // 是右子节点
                        parent.right = null;
                    }
    
                } else if (targetNode.left != null && targetNode.right != null) {  // 删除有两颗子树的节点
                    /**
                     * 此处是第三种情况,暂时不写内容
                     */
                } else {  // 删除只有一颗子树的节点
    
                    // 如果要删除的节点有左子节点
                    if (targetNode.left != null) {
    
                        // 如果 targetNode 是 parent 的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {  // targetNode 是 parent 的右子节点
                            parent.right = targetNode.left;
                        }
    
                    } else {
                        
                        // 如果 targetNode 是 parent 的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else {  // 如果 targetNode 是 parent 的右子节点
                            parent.right = targetNode.right;
                        }
    
                    }
    
                }
    
            }
    
        }
    
        // 添加节点的方法
        public void add(Node node) {
            if (root == null) {
                root = node;
            } else {
                root.add(node);
            }
        }
    
        // 中序遍历的方法
        public void infixOrder() {
            if (root != null) {
                root.infixOrder();
            } else {
                System.out.println("The Binary Sort Tree is empty, so it can not be traversal!!!");
            }
        }
    
    }
    
    // 创建 Node 节点类
    class Node {
    
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        /**
         * 查找要删除的节点
         *
         * @param value 需要删除的节点的值
         * @return 如果找到,则返回该节点,否则返回 null
         */
        public Node search(int value) {
            if (value == this.value) {
                return this;
            } else if (value < this.value) {  // 向左子树递归查找
                // 如果左子节点为空
                if (this.left == null) {
                    return null;
                }
                return this.left.search(value);
            } else {  // 向右子树递归查找
                if (this.right == null) {
                    return null;
                }
                return this.right.search(value);
            }
        }
    
        /**
         * 查找要删除节点的父节点
         *
         * @param value 要查找节点的值
         * @return 找到就返回父节点,否则返回 null
         */
        public Node searchParent(int value) {
            // 如果当前节点就是要删除的节点的父节点,就返回
            if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
                return this;
            } else {
    
                // 如果查找的值小于当前节点的值,并且当前节点的左子节点不为空
                if (value < this.value && this.left != null) {
                    return this.left.searchParent(value);  // 向左子树递归查找
                } else if (value >= this.value && this.right != null) {
                    return this.right.searchParent(value); // 向右子树递归查找
                } else {
                    return null;  // 没有找到父节点
                }
            }
        }
    
        // 添加节点:使用递归的方式添加节点。注意:需要满足二叉排序树的要求
        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 {  // 添加的节点大于当前节点的值
                // 如果当前节点的左子节点为 null
                if (this.right == null) {
                    this.right = node;
                } else {
                    // 递归向左子树添加
                    this.right.add(node);
                }
            }
    
        }
    
        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }
    
        // 中序遍历
        public void infixOrder() {
    
            if (this.left != null) {
                this.left.infixOrder();
            }
    
            System.out.println(this);
    
            if (this.right != null) {
                this.right.infixOrder();
            }
    
        }
    
    }
    

    第三种情况: 删除有两颗子树的节点 。相关代码如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/6 16:17
     * @Description: 二叉排序树(BST)的创建和遍历
     */
    public class BinarySortTreeTest {
        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]));
            }
    
            binarySortTree.infixOrder();
            binarySortTree.delNode(7);
            System.out.println("======================");
            binarySortTree.infixOrder();
    
        }
    }
    
    
    // 创建二叉排序树类 BinarySortTree
    class BinarySortTree {
    
        // 定义根节点
        private Node root;
    
        // 查找要删除的节点
        public Node search(int value) {
            if (root == null) {
                return null;
            } else {
                return root.search(value);
            }
        }
    
        // 查找父节点
        public Node searchParent(int value) {
            if (root == null) {
                return null;
            } else {
                return root.searchParent(value);
            }
        }
    
        // 把传入的节点 node 当做二叉排序树的根节点,然后返回以 node 为根节点的二叉排序树的最小值
        public int delRightTreeMin(Node node) {
    
            Node temp = node;
    
            // 循环查找左子节点,就会找到最小值
            while (temp.left != null) {
                temp = temp.left;
            }
    
            // 删除最小节点
            delNode(temp.value);
            return temp.value;
    
        }
    
        // 删除节点,这个方法才是核心
        public void delNode(int value) {
    
            if (root == null) {
                return;
            } else {
    
                // 先找到要删除的节点 targetNode
                Node targetNode = search(value);
    
                // 如果没有找到
                if (targetNode == null) {
                    return;
                }
    
                // 如果这颗二叉树只有一个节点
                if (root.left == null && root.right == null) {
                    root = null;
                    return;
                }
    
                // 去找 targetNode 的父节点
                Node parent = searchParent(value);
    
                // 如果要删除的节点是叶子节点
                if (targetNode.left == null && targetNode.right == null) {
    
                    // 判断 targetNode 是父节点的左子节点还是右子节点
                    if (parent.left != null && parent.left.value == value) {  // 是左子节点
                        parent.left = null;
                    } else if (parent.right != null && parent.right.value == value) {  // 是右子节点
                        parent.right = null;
                    }
    
                } else if (targetNode.left != null && targetNode.right != null) {  // 删除有两颗子树的节点
                    int minVal = delRightTreeMin(targetNode.right);
                    targetNode.value = minVal;
                } else {  // 删除只有一颗子树的节点
    
                    // 如果要删除的节点有左子节点
                    if (targetNode.left != null) {
    
                        if (parent != null) {
                            // 如果 targetNode 是 parent 的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.left;
                            } else {  // targetNode 是 parent 的右子节点
                                parent.right = targetNode.left;
                            }
                        } else {
                            root = targetNode.left;
                        }
    
                    } else {
    
                        if (parent != null) {
                            // 如果 targetNode 是 parent 的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.right;
                            } else {  // 如果 targetNode 是 parent 的右子节点
                                parent.right = targetNode.right;
                            }
                        } else {
                            root = targetNode.right;
                        }
    
                    }
    
                }
    
            }
    
        }
    
        // 添加节点的方法
        public void add(Node node) {
            if (root == null) {
                root = node;
            } else {
                root.add(node);
            }
        }
    
        // 中序遍历的方法
        public void infixOrder() {
            if (root != null) {
                root.infixOrder();
            } else {
                System.out.println("The Binary Sort Tree is empty, so it can not be traversal!!!");
            }
        }
    
    }
    
    // 创建 Node 节点类
    class Node {
    
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        /**
         * 查找要删除的节点
         * @param value 需要删除的节点的值
         * @return 如果找到,则返回该节点,否则返回 null
         */
        public Node search(int value) {
            if (value == this.value) {
                return this;
            } else if (value < this.value) {  // 向左子树递归查找
                // 如果左子节点为空
                if (this.left == null) {
                    return null;
                }
                return this.left.search(value);
            } else {  // 向右子树递归查找
                if (this.right == null) {
                    return null;
                }
                return this.right.search(value);
            }
        }
    
        /**
         * 查找要删除节点的父节点
         * @param value 要查找节点的值
         * @return 找到就返回父节点,否则返回 null
         */
        public Node searchParent(int value) {
            // 如果当前节点就是要删除的节点的父节点,就返回
            if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
                return this;
            } else {
    
                // 如果查找的值小于当前节点的值,并且当前节点的左子节点不为空
                if (value < this.value && this.left != null) {
                    return this.left.searchParent(value);  // 向左子树递归查找
                } else if (value >= this.value && this.right != null) {
                    return this.right.searchParent(value); // 向右子树递归查找
                } else {
                    return null;  // 没有找到父节点
                }
            }
        }
    
        // 添加节点:使用递归的方式添加节点。注意:需要满足二叉排序树的要求
        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 {  // 添加的节点大于当前节点的值
                // 如果当前节点的左子节点为 null
                if (this.right == null) {
                    this.right = node;
                } else {
                    // 递归向左子树添加
                    this.right.add(node);
                }
            }
    
        }
    
        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }
    
        // 中序遍历
        public void infixOrder() {
    
            if (this.left != null) {
                this.left.infixOrder();
            }
    
            System.out.println(this);
    
            if (this.right != null) {
                this.right.infixOrder();
            }
    
        }
    
    }
    

    平衡二叉树(AVL)

    基本介绍

    二叉排序树 有的时候是有些问题的,这时就需要用到 平衡二叉树(AVL) 了。基本介绍如下:

    创建和遍历

    以下是 创建平衡二叉树过程中需要用到的三种解决方案 ,如下图:

    获得树的高度、左子树的高度和右子树的高度。 代码如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/7 12:58
     * @Description: 平衡二叉树(AVL)
     */
    public class AVLTreeTest {
        public static void main(String[] args) {
    
            int[] arr = {4, 3, 6, 5, 7, 8};
            // 创建 AVLTree 对象
            AVLTree avlTree = new AVLTree();
    
            // 添加节点
            for (int i = 0; i < arr.length; i++) {
                avlTree.add(new Node(arr[i]));
            }
    
            avlTree.infixOrder();
            Node root = avlTree.getRoot();
            System.out.println("树的高度 = " + root.height());
            System.out.println("树的左子树高度 = " + root.leftHeight());
            System.out.println("树的右子树高度 = " + root.rightHeight());
    
        }
    }
    
    // 创建 AVL 树
    class AVLTree {
    
        // 定义根节点
        private Node root;
    
        // 获得根节点
        public Node getRoot() {
            return this.root;
        }
    
        // 查找要删除的节点
        public Node search(int value) {
            if (root == null) {
                return null;
            } else {
                return root.search(value);
            }
        }
    
        // 查找父节点
        public Node searchParent(int value) {
            if (root == null) {
                return null;
            } else {
                return root.searchParent(value);
            }
        }
    
        // 把传入的节点 node 当做二叉排序树的根节点,然后返回以 node 为根节点的二叉排序树的最小值
        public int delRightTreeMin(Node node) {
    
            Node temp = node;
    
            // 循环查找左子节点,就会找到最小值
            while (temp.left != null) {
                temp = temp.left;
            }
    
            // 删除最小节点
            delNode(temp.value);
            return temp.value;
    
        }
    
        // 删除节点,这个方法才是核心
        public void delNode(int value) {
    
            if (root == null) {
                return;
            } else {
    
                // 先找到要删除的节点 targetNode
                Node targetNode = search(value);
    
                // 如果没有找到
                if (targetNode == null) {
                    return;
                }
    
                // 如果这颗二叉树只有一个节点
                if (root.left == null && root.right == null) {
                    root = null;
                    return;
                }
    
                // 去找 targetNode 的父节点
                Node parent = searchParent(value);
    
                // 如果要删除的节点是叶子节点
                if (targetNode.left == null && targetNode.right == null) {
    
                    // 判断 targetNode 是父节点的左子节点还是右子节点
                    if (parent.left != null && parent.left.value == value) {  // 是左子节点
                        parent.left = null;
                    } else if (parent.right != null && parent.right.value == value) {  // 是右子节点
                        parent.right = null;
                    }
    
                } else if (targetNode.left != null && targetNode.right != null) {  // 删除有两颗子树的节点
                    int minVal = delRightTreeMin(targetNode.right);
                    targetNode.value = minVal;
                } else {  // 删除只有一颗子树的节点
    
                    // 如果要删除的节点有左子节点
                    if (targetNode.left != null) {
    
                        if (parent != null) {
                            // 如果 targetNode 是 parent 的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.left;
                            } else {  // targetNode 是 parent 的右子节点
                                parent.right = targetNode.left;
                            }
                        } else {
                            root = targetNode.left;
                        }
    
                    } else {
    
                        if (parent != null) {
                            // 如果 targetNode 是 parent 的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.right;
                            } else {  // 如果 targetNode 是 parent 的右子节点
                                parent.right = targetNode.right;
                            }
                        } else {
                            root = targetNode.right;
                        }
    
                    }
    
                }
    
            }
    
        }
    
        // 添加节点的方法
        public void add(Node node) {
            if (root == null) {
                root = node;
            } else {
                root.add(node);
            }
        }
    
        // 中序遍历的方法
        public void infixOrder() {
            if (root != null) {
                root.infixOrder();
            } else {
                System.out.println("The Binary Sort Tree is empty, so it can not be traversal!!!");
            }
        }
    
    }
    
    // 创建 Node 节点类
    class Node {
    
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        // 返回左子树的高度
        public int leftHeight() {
            if (left == null) {
                return 0;
            }
            return left.height();
        }
    
        // 返回右子树的高度
        public int rightHeight() {
            if (right == null) {
                return 0;
            }
            return right.height();
        }
    
        // 返回当前节点的高度,以该节点为根节点的树的高度
        public int height() {
            return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
        }
    
        /**
         * 查找要删除的节点
         * @param value 需要删除的节点的值
         * @return 如果找到,则返回该节点,否则返回 null
         */
        public Node search(int value) {
            if (value == this.value) {
                return this;
            } else if (value < this.value) {  // 向左子树递归查找
                // 如果左子节点为空
                if (this.left == null) {
                    return null;
                }
                return this.left.search(value);
            } else {  // 向右子树递归查找
                if (this.right == null) {
                    return null;
                }
                return this.right.search(value);
            }
        }
    
        /**
         * 查找要删除节点的父节点
         * @param value 要查找节点的值
         * @return 找到就返回父节点,否则返回 null
         */
        public Node searchParent(int value) {
            // 如果当前节点就是要删除的节点的父节点,就返回
            if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
                return this;
            } else {
    
                // 如果查找的值小于当前节点的值,并且当前节点的左子节点不为空
                if (value < this.value && this.left != null) {
                    return this.left.searchParent(value);  // 向左子树递归查找
                } else if (value >= this.value && this.right != null) {
                    return this.right.searchParent(value); // 向右子树递归查找
                } else {
                    return null;  // 没有找到父节点
                }
            }
        }
    
        // 添加节点:使用递归的方式添加节点。注意:需要满足二叉排序树的要求
        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 {  // 添加的节点大于当前节点的值
                // 如果当前节点的左子节点为 null
                if (this.right == null) {
                    this.right = node;
                } else {
                    // 递归向左子树添加
                    this.right.add(node);
                }
            }
    
        }
    
        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }
    
        // 中序遍历
        public void infixOrder() {
    
            if (this.left != null) {
                this.left.infixOrder();
            }
    
            System.out.println(this);
    
            if (this.right != null) {
                this.right.infixOrder();
            }
    
        }
    
    }
    

    左旋转

    对二叉排序树进行左旋转,即变成了平衡二叉树。 由上面代码发现,左右两颗子树的高度差的绝对值超过了 1 ,且右子树高于左子树, 所有需要进行 左旋转左旋转思路分析 如下图:

    左旋转 的代码实现如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/7 12:58
     * @Description: 平衡二叉树(AVL)
     */
    public class AVLTreeTest {
        public static void main(String[] args) {
    
            int[] arr = {4, 3, 6, 5, 7, 8};
            // 创建 AVLTree 对象
            AVLTree avlTree = new AVLTree();
    
            // 添加节点
            for (int i = 0; i < arr.length; i++) {
                avlTree.add(new Node(arr[i]));
            }
    
            avlTree.infixOrder();
            Node root = avlTree.getRoot();
            System.out.println("树的高度 = " + root.height());
            System.out.println("树的左子树高度 = " + root.leftHeight());
            System.out.println("树的右子树高度 = " + root.rightHeight());
    
        }
    }
    
    // 创建 AVL 树
    class AVLTree {
    
        // 定义根节点
        private Node root;
    
        // 获得根节点
        public Node getRoot() {
            return this.root;
        }
    
        // 查找要删除的节点
        public Node search(int value) {
            if (root == null) {
                return null;
            } else {
                return root.search(value);
            }
        }
    
        // 查找父节点
        public Node searchParent(int value) {
            if (root == null) {
                return null;
            } else {
                return root.searchParent(value);
            }
        }
    
        // 把传入的节点 node 当做二叉排序树的根节点,然后返回以 node 为根节点的二叉排序树的最小值
        public int delRightTreeMin(Node node) {
    
            Node temp = node;
    
            // 循环查找左子节点,就会找到最小值
            while (temp.left != null) {
                temp = temp.left;
            }
    
            // 删除最小节点
            delNode(temp.value);
            return temp.value;
    
        }
    
        // 删除节点,这个方法才是核心
        public void delNode(int value) {
    
            if (root == null) {
                return;
            } else {
    
                // 先找到要删除的节点 targetNode
                Node targetNode = search(value);
    
                // 如果没有找到
                if (targetNode == null) {
                    return;
                }
    
                // 如果这颗二叉树只有一个节点
                if (root.left == null && root.right == null) {
                    root = null;
                    return;
                }
    
                // 去找 targetNode 的父节点
                Node parent = searchParent(value);
    
                // 如果要删除的节点是叶子节点
                if (targetNode.left == null && targetNode.right == null) {
    
                    // 判断 targetNode 是父节点的左子节点还是右子节点
                    if (parent.left != null && parent.left.value == value) {  // 是左子节点
                        parent.left = null;
                    } else if (parent.right != null && parent.right.value == value) {  // 是右子节点
                        parent.right = null;
                    }
    
                } else if (targetNode.left != null && targetNode.right != null) {  // 删除有两颗子树的节点
                    int minVal = delRightTreeMin(targetNode.right);
                    targetNode.value = minVal;
                } else {  // 删除只有一颗子树的节点
    
                    // 如果要删除的节点有左子节点
                    if (targetNode.left != null) {
    
                        if (parent != null) {
                            // 如果 targetNode 是 parent 的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.left;
                            } else {  // targetNode 是 parent 的右子节点
                                parent.right = targetNode.left;
                            }
                        } else {
                            root = targetNode.left;
                        }
    
                    } else {
    
                        if (parent != null) {
                            // 如果 targetNode 是 parent 的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.right;
                            } else {  // 如果 targetNode 是 parent 的右子节点
                                parent.right = targetNode.right;
                            }
                        } else {
                            root = targetNode.right;
                        }
    
                    }
    
                }
    
            }
    
        }
    
        // 添加节点的方法
        public void add(Node node) {
            if (root == null) {
                root = node;
            } else {
                root.add(node);
            }
        }
    
        // 中序遍历的方法
        public void infixOrder() {
            if (root != null) {
                root.infixOrder();
            } else {
                System.out.println("The Binary Sort Tree is empty, so it can not be traversal!!!");
            }
        }
    
    }
    
    // 创建 Node 节点类
    class Node {
    
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        // 左旋转方法
        public void leftRotate() {
    
            // 以当前根节点的值创建新的节点
            Node newNdoe = new Node(value);
    
            // 把新的节点的左子树设置成为当前节点的左子树
            newNdoe.left = left;
    
            // 把新的节点的右子树设置成当前节点的右子树的左子树
            newNdoe.right = right.left;
    
            // 把当前节点的值替换成右子节点的值
            value = right.value;
    
            // 把当前节点的右子树设置成当前节点右子树的右子树
            right = right.right;
    
            // 把当前节点的左子树(左子节点)设置成新的节点
            left = newNdoe;
    
        }
    
        // 返回左子树的高度
        public int leftHeight() {
            if (left == null) {
                return 0;
            }
            return left.height();
        }
    
        // 返回右子树的高度
        public int rightHeight() {
            if (right == null) {
                return 0;
            }
            return right.height();
        }
    
        // 返回当前节点的高度,以该节点为根节点的树的高度
        public int height() {
            return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
        }
    
        /**
         * 查找要删除的节点
         *
         * @param value 需要删除的节点的值
         * @return 如果找到,则返回该节点,否则返回 null
         */
        public Node search(int value) {
            if (value == this.value) {
                return this;
            } else if (value < this.value) {  // 向左子树递归查找
                // 如果左子节点为空
                if (this.left == null) {
                    return null;
                }
                return this.left.search(value);
            } else {  // 向右子树递归查找
                if (this.right == null) {
                    return null;
                }
                return this.right.search(value);
            }
        }
    
        /**
         * 查找要删除节点的父节点
         *
         * @param value 要查找节点的值
         * @return 找到就返回父节点,否则返回 null
         */
        public Node searchParent(int value) {
            // 如果当前节点就是要删除的节点的父节点,就返回
            if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
                return this;
            } else {
    
                // 如果查找的值小于当前节点的值,并且当前节点的左子节点不为空
                if (value < this.value && this.left != null) {
                    return this.left.searchParent(value);  // 向左子树递归查找
                } else if (value >= this.value && this.right != null) {
                    return this.right.searchParent(value); // 向右子树递归查找
                } else {
                    return null;  // 没有找到父节点
                }
            }
        }
    
        // 添加节点:使用递归的方式添加节点。注意:需要满足二叉排序树的要求
        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 {  // 添加的节点大于当前节点的值
                // 如果当前节点的左子节点为 null
                if (this.right == null) {
                    this.right = node;
                } else {
                    // 递归向右子树添加
                    this.right.add(node);
                }
            }
    
            // 如果 (右子树的高度 - 左子树的高度)> 1 ,那么就进行左旋转
            if (rightHeight() - leftHeight() > 1) {
                leftRotate();
            }
    
        }
    
        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }
    
        // 中序遍历
        public void infixOrder() {
    
            if (this.left != null) {
                this.left.infixOrder();
            }
    
            System.out.println(this);
    
            if (this.right != null) {
                this.right.infixOrder();
            }
    
        }
    
    }
    

    右旋转

    对二叉排序树进行右旋转,即变成了平衡二叉树。 由上面代码发现,左右两颗子树的高度差的绝对值超过了 1 ,且左子树高于右子树, 所有需要进行 右旋转右旋转思路分析 如下图:

    右旋转 的代码实现如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/7 12:58
     * @Description: 平衡二叉树(AVL)
     */
    public class AVLTreeTest {
        public static void main(String[] args) {
    
            //int[] arr = {4, 3, 6, 5, 7, 8};  // 左旋转使用的数组
            int[] arr = {10, 12, 8, 9, 7, 6};  // 右旋转使用的数组
    
            // 创建 AVLTree 对象
            AVLTree avlTree = new AVLTree();
    
            // 添加节点
            for (int i = 0; i < arr.length; i++) {
                avlTree.add(new Node(arr[i]));
            }
    
            avlTree.infixOrder();
            Node root = avlTree.getRoot();
            System.out.println("树的高度 = " + root.height());
            System.out.println("树的左子树高度 = " + root.leftHeight());
            System.out.println("树的右子树高度 = " + root.rightHeight());
            System.out.println("当前根节点 = " + avlTree.getRoot());
    
        }
    }
    
    // 创建 AVL 树
    class AVLTree {
    
        // 定义根节点
        private Node root;
    
        // 获得根节点
        public Node getRoot() {
            return this.root;
        }
    
        // 查找要删除的节点
        public Node search(int value) {
            if (root == null) {
                return null;
            } else {
                return root.search(value);
            }
        }
    
        // 查找父节点
        public Node searchParent(int value) {
            if (root == null) {
                return null;
            } else {
                return root.searchParent(value);
            }
        }
    
        // 把传入的节点 node 当做二叉排序树的根节点,然后返回以 node 为根节点的二叉排序树的最小值
        public int delRightTreeMin(Node node) {
    
            Node temp = node;
    
            // 循环查找左子节点,就会找到最小值
            while (temp.left != null) {
                temp = temp.left;
            }
    
            // 删除最小节点
            delNode(temp.value);
            return temp.value;
    
        }
    
        // 删除节点,这个方法才是核心
        public void delNode(int value) {
    
            if (root == null) {
                return;
            } else {
    
                // 先找到要删除的节点 targetNode
                Node targetNode = search(value);
    
                // 如果没有找到
                if (targetNode == null) {
                    return;
                }
    
                // 如果这颗二叉树只有一个节点
                if (root.left == null && root.right == null) {
                    root = null;
                    return;
                }
    
                // 去找 targetNode 的父节点
                Node parent = searchParent(value);
    
                // 如果要删除的节点是叶子节点
                if (targetNode.left == null && targetNode.right == null) {
    
                    // 判断 targetNode 是父节点的左子节点还是右子节点
                    if (parent.left != null && parent.left.value == value) {  // 是左子节点
                        parent.left = null;
                    } else if (parent.right != null && parent.right.value == value) {  // 是右子节点
                        parent.right = null;
                    }
    
                } else if (targetNode.left != null && targetNode.right != null) {  // 删除有两颗子树的节点
                    int minVal = delRightTreeMin(targetNode.right);
                    targetNode.value = minVal;
                } else {  // 删除只有一颗子树的节点
    
                    // 如果要删除的节点有左子节点
                    if (targetNode.left != null) {
    
                        if (parent != null) {
                            // 如果 targetNode 是 parent 的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.left;
                            } else {  // targetNode 是 parent 的右子节点
                                parent.right = targetNode.left;
                            }
                        } else {
                            root = targetNode.left;
                        }
    
                    } else {
    
                        if (parent != null) {
                            // 如果 targetNode 是 parent 的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.right;
                            } else {  // 如果 targetNode 是 parent 的右子节点
                                parent.right = targetNode.right;
                            }
                        } else {
                            root = targetNode.right;
                        }
    
                    }
    
                }
    
            }
    
        }
    
        // 添加节点的方法
        public void add(Node node) {
            if (root == null) {
                root = node;
            } else {
                root.add(node);
            }
        }
    
        // 中序遍历的方法
        public void infixOrder() {
            if (root != null) {
                root.infixOrder();
            } else {
                System.out.println("The Binary Sort Tree is empty, so it can not be traversal!!!");
            }
        }
    
    }
    
    // 创建 Node 节点类
    class Node {
    
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        // 右旋转方法
        public void rightRotate() {
    
            Node newNdoe = new Node(value);
            newNdoe.right = right;
            newNdoe.left = left.right;
            value = left.value;
            left = left.left;
            right = newNdoe;
    
        }
    
        // 左旋转方法
        public void leftRotate() {
    
            // 以当前根节点的值创建新的节点
            Node newNdoe = new Node(value);
    
            // 把新的节点的左子树设置成为当前节点的左子树
            newNdoe.left = left;
    
            // 把新的节点的右子树设置成当前节点的右子树的左子树
            newNdoe.right = right.left;
    
            // 把当前节点的值替换成右子节点的值
            value = right.value;
    
            // 把当前节点的右子树设置成当前节点右子树的右子树
            right = right.right;
    
            // 把当前节点的左子树(左子节点)设置成新的节点
            left = newNdoe;
    
        }
    
        // 返回左子树的高度
        public int leftHeight() {
            if (left == null) {
                return 0;
            }
            return left.height();
        }
    
        // 返回右子树的高度
        public int rightHeight() {
            if (right == null) {
                return 0;
            }
            return right.height();
        }
    
        // 返回当前节点的高度,以该节点为根节点的树的高度
        public int height() {
            return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
        }
    
        /**
         * 查找要删除的节点
         *
         * @param value 需要删除的节点的值
         * @return 如果找到,则返回该节点,否则返回 null
         */
        public Node search(int value) {
            if (value == this.value) {
                return this;
            } else if (value < this.value) {  // 向左子树递归查找
                // 如果左子节点为空
                if (this.left == null) {
                    return null;
                }
                return this.left.search(value);
            } else {  // 向右子树递归查找
                if (this.right == null) {
                    return null;
                }
                return this.right.search(value);
            }
        }
    
        /**
         * 查找要删除节点的父节点
         *
         * @param value 要查找节点的值
         * @return 找到就返回父节点,否则返回 null
         */
        public Node searchParent(int value) {
            // 如果当前节点就是要删除的节点的父节点,就返回
            if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
                return this;
            } else {
    
                // 如果查找的值小于当前节点的值,并且当前节点的左子节点不为空
                if (value < this.value && this.left != null) {
                    return this.left.searchParent(value);  // 向左子树递归查找
                } else if (value >= this.value && this.right != null) {
                    return this.right.searchParent(value); // 向右子树递归查找
                } else {
                    return null;  // 没有找到父节点
                }
            }
        }
    
        // 添加节点:使用递归的方式添加节点。注意:需要满足二叉排序树的要求
        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 {  // 添加的节点大于当前节点的值
                // 如果当前节点的左子节点为 null
                if (this.right == null) {
                    this.right = node;
                } else {
                    // 递归向右子树添加
                    this.right.add(node);
                }
            }
    
            // 如果 (右子树的高度 - 左子树的高度)> 1 ,那么就进行左旋转
            if (rightHeight() - leftHeight() > 1) {
                leftRotate();
            }
    
            // 如果 (左子树的高度 - 右子树的高度)> 1 ,那么就进行右旋转
            if (leftHeight() - rightHeight() > 1) {
                rightRotate();
            }
        }
    
        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }
    
        // 中序遍历
        public void infixOrder() {
    
            if (this.left != null) {
                this.left.infixOrder();
            }
    
            System.out.println(this);
    
            if (this.right != null) {
                this.right.infixOrder();
            }
    
        }
    
    }
    

    双旋转

    双旋转 主要是 为了解决左旋转和右旋转无法解决的问题。相关问题以及双旋转的思路分析 如下图:

    双旋转 的代码实现如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/7/7 12:58
     * @Description: 平衡二叉树(AVL)
     */
    public class AVLTreeTest {
        public static void main(String[] args) {
    
            //int[] arr = {4, 3, 6, 5, 7, 8};  // 左旋转使用的数组
            //int[] arr = {10, 12, 8, 9, 7, 6};  // 右旋转使用的数组
            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]));
            }
    
            avlTree.infixOrder();
            Node root = avlTree.getRoot();
            System.out.println("树的高度 = " + root.height());
            System.out.println("树的左子树高度 = " + root.leftHeight());
            System.out.println("树的右子树高度 = " + root.rightHeight());
            System.out.println("当前根节点 = " + avlTree.getRoot());
            System.out.println("当前根节点的右子树的 …… " + avlTree.getRoot().right.right.left);
    
        }
    }
    
    // 创建 AVL 树
    class AVLTree {
    
        // 定义根节点
        private Node root;
    
        // 获得根节点
        public Node getRoot() {
            return this.root;
        }
    
        // 查找要删除的节点
        public Node search(int value) {
            if (root == null) {
                return null;
            } else {
                return root.search(value);
            }
        }
    
        // 查找父节点
        public Node searchParent(int value) {
            if (root == null) {
                return null;
            } else {
                return root.searchParent(value);
            }
        }
    
        // 把传入的节点 node 当做二叉排序树的根节点,然后返回以 node 为根节点的二叉排序树的最小值
        public int delRightTreeMin(Node node) {
    
            Node temp = node;
    
            // 循环查找左子节点,就会找到最小值
            while (temp.left != null) {
                temp = temp.left;
            }
    
            // 删除最小节点
            delNode(temp.value);
            return temp.value;
    
        }
    
        // 删除节点,这个方法才是核心
        public void delNode(int value) {
    
            if (root == null) {
                return;
            } else {
    
                // 先找到要删除的节点 targetNode
                Node targetNode = search(value);
    
                // 如果没有找到
                if (targetNode == null) {
                    return;
                }
    
                // 如果这颗二叉树只有一个节点
                if (root.left == null && root.right == null) {
                    root = null;
                    return;
                }
    
                // 去找 targetNode 的父节点
                Node parent = searchParent(value);
    
                // 如果要删除的节点是叶子节点
                if (targetNode.left == null && targetNode.right == null) {
    
                    // 判断 targetNode 是父节点的左子节点还是右子节点
                    if (parent.left != null && parent.left.value == value) {  // 是左子节点
                        parent.left = null;
                    } else if (parent.right != null && parent.right.value == value) {  // 是右子节点
                        parent.right = null;
                    }
    
                } else if (targetNode.left != null && targetNode.right != null) {  // 删除有两颗子树的节点
                    int minVal = delRightTreeMin(targetNode.right);
                    targetNode.value = minVal;
                } else {  // 删除只有一颗子树的节点
    
                    // 如果要删除的节点有左子节点
                    if (targetNode.left != null) {
    
                        if (parent != null) {
                            // 如果 targetNode 是 parent 的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.left;
                            } else {  // targetNode 是 parent 的右子节点
                                parent.right = targetNode.left;
                            }
                        } else {
                            root = targetNode.left;
                        }
    
                    } else {
    
                        if (parent != null) {
                            // 如果 targetNode 是 parent 的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.right;
                            } else {  // 如果 targetNode 是 parent 的右子节点
                                parent.right = targetNode.right;
                            }
                        } else {
                            root = targetNode.right;
                        }
    
                    }
    
                }
    
            }
    
        }
    
        // 添加节点的方法
        public void add(Node node) {
            if (root == null) {
                root = node;
            } else {
                root.add(node);
            }
        }
    
        // 中序遍历的方法
        public void infixOrder() {
            if (root != null) {
                root.infixOrder();
            } else {
                System.out.println("The Binary Sort Tree is empty, so it can not be traversal!!!");
            }
        }
    
    }
    
    // 创建 Node 节点类
    class Node {
    
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        // 右旋转方法
        public void rightRotate() {
    
            Node newNdoe = new Node(value);
            newNdoe.right = right;
            newNdoe.left = left.right;
            value = left.value;
            left = left.left;
            right = newNdoe;
    
        }
    
        // 左旋转方法
        public void leftRotate() {
    
            // 以当前根节点的值创建新的节点
            Node newNdoe = new Node(value);
    
            // 把新的节点的左子树设置成为当前节点的左子树
            newNdoe.left = left;
    
            // 把新的节点的右子树设置成当前节点的右子树的左子树
            newNdoe.right = right.left;
    
            // 把当前节点的值替换成右子节点的值
            value = right.value;
    
            // 把当前节点的右子树设置成当前节点右子树的右子树
            right = right.right;
    
            // 把当前节点的左子树(左子节点)设置成新的节点
            left = newNdoe;
    
        }
    
        // 返回左子树的高度
        public int leftHeight() {
            if (left == null) {
                return 0;
            }
            return left.height();
        }
    
        // 返回右子树的高度
        public int rightHeight() {
            if (right == null) {
                return 0;
            }
            return right.height();
        }
    
        // 返回当前节点的高度,以该节点为根节点的树的高度
        public int height() {
            return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
        }
    
        /**
         * 查找要删除的节点
         *
         * @param value 需要删除的节点的值
         * @return 如果找到,则返回该节点,否则返回 null
         */
        public Node search(int value) {
            if (value == this.value) {
                return this;
            } else if (value < this.value) {  // 向左子树递归查找
                // 如果左子节点为空
                if (this.left == null) {
                    return null;
                }
                return this.left.search(value);
            } else {  // 向右子树递归查找
                if (this.right == null) {
                    return null;
                }
                return this.right.search(value);
            }
        }
    
        /**
         * 查找要删除节点的父节点
         *
         * @param value 要查找节点的值
         * @return 找到就返回父节点,否则返回 null
         */
        public Node searchParent(int value) {
            // 如果当前节点就是要删除的节点的父节点,就返回
            if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
                return this;
            } else {
    
                // 如果查找的值小于当前节点的值,并且当前节点的左子节点不为空
                if (value < this.value && this.left != null) {
                    return this.left.searchParent(value);  // 向左子树递归查找
                } else if (value >= this.value && this.right != null) {
                    return this.right.searchParent(value); // 向右子树递归查找
                } else {
                    return null;  // 没有找到父节点
                }
            }
        }
    
        // 添加节点:使用递归的方式添加节点。注意:需要满足二叉排序树的要求
        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 {  // 添加的节点大于当前节点的值
                // 如果当前节点的左子节点为 null
                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();
                }
            }
        }
    
        @Override
        public String toString() {
            return "Node{" + "value=" + value + '}';
        }
    
        // 中序遍历
        public void infixOrder() {
    
            if (this.left != null) {
                this.left.infixOrder();
            }
    
            System.out.println(this);
    
            if (this.right != null) {
                this.right.infixOrder();
            }
    
        }
    
    }
    

    多路查找树

    TIPS:

    此部分的内容比较少用,且难度大。 所以这里只是简单的做一些概念了解,需要深入的同学请自行查阅资料!!!

    二叉树和 B 树

    2-3 树和 2-3-4 树

    B 树、B+ 树和 B* 树

    图的知识

    为什么会有图这种数据结构?
    原因:当我们需要表示多对多关系时,就要用到图这种数据结构。

    图的举例说明

    图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为 。 结点也可以称为 顶点 。如图:

    图的常用概念

    在学习图的过程中,理解常用概念是非常必要的,如下图:

    图的表示方式

    图的表示方式有两种:
    1、二维数组表示(邻接矩阵) 2、链表表示(邻接表)

    邻接矩阵

    邻接矩阵是表示图形中顶点之间相邻关系的矩阵,对于 n 个顶点的图而言,矩阵是的 row 和 col 表示的是 1....n 个点。图与邻接矩阵的关系以及解释如下:

    邻接表

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

    图的入门案例

    要求: 代码实现下面的图结构:

    代码实现如下:

    /**
     * @Author: guoshizhan
     * @Create: 2020/4/9 23:50
     * @Description: 图的入门案例
     */
    public class Main {
        public static void main(String[] args) {
            // 1-初始化图
            int nodeNum = 5;    // 结点个数
            String[] str = {"A", "B", "C", "D", "E"};    // 5个结点
    
            // 2-创建图对象
            Graph graph = new Graph(nodeNum);
    
            // 3-把上面定义的 5 个顶点添加到图中
            for(String vertex : str){
                graph.insertVertex(vertex);
            }
    
            // 4-添加边   A-B   A-C   B-C   B-D   B-E
            graph.insertEdge(0, 1, 1); // 表示 A-B 这条边
            graph.insertEdge(0, 2, 1); // 表示 A-C 这条边
            graph.insertEdge(1, 2, 1); // 表示 B-C 这条边
            graph.insertEdge(1, 3, 1); // 表示 B-D 这条边
            graph.insertEdge(1, 4, 1); // 表示 B-E 这条边
    
            // 5-把创建的图的邻接矩阵显示出来
            graph.showGraph();
        }
    }
    
    // 创建一个图的类
    class Graph {
    
        private ArrayList<String> vertexList;    // 存储顶点集合
        private int[][] edges;                   // 存储图对应的邻结矩阵
        private int numOfEdges;                  // 表示边的数目
        private boolean[] isVisited;             // 记录某个结点是否被访问
    
        // 01-编写构造器,n 代表图的结点个数
        public Graph(int n) {
            // 初始化矩阵和 vertexList
            edges = new int[n][n];
            vertexList = new ArrayList<String>();
            numOfEdges = 0;
        }
    
        // 02-插入结点
        public void insertVertex(String vertex) {
            vertexList.add(vertex);
        }
    
        // 03-添加边(无向图)。v1 表示某个顶点下标,v2 表示另一个顶点下标,weight 表示这两个顶点是否相连,是的话 weight = 1,否则等于 0
        public void insertEdge(int v1, int v2, int weight) {
            edges[v1][v2] = weight;
            edges[v2][v1] = weight;
            numOfEdges++;
        }
    
        // 04-返回结点个数
        public int getNumOfVertex() {
            return vertexList.size();
        }
    
        // 05-显示图所对应的矩阵
        public void showGraph() {
            for (int[] link : edges) {
                System.out.println(Arrays.toString(link));
            }
        }
    
        // 06-得到边的数目
        public int getNumOfEdges() {
            return numOfEdges;
        }
    
        // 07-返回结点i(下标)对应的数据。例如:0->"A" 1->"B" 2->"C"
        public String getValueByIndex(int i) {
            return vertexList.get(i);
        }
    
        // 08-返回 v1和v2 的权值
        public int getWeight(int v1, int v2) {
            return edges[v1][v2];
        }
    
        // 09-得到第一个邻接结点的下标 w
        public int getFirstNeighbor(int index) {
            for (int i = 0; i < vertexList.size(); i++) {
                if (edges[index][i] > 0) {
                    return i;
                }
            }
            return -1;
        }
    
        // 10-根据前一个邻接结点的下标来获取下一个邻接结点
        public int getNextNeighbor(int v1, int v2) {
            for (int i = v2 + 1; i < vertexList.size(); i++) {
                if (edges[v1][v2] > 0) {
                    return i;
                }
            }
            return -1;
        }
    }
    

    图的遍历

    图的遍历:
    所谓图的遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有以下两种访问策略: 1、深度优先遍历 2、广度优先遍历

    深度优先遍历(DFS)

    深度优先遍历,从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点, 可以这样理解:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。显然,深度优先搜索是一个递归的过程。

    深度优先遍历算法步骤:
    1、访问初始结点v,并标记结点 v 为已访问。 2、查找结点 v 的第一个邻接结点 w 。 3、若 w 存在,则执行 4 ,如果 w 不存在,则回到第 1 步,将从 v 的下一个结点继续。 4、若 w 未被访问,对 w 进行深度优先遍历递归(即把w当做另一个 v ,然后进行步骤 123)。 5、查找结点 v 的 w 邻接结点的下一个邻接结点,转到步骤3。
    /**
     * @Author: guoshizhan
     * @Create: 2020/4/9 23:50
     * @Description: 深度优先遍历测试
     * @Ohter: 如果出现中文乱码,那就把编码改为 GBK
     */
    public class Graph {
        //int[] arr = {20,30,10,80,70,60,50,40,90};
        private ArrayList<String> vertexList;    // 存储顶点集合
        private int[][] edges;                   // 存储图对应的邻结矩阵
        private int numOfEdges;                  // 表示边的数目
        private boolean[] isVisited;             // 记录某个结点是否被访问
    
        public static void main(String[] args) {
            // 1-初始化图
            String[] str = {"1", "2", "3", "4", "5", "6", "7", "8"};    // 8 个结点
    
            // 2-创建图对象
            Graph graph = new Graph(8);
    
            // 3-把 8 个顶点添加到图中
            for (String vertex : str) {
                graph.insertVertex(vertex);
            }
    
            // 4-添加边
            graph.insertEdge(0, 1);
            graph.insertEdge(0, 2);
            graph.insertEdge(1, 3);
            graph.insertEdge(1, 4);
            graph.insertEdge(3, 7);
            graph.insertEdge(4, 7);
            graph.insertEdge(2, 5);
            graph.insertEdge(2, 6);
            graph.insertEdge(5, 6);
    
            // 5-把创建的图的邻接矩阵显示出来
            graph.showGraph();
    
            // 6-深度优先遍历DFS测试
            System.out.println("\n深度优先遍历顺序如下:");
            graph.dfs();
    
        }
    
        // 01-编写构造器,n 代表图的结点个数
        public Graph(int n) {
            // 初始化矩阵和 vertexList
            edges = new int[n][n];
            vertexList = new ArrayList<String>();
            numOfEdges = 0;
        }
    
        // 02-插入结点
        public void insertVertex(String vertex) {
            vertexList.add(vertex);
        }
    
        // 03-添加边(无向图)。v1 表示某个顶点下标,v2 表示另一个顶点下标
        public void insertEdge(int v1, int v2) {
            edges[v1][v2] = 1;
            edges[v2][v1] = 1;
            numOfEdges++;
        }
    
        // 04-返回结点个数
        public int getNumOfVertex() {
            return vertexList.size();
        }
    
        // 05-显示图所对应的矩阵
        public void showGraph() {
            for (int[] link : edges) {
                System.out.println(Arrays.toString(link));
            }
        }
    
        // 06-得到边的数目
        public int getNumOfEdges() {
            return numOfEdges;
        }
    
        // 07-返回结点i(下标)对应的数据。例如:0->"A" 1->"B" 2->"C"
        public String getValueByIndex(int i) {
            return vertexList.get(i);
        }
    
        // 08-返回 v1和v2 的权值
        public int getWeight(int v1, int v2) {
            return edges[v1][v2];
        }
    
        // 09-得到第一个邻接结点的下标 w
        public int getFirstNeighbor(int index) {
            for (int i = 0; i < vertexList.size(); i++) {
                if (edges[index][i] > 0) {
                    return i;
                }
            }
            return -1;
        }
    
        // 10-根据前一个邻接结点的下标来获取下一个邻接结点
        public int getNextNeighbor(int v1, int v2) {
            for (int i = v2 + 1; i < vertexList.size(); i++) {
                if (edges[v1][i] > 0) {
                    return i;
                }
            }
            return -1;
        }
    
        // 11-深度优先遍历算法,i 第一次就是 0
        private void dfs(boolean[] isVisited, int i) {
            // 访问 i 结点并输出
            System.out.print(getValueByIndex(i) + "-->");
            // 将结点设置为已访问
            isVisited[i] = true;
            // 查找结点 i 的第一个邻接结点 w
            int w = getFirstNeighbor(i);
            // while 循环里面的条件代码 i 有邻接结点 w
            while (w != -1) {
                if (!isVisited[w]) {
                    dfs(isVisited, w);
                }
                // 如果 w 结点已访问,那么再去找 i 的其他邻接结点
                w = getNextNeighbor(i, w);
            }
        }
    
        // 12-深度优先遍历算法开始
        public void dfs() {
            isVisited = new boolean[vertexList.size()];
            // 遍历所有结点,进行 dfs 回溯
            for (int i = 0; i < getNumOfVertex(); i++) {
                if (!isVisited[i]) {
                    dfs(isVisited, i);
                }
            }
        }
    }
    

    广度优先遍历(BFS)

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

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

    广度优先遍历代码实现:

    /**
     * @Author: guoshizhan
     * @Create: 2020/4/9 23:50
     * @Description: 广度优先遍历测试
     * @Ohter: 如果出现中文乱码,那就把编码改为 GBK
     */
    public class Main {
        public static void main(String[] args) {
            // 1-初始化图
            int nodeNum = 5;    // 结点个数
            String[] str = {"A", "B", "C", "D", "E"};    // 5个结点
    
            // 2-创建图对象
            Graph graph = new Graph(nodeNum);
    
            // 3-把上面定义的 5 个顶点添加到图中
            for (String vertex : str) {
                graph.insertVertex(vertex);
            }
    
            // 4-添加边   A-B   A-C   B-C   B-D   B-E
            graph.insertEdge(0, 1, 1); // 表示 A-B 这条边
            graph.insertEdge(0, 2, 1); // 表示 A-C 这条边
            graph.insertEdge(1, 2, 1); // 表示 B-C 这条边
            graph.insertEdge(1, 3, 1); // 表示 B-D 这条边
            graph.insertEdge(1, 4, 1); // 表示 B-E 这条边
    
            // 5-把创建的图的邻接矩阵显示出来
            graph.showGraph();
    
            // 6-深度优先遍历DFS测试
            System.out.println("\n深度优先遍历顺序如下:");
            graph.dfs();
    
            // 7-广度优先遍历BFS测试
            System.out.println("\n广度优先遍历顺序如下:");
            graph.bfs();
        }
    }
    
    // 创建一个图的类
    class Graph {
    
        private ArrayList<String> vertexList;    // 存储顶点集合
        private int[][] edges;                   // 存储图对应的邻结矩阵
        private int numOfEdges;                  // 表示边的数目
        private boolean[] isVisited;             // 记录某个结点是否被访问
    
        // 01-编写构造器,n 代表图的结点个数
        public Graph(int n) {
            // 初始化矩阵和 vertexList
            edges = new int[n][n];
            vertexList = new ArrayList<String>();
            numOfEdges = 0;
        }
    
        // 02-插入结点
        public void insertVertex(String vertex) {
            vertexList.add(vertex);
        }
    
        // 03-添加边(无向图)。v1 表示某个顶点下标,v2 表示另一个顶点下标,weight 表示这两个顶点是否相连,是的话 weight = 1,否则等于 0
        public void insertEdge(int v1, int v2, int weight) {
            edges[v1][v2] = weight;
            edges[v2][v1] = weight;
            numOfEdges++;
        }
    
        // 04-返回结点个数
        public int getNumOfVertex() {
            return vertexList.size();
        }
    
        // 05-显示图所对应的矩阵
        public void showGraph() {
            for (int[] link : edges) {
                System.out.println(Arrays.toString(link));
            }
        }
    
        // 06-得到边的数目
        public int getNumOfEdges() {
            return numOfEdges;
        }
    
        // 07-返回结点i(下标)对应的数据。例如:0->"A" 1->"B" 2->"C"
        public String getValueByIndex(int i) {
            return vertexList.get(i);
        }
    
        // 08-返回 v1和v2 的权值
        public int getWeight(int v1, int v2) {
            return edges[v1][v2];
        }
    
        // 09-得到第一个邻接结点的下标 w
        public int getFirstNeighbor(int index) {
            for (int i = 0; i < vertexList.size(); i++) {
                if (edges[index][i] > 0) {
                    return i;
                }
            }
            return -1;
        }
    
        // 10-根据前一个邻接结点的下标来获取下一个邻接结点
        public int getNextNeighbor(int v1, int v2) {
            for (int i = v2 + 1; i < vertexList.size(); i++) {
                if (edges[v1][v2] > 0) {
                    return i;
                }
            }
            return -1;
        }
    
        // 11-深度优先遍历算法,i 第一次就是 0
        private void dfs(boolean[] isVisited, int i) {
            // 访问 i 结点并输出
            if (i == vertexList.size() - 1) {
                System.out.println(getValueByIndex(i));
            } else {
                System.out.print(getValueByIndex(i) + "-->");
            }
            // 将结点设置为已访问
            isVisited[i] = true;
            // 查找结点 i 的第一个邻接结点 w
            int w = getFirstNeighbor(i);
            // while 循环里面的条件代码 i 有邻接结点 w
            while (w != -1) {
                if (!isVisited[w]) {
                    dfs(isVisited, w);
                }
                // 如果 w 结点已访问,那么再去找 i 的其他邻接结点
                w = getNextNeighbor(i, w);
            }
        }
    
        // 12-深度优先遍历算法开始
        public void dfs() {
            isVisited = new boolean[vertexList.size()];
            // 遍历所有结点,进行 dfs 回溯
            for (int i = 0; i < getNumOfVertex(); i++) {
                if (!isVisited[i]) {
                    dfs(isVisited, i);
                }
            }
        }
    
        // 13-广度优先遍历算法
        private void bfs(boolean[] isVisited, int i) {
            int u;    //  表示队列的头节点对应下标
            int w;    // 邻接结点
            // 创建集合队列,记录结点访问顺序
            LinkedList queue = new LinkedList();
            // 访问结点,输出结点信息
            if (i == vertexList.size() - 1) {
                System.out.println(getValueByIndex(i));
            } else {
                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]) {
                        if (w == vertexList.size() - 1) {
                            System.out.println(getValueByIndex(w));
                        } else {
                            System.out.print(getValueByIndex(w) + "-->");
                        }
                        // 标记此结点以访问
                        isVisited[w] = true;
                        // 入队
                        queue.addLast(w);
                    }
                    // 以 u 为前驱点,找 w 的下一个邻接点
                    w = getNextNeighbor(u, w);
                }
            }
        }
    
        // 14-广度优先遍历算法开始
        public void bfs() {
            isVisited = new boolean[vertexList.size()];
            for (int i = 0; i < getNumOfVertex(); i++) {
                if (!isVisited[i]) {
                    bfs(isVisited, i);
                }
            }
        }
    }
    

    两种遍历方式对比

    上面的例子中,两种遍历方式的结果都是一样的,无法对比出来。现在以下图例子进行举例,结果截然不同。如下:

    代码实现:

    /**
     * @Author: guoshizhan
     * @Create: 2020/4/9 23:50
     * @Description: 深度优先遍历测试
     * @Ohter: 如果出现中文乱码,那就把编码改为 GBK
     */
    public class Main {
        public static void main(String[] args) {
            // 1-初始化图
            int nodeNum = 8;    // 结点个数
            String[] str = {"1", "2", "3", "4", "5", "6", "7", "8"};;    // 8 个结点
    
            // 2-创建图对象
            Graph graph = new Graph(nodeNum);
    
            // 3-把上面定义的 5 个顶点添加到图中
            for (String vertex : str) {
                graph.insertVertex(vertex);
            }
    
            // 4-添加边
            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);
    
            // 5-把创建的图的邻接矩阵显示出来
            graph.showGraph();
    
            // 6-深度优先遍历DFS测试
            System.out.println("\n深度优先遍历顺序如下:");
            graph.dfs();
    
            // 7-广度优先遍历BFS测试
            System.out.println("\n广度优先遍历顺序如下:");
            graph.bfs();
        }
    }
    
    // 创建一个图的类
    class Graph {
    
        private ArrayList<String> vertexList;    // 存储顶点集合
        private int[][] edges;                   // 存储图对应的邻结矩阵
        private int numOfEdges;                  // 表示边的数目
        private boolean[] isVisited;             // 记录某个结点是否被访问
    
        // 01-编写构造器,n 代表图的结点个数
        public Graph(int n) {
            // 初始化矩阵和 vertexList
            edges = new int[n][n];
            vertexList = new ArrayList<String>();
            numOfEdges = 0;
        }
    
        // 02-插入结点
        public void insertVertex(String vertex) {
            vertexList.add(vertex);
        }
    
        // 03-添加边(无向图)。v1 表示某个顶点下标,v2 表示另一个顶点下标,weight 表示这两个顶点是否相连,是的话 weight = 1,否则等于 0
        public void insertEdge(int v1, int v2, int weight) {
            edges[v1][v2] = weight;
            edges[v2][v1] = weight;
            numOfEdges++;
        }
    
        // 04-返回结点个数
        public int getNumOfVertex() {
            return vertexList.size();
        }
    
        // 05-显示图所对应的矩阵
        public void showGraph() {
            for (int[] link : edges) {
                System.out.println(Arrays.toString(link));
            }
        }
    
        // 06-得到边的数目
        public int getNumOfEdges() {
            return numOfEdges;
        }
    
        // 07-返回结点i(下标)对应的数据。例如:0->"A" 1->"B" 2->"C"
        public String getValueByIndex(int i) {
            return vertexList.get(i);
        }
    
        // 08-返回 v1和v2 的权值
        public int getWeight(int v1, int v2) {
            return edges[v1][v2];
        }
    
        // 09-得到第一个邻接结点的下标 w
        public int getFirstNeighbor(int index) {
            for (int i = 0; i < vertexList.size(); i++) {
                if (edges[index][i] > 0) {
                    return i;
                }
            }
            return -1;
        }
    
        // 10-根据前一个邻接结点的下标来获取下一个邻接结点
        public int getNextNeighbor(int v1, int v2) {
            for (int i = v2 + 1; i < vertexList.size(); i++) {
                if (edges[v1][v2] > 0) {
                    return i;
                }
            }
            return -1;
        }
    
        // 11-深度优先遍历算法,i 第一次就是 0
        private void dfs(boolean[] isVisited, int i) {
            // 访问 i 结点并输出
            if (i == vertexList.size() - 1) {
                System.out.println(getValueByIndex(i));
            } else {
                System.out.print(getValueByIndex(i) + "-->");
            }
            // 将结点设置为已访问
            isVisited[i] = true;
            // 查找结点 i 的第一个邻接结点 w
            int w = getFirstNeighbor(i);
            // while 循环里面的条件代码 i 有邻接结点 w
            while (w != -1) {
                if (!isVisited[w]) {
                    dfs(isVisited, w);
                }
                // 如果 w 结点已访问,那么再去找 i 的其他邻接结点
                w = getNextNeighbor(i, w);
            }
        }
    
        // 12-深度优先遍历算法开始
        public void dfs() {
            isVisited = new boolean[vertexList.size()];
            // 遍历所有结点,进行 dfs 回溯
            for (int i = 0; i < getNumOfVertex(); i++) {
                if (!isVisited[i]) {
                    dfs(isVisited, i);
                }
            }
        }
    
        // 13-广度优先遍历算法
        private void bfs(boolean[] isVisited, int i) {
            int u;    // 表示队列的头节点对应下标
            int w;    // 邻接结点
            // 创建集合队列,记录结点访问顺序
            LinkedList queue = new LinkedList();
            // 访问结点,输出结点信息
            if (i == vertexList.size() - 1) {
                System.out.println(getValueByIndex(i));
            } else {
                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]) {
                        if (w == vertexList.size() - 1) {
                            System.out.println(getValueByIndex(w));
                        } else {
                            System.out.print(getValueByIndex(w) + "-->");
                        }
                        // 标记此结点以访问
                        isVisited[w] = true;
                        // 入队
                        queue.addLast(w);
                    }
                    // 以 u 为前驱点,找 w 的下一个邻接点
                    w = getNextNeighbor(u, w);
                }
            }
        }
    
        // 14-广度优先遍历算法开始
        public void bfs() {
            isVisited = new boolean[vertexList.size()];
            for (int i = 0; i < getNumOfVertex(); i++) {
                if (!isVisited[i]) {
                    bfs(isVisited, i);
                }
            }
        }
    }
    

    数据结构的知识点到这里就结束了。如果有错误请评论指出,方便改正。该篇文章也会持续更新,查漏补缺,希望能够对大家有帮助。

    番外篇,哈哈

    数据结构:逻辑结构和物理结构(数据在计算机内部的物理存储方式)
    数据元素存储形式:顺序存储结构和链式存储结构(银行排队叫号系统)
    逻辑结构:集合结构、线性结构、树形结构(金字塔关系)、图形结构
    了解:六度空间理论
    
    了解算法:就是解决问题的方法。例如:求从1加到100的和。使用for循环和等差公式,对计算机来说都没有什么差别,但加到10000000就差别大了,这就是算法。
    算法5个特性:零个或多个输入、至少一个或多个输出、有穷性、确定性和可行性。
    算法设计要求:正确性、可读性、健壮性、时间效率高和存储量低。
    
    时间复杂度(渐近时间复杂度):使用大O体现算法时间复杂度,成为大O计法。
    线性阶:非嵌套循环涉及线性阶,对应次数成直线增长。
    平方阶:两个嵌套循环涉及平方阶。
    对数阶:例如下面的程序:2的x次方=n,求解之后x=log(2)n,所以时间复杂度为O(logn)
    还有常数阶,立方阶,指数阶。nlogn阶。
    int i  = 1, n = 100;
    while(i < n)
    {
    i = i * 2;
    }
    
    最坏情况:
    平均情况:平均运行时间就是期望运行时间。
    空间复杂度:写代码时,可以用空间换取时间。闰年算法的例子。 
    
    
    线性表:
    存和读的情况:时间复杂度为O(1)
    插入和删除情况:时间复杂度为O(n)
    单链表:
    结点:数据域和指针域合在一起叫做结点
    数据域:存放数据的地方
    指针域:存放下一个地址的地方
    第一个结点叫做头结点(头指针)头结点一般不存储任何东西,头指针指向头结点,最后一个结点指向NULL
    
    
    下一次看线性表第6集
    
    
    
    ======================================
    
    认识时间复杂度,用big O表示
    二分搜索,时间复杂度O(log2N)
    外排(谁小谁移动)
    题目:给定一个M个数的数组a和N个数的数组B,数组a乱序,数组b顺序,求两个数组共有多少个相同的数的复杂度?
    第一种:嵌套for循环,复杂度为O(M*N)
    第二种:对数组b(数组b是顺序的)使用二分查找,时间复杂度O(M*log2N)
    第三种:使用外排,先对数组a进行排序,然后使用外排,就是将两个数组的索引指向0,指向数字谁小谁就往下移动一个位置,直到结束。
    
    
    选择排序:
    第一次排序把最小的放在第一位,第二次排序把第二小的数字放在第二位,以此类推,直至结束。
    这种排序和数据状况没有关系,即便是一个排好的数组,它的时间复杂度仍然不变。
    
    
    冒泡排序:
    在一个数组中,相邻位置的数进行比较。进行完第一轮排序,最大的数字会在最后一个位置。那么下一轮排序就不用比较最后一个数字了。
    这种排序和数据状况没有关系,即便是一个排好的数组,它的时间复杂度仍然不变。
    
    
    插入排序:
    就像打扑克牌一样,一副排好序的牌,然后你摸了一张牌,就要给这张牌找位置,这就是插入排序。
    插入排序和数据状况有关,例如:数组元素1,2,3,4,5,那么插入排序复杂度为O(N),如果是5,4,3,2,1,那么复杂度为O(N2).
    一般情况下,都是按照最坏情况作为一个算法的复杂度。
    
    
    最好情况:
    
    
    平均情况:
    
    
    最坏情况:
    
    
    以上三种情况在插入排序可见,自己百度以下平均情况。
    
    
    对数器【很重要的】:方法在排序代码里有。先要有随机数组产生器,然后需要绝对正确的方法,接着进行大样本的测试。
    堆的结构准备模板,排序、二叉树、数组也要准备对数器模板。
    
    冒泡和选择公司已经不使用了,只具有参考和教学意义。
    
    递归算法:1:38:26	递归如何求时间复杂度?1:51:49	时间复杂度求解公式1:54:30
    
    
    归并排序:
    
    master公式
    复杂度为O(N*log2N)
    
    
    
    
    
    
    计算机网络看视频从第一章开始看,同时参观CSDN别人的博客。
    
    
    
    ===============================
    韩顺平老师数据结构:
    ===============================
    KMP算法:
    
    汉诺塔问题:使用分治算法
    
    
    八皇后问题:使用回溯算法
    
    
    骑士周游问题:DFS+贪心算法
    
    
    场合不同,所使用的算法不一样
    
    五子棋程序
    
    约瑟夫问题【单向环形链表】
    
    稀疏数组和队列
    队列的应用:队列是个有序列表,可以用数组或者链表实现。特点:先进先出
    队列加数据在尾部加入,且rear+1,取数据在头部取,且front+1。
    queue包里面代码:数组实现队列和链表实现队列。
    数组模拟成环形队列。
    
    栈的应用:如子弹的弹夹,最先压入的子弹最后打出。
    线性表:自己补充
    
    单链表知识:看完写博客
    
    双向链表:
    
    (环形链表)约瑟夫环:
    
    
    
    排序算法:
    内容在 PPT 上
    
    已看:50 51 
    
    
    冒泡排序:
    选择排序:
    插入排序:
    希尔排序:
    快速排序:
    归并排序:
    基数排序:
    桶排序:
    堆排序:
    计数排序:
    
    
    
    查找算法:
    顺序(线性)查找:
    二分查找/折半查找:
    插值查找:	非常的牛逼
    斐波那契查找(黄金分割查找):
    
    
    
    哈希表:
    
    
    
    二叉树:
    - 各种二叉树术语
    - 三种遍历方式
    - 二叉树的查找
    - 二叉树的删除
    - 顺序存储二叉树
    - 线索化二叉树
    - 堆排序:先变成大顶堆,然后排序
    
    
    赫夫曼树:
    wpl最小的就是赫夫曼树,赫夫曼树也是二叉树
    赫夫曼编码:不要前缀编码,就是不要出现二义性
    赫夫曼压缩
    赫夫曼解压
    
    
    
    二叉排序树:
    - 创建
    - 遍历
    - 删除
    
    
    平衡二叉树:
    - 左旋转
    - 右旋转
    - 双旋转
    
    多叉树:
    B树
    - 2-3树
    - 234树
    
    B+树
    
    B*树
    
    多路查找树
    
    
    
    图:
    图的基本术语
    图的邻接矩阵
    图的邻接表
    图的遍历方式:
    - 深度优先遍历(DFS)
    - 广度优先遍历(BFS)
    想要理解清楚 DFS 和 BFS 的区别,就要以图的邻接矩阵为例子,更好理解一点。
    
    
    
    程序员常用的 10 中算法:
    - 二分查找算法(非递归)
    - 分治算法(汉诺塔问题)【使用了递归算法】
    - 动态规划算法(背包问题)
    - KMP 算法(字符串匹配问题)
    - 暴力匹配算法
    - 贪心算法
    - 普利姆算法(prim算法)(修路问题)(最小生成树问题)
    - 克鲁斯卡尔算法(公交站问题)
    - 迪杰斯特拉算法(最短路径问题)
    - 弗洛伊德算法
    - 马踏棋盘算法(骑士周游问题)
    
    
    
    卖油翁和老黄牛的故事:
    在通往成功的路上,我们必须坚持,不要中途放弃,自毁前程,而要勇往直前,坚持不懈,最终会抵达理想的彼岸。既然选择了远方,便只顾风雨兼程。
    
    数据结构
    • 文章作者:GuoShiZhan
    • 创建时间:2021-08-16 14:12:01
    • 更新时间:2021-08-16 14:12:01
    • 版权声明:本文为博主原创文章,未经博主允许不得转载!
    请 在 评 论 区 留 言 哦 ~~~
    1024