2020-01-11

数据结构和算法

4 小时读完 (大约 33713 个字)

数据结构入门

内容概要：

线性表和链表
栈和队列
数组和广义表
树和二叉树
图的知识

线性表和链表

链表与单链表介绍

单链表的应用

基本介绍

代码实现

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

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 ，其左右子节点为 left 和 right ，这种情况下，有两种可能：

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算法）（修路问题）（最小生成树问题）
- 克鲁斯卡尔算法（公交站问题）
- 迪杰斯特拉算法（最短路径问题）
- 弗洛伊德算法
- 马踏棋盘算法（骑士周游问题）



卖油翁和老黄牛的故事：
在通往成功的路上，我们必须坚持，不要中途放弃，自毁前程，而要勇往直前，坚持不懈，最终会抵达理想的彼岸。既然选择了远方，便只顾风雨兼程。

数据结构

本文标题：数据结构入门
本文作者：Java Developer
本文链接：https://guoshizhan.github.io/Structure.html
版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！

📚 本站推荐文章
👉 从 0 开始搭建 Hexo 博客
👉 计算机网络入门教程
👉 数据结构入门
👉 算法入门
👉 IDEA 入门教程