资料来源：https://www.bilibili.com/video/BV1E4411H73v?p=86

一、哈希表

1、哈希表的基本介绍

散列表（Hash table ，也叫哈希表），是根据关键码值（Key value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

2、哈希表的实例

有一个公司，当有新的员工来报道时，要求将该员工的信息加入（id, 性别, 年龄, 名字, 住址..），当输入该员工的 id 时，要求查找到该员工的所有信息

要求：
1) 不使用数据库，速度越快越好 => 哈希表（散列）
2) 添加时，保证按照 id 从低到高插入
思考：如果 id 不是从低到高插入，但要求各条链表仍是从低到高，怎么解决?
3) 使用链表来实现哈希表，该链表不带表头【即：链表的第一个结点就存放雇员信息】
4) 思路分析并画出示意图

5) 代码实现

public class HashTabDemo {
    public static void main(String[] args) {
        // 创建哈希表
        HashTab hashTab = new HashTab(7);
        // 写一个简单的菜单
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while(true) {
            System.out.println("add:  添加雇员");
            System.out.println("list: 显示雇员");
            System.out.println("find: 查找雇员");
            System.out.println("exit: 退出系统");
            key = scanner.next();
            switch (key) {
            case "add":
                System.out.println("输入id");
                int id = scanner.nextInt();
                System.out.println("输入名字");
                String name = scanner.next();
                //创建 雇员
                Emp emp = new Emp(id, name);
                hashTab.add(emp);
                break;
            case "list":
                hashTab.list();
                break;
            case "find":
                System.out.println("请输入要查找的id");
                id = scanner.nextInt();
                hashTab.findEmpById(id);
                break;
            case "exit":
                scanner.close();
                System.exit(0);
            default:
                break;
            }
        }
    }
}
// 创建HashTab：管理多条链表
class HashTab {
    private EmpLinkedList[] empLinkedListArray;
    private int size; // 表示有多少条链表
    // 构造器
    public HashTab(int size) {
        this.size = size;
        // 初始化empLinkedListArray
        empLinkedListArray = new EmpLinkedList[size];
        // 这时必须分别初始化每个链表，否则报错空指针
        for(int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }
    // 添加雇员
    public void add(Emp emp) {
        // 根据员工的id，得到该员工应当添加到哪条链表
        int empLinkedListNO = hashFun(emp.id);
        // 将emp添加到对应的链表中
        empLinkedListArray[empLinkedListNO].add(emp);
    }
    // 遍历所有的链表，遍历hashtab
    public void list() {
        for(int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }
    // 根据输入的id,查找雇员
    public void findEmpById(int id) {
        // 使用散列函数确定到哪条链表查找
        int empLinkedListNO = hashFun(id);
        Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
        if(emp != null) { //找到
            System.out.printf("在第%d条链表中找到雇员 id = %d\n", (empLinkedListNO + 1), id);
        }else{
            System.out.println("在哈希表中，没有找到该雇员~");
        }
    }
    // 编写散列函数, 使用一个简单取模法
    public int hashFun(int id) {
        return id % size;
    }
}
// 表示一个雇员
class Emp {
    public int id;
    public String name;
    public Emp next; // next 默认为 null
    public Emp(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
}
// 创建EmpLinkedList，表示链表
class EmpLinkedList {
    // 头指针，执行第一个Emp，因此我们这个链表的head是直接指向第一个Emp
    private Emp head; // 默认null
    // 添加雇员到链表
    // 1. 假定，当添加雇员时，id是自增长，即id的分配总是从小到大。因此我们将该雇员直接加入到本链表的最后即可
    public void add(Emp emp) {
        // 如果是添加第一个雇员
        if(head == null) {
            head = emp;
            return;
        }
        // 如果不是第一个雇员，则使用一个辅助的指针，帮助定位到最后
        Emp curEmp = head;
        while(true) {
            if(curEmp.next == null) { // 说明到链表最后
                break;
            }
            curEmp = curEmp.next;   // 后移，直到curEmp到链表最后
        }
        // 退出时直接将emp加入链表
        curEmp.next = emp;
    }
    // 遍历链表的雇员信息
    public void list(int no) {
        if(head == null) {     // 说明链表为空
            System.out.println("第 " + (no+1) + " 链表为空");
            return;
        }
        System.out.print("第 "+ (no+1) +" 链表的信息为：");
        Emp curEmp = head; // 辅助指针
        while(true) {
            System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name);
            if(curEmp.next == null) { // 说明curEmp已经是最后结点
                break;
            }
            curEmp = curEmp.next;  // 后移遍历，直到curEmp到链表最后
        }
        System.out.println();
    }
    // 根据id查找雇员
    // 如果查找到，就返回Emp, 如果没有找到，就返回null
    public Emp findEmpById(int id) {
        // 判断链表是否为空
        if(head == null) {
            System.out.println("链表为空");
            return null;
        }
        // 辅助指针
        Emp curEmp = head;
        while(true) {
            if(curEmp.id == id) { // 找到
                break;  // 这时curEmp就指向要查找的雇员
            }
            // 退出
            if(curEmp.next == null) {// 说明遍历当前链表没有找到该雇员
                curEmp = null;
                break;
            }
            curEmp = curEmp.next; // 后移，直到curEmp到链表最后
        }
        return curEmp;
    }
}

二、树结构的基础部分

1、二叉树

1.1 为什么需要树这种数据结构

1）数组存储方式的分析

优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低

2）链式存储方式的分析

优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好)。
缺点：在进行检索时，效率仍然较低，比如检索某个值，需要从头节点开始遍历)

3）树存储方式的分析

能提高数据存储，读取的效率, 比如利用二叉排序树(Binary Sort Tree) ，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

案例: [7, 3, 10, 1, 5, 9, 12]

1.2 树示意图

树的常用术语（结合示意图理解）:

节点
根节点
父节点
子节点
叶子节点（没有子节点的节点）
节点的权（节点值）
路径（从 root 节点找到该节点的路线）
层
子树
树的高度（最大层数）
森林：多颗子树构成森林

1.3 二叉树的概念

树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
二叉树的子节点分为左节点和右节点

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

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

1.4 二叉树遍历的说明

使用前序，中序和后序对下面的二叉树进行遍历.

前序遍历: 先输出父节点，再遍历左子树和右子树父 - 左 - 右
中序遍历: 先遍历左子树，再输出父节点，再遍历右子树左 - 父 - 右
后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点 左 - 右 - 父
小结：看输出父节点的顺序，就确定是前序，中序还是后序

1.5 二叉树遍历应用实例（前序、中序、后序）

应用实例的说明和思路<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/22523384/1652880541900-6690fd3b-331b-4080-900e-ee9b14411078.png#clientId=ue0390292-80be-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=503&id=u5c71bbe9&margin=%5Bobject%20Object%5D&name=image.png&originHeight=503&originWidth=1017&originalType=binary&ratio=1&rotation=0&showTitle=false&size=365890&status=done&style=none&taskId=uf608dac1-4021-442a-97d9-32adcef2a74&title=&width=1017)<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/22523384/1652882036961-a8e5128c-58c0-40ca-a6dd-87abd0683de6.png#clientId=ue0390292-80be-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=319&id=uf30618b7&margin=%5Bobject%20Object%5D&name=image.png&originHeight=416&originWidth=525&originalType=binary&ratio=1&rotation=0&showTitle=false&size=47982&status=done&style=none&taskId=u032aa338-8b4d-40b3-9d93-cdb479a990a&title=&width=403)<br />代码实现：

public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 先需要创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        // 创建需要的结点
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");
        //说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        binaryTree.setRoot(root);
        // 测试
        System.out.println("前序遍历");     
        binaryTree.preOrder();                // 1,2,3,5,4
        System.out.println("中序遍历");
        binaryTree.infixOrder();             // 2,1,5,3,4
        System.out.println("后序遍历");
        binaryTree.postOrder();             // 2,5,4,3,1
    }
}
//定义BinaryTree 二叉树
class BinaryTree {
    private HeroNode root;
    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //前序遍历
    public void preOrder() {
        if(this.root != null) {
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //中序遍历
    public void infixOrder() {
        if(this.root != null) {
            this.root.infixOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //后序遍历
    public void postOrder() {
        if(this.root != null) {
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
}
// 先创建HeroNode 结点
@Data
class HeroNode {
    private int no;                // 节点编号
    private String name;        // 节点名称
    private HeroNode left;         // 指向左边节点、默认null
    private HeroNode right;     // 指向右边节点、默认null
    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + "]";
    }
    //编写前序遍历的方法
    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.6 二叉树-查找指定节点

请编写前序查找，中序查找和后序查找的方法。
并分别使用三种查找方式，查找 heroNO = 5的节点
并分析各种查找方式，分别比较了多少次
思路分析图解

public class BinaryTreeDemo {
    public static void main(String[] args) {
        //先需要创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建需要的结点
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");
        //说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        binaryTree.setRoot(root);
        //前序遍历
        //前序遍历的次数 ：4 
        System.out.println("前序遍历方式~~~");
        HeroNode resNode = binaryTree.preOrderSearch(5);
        if (resNode != null) {
            System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
        } else {
            System.out.printf("没有找到 no = %d 的英雄", 5);
        }
        //中序遍历查找
        //中序遍历3次
        System.out.println("中序遍历方式~~~");
        HeroNode resNode1 = binaryTree.infixOrderSearch(5);
        if (resNode1 != null) {
            System.out.printf("找到了，信息为 no=%d name=%s", resNode1.getNo(), resNode1.getName());
        } else {
            System.out.printf("没有找到 no = %d 的英雄", 5);
        }
        //后序遍历查找
        //后序遍历查找的次数  2次
        System.out.println("后序遍历方式~~~");
        HeroNode resNode2 = binaryTree.postOrderSearch(5);
        if (resNode2 != null) {
            System.out.printf("找到了，信息为 no=%d name=%s", resNode2.getNo(), resNode2.getName());
        } else {
            System.out.printf("没有找到 no = %d 的英雄", 5);
        }
    }
}
//定义BinaryTree 二叉树
class BinaryTree {
    private HeroNode root;
    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //前序遍历
    public HeroNode preOrderSearch(int no) {
        if(root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序遍历
    public HeroNode infixOrderSearch(int no) {
        if(root != null) {
            return root.infixOrderSearch(no);
        }else {
            return null;
        }
    }
    //后序遍历
    public HeroNode postOrderSearch(int no) {
        if(root != null) {
            return this.root.postOrderSearch(no);
        }else {
            return null;
        }
    }
}
// 先创建HeroNode 结点
@Data
class HeroNode {
    private int no;            // 节点编号
    private String name;    // 节点名称
    private HeroNode left;     // 指向左边节点、默认null
    private HeroNode right; // 指向右边节点、默认null
    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + "]";
    }
    /** 前序遍历查找
     * @param no 查找no
     * @return 如果找到就返回该Node ,如果没有找到返回 null
     */
    public HeroNode preOrderSearch(int no) {
        System.out.println("进入前序遍历");
        //比较当前结点是不是
        if(this.no == no) {
            return this;
        }
        //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
        //2.如果左递归前序查找，找到结点，则返回
        HeroNode resultNode = null;
        if(this.left != null) {
            resultNode = this.left.preOrderSearch(no);
        }
        if(resultNode != null) {    //说明在左子树找到目标节点
            return resultNode;
        }
        //1.左递归前序查找，找到结点，则返回，否继续判断，
        //2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
        if(this.right != null) {
            resultNode = this.right.preOrderSearch(no);
        }
        return resultNode;
    }
    //中序遍历查找
    public HeroNode infixOrderSearch(int no) {
        //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
        HeroNode resNode = null;
        if(this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        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 HeroNode postOrderSearch(int no) {
        //判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
        HeroNode resNode = null;
        if(this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if(resNode != null) {//说明在左子树找到
            return resNode;
        }
        //如果左子树没有找到，则向右子树递归进行后序遍历查找
        if(this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if(resNode != null) {
            return resNode;
        }
        System.out.println("进入后序查找");
        //如果左右子树都没有找到，就比较当前结点是不是
        if(this.no == no) {
            return this;
        }
        return resNode;
    }
}

1.7 二叉树-删除节点

要求
1) 如果删除的节点是叶子节点，则删除该节点
2) 如果删除的节点是非叶子节点，则删除该子树.
3) 测试，删除掉 5 号叶子节点和 3 号子树.
4) 完成删除思路分析
5) 代码实现

1.8 二叉树-删除节点

思考题(课后练习)
1) 如果要删除的节点是非叶子节点，现在我们不希望将该非叶子节点为根节点的子树删除，需要指定规则, 假如规定如下:
2) 如果该非叶子节点A 只有一个子节点B ，则子节点B 替代节点A
3) 如果该非叶子节点A 有左子节点B 和右子节点C ，则让左子节点B 替代节点A。
4) 请大家思考，如何完成该删除功能, 老师给出提示.(课后练习)
5) 后面在讲解二叉排序树时，在给大家讲解具体的删除方法

2、顺序存储二叉树

2.1 顺序存储二叉树的概念

2.1.1 基本说明
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，看下面的示意图。

2.1.2 要求：

上图的二叉树的结点，要求以数组的方式来存放 arr：[1, 2, 3, 4, 5, 6, 7]
要求在遍历数组 arr 时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历

2.1.3 顺序存储二叉树的特点：

顺序二叉树通常只考虑完全二叉树
第n个元素的左子节点为 2 * n + 1
第n个元素的右子节点为 2 * n + 2
第n个元素的父节点为 (n-1) / 2
n：表示二叉树中的第几个元素（按0开始编号如图所示）
2.2 顺序存储二叉树遍历
需求：给你一个数组{1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。前序遍历的结果应当为 1,2,4,5,3,6,7 ```java package com.atguigu.tree;

public class ArrBinaryTreeDemo {

public static void main(String[] args) {
    int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
    // 创建一个 ArrBinaryTree
    ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
    arrBinaryTree.preOrder();     // 1,2,4,5,3,6,7
}

}

// 编写一个ArrayBinaryTree, 实现顺序存储二叉树遍历 class ArrBinaryTree { private int[] arr; //存储数据结点的数组

public ArrBinaryTree(int[] arr) {
    this.arr = arr;
}
// 重载preOrder
public void preOrder() {
    this.preOrder(0);
}
/**
 * 编写一个方法，完成顺序存储二叉树的前序遍历
 * @param index 数组的下标 
 */
public void preOrder(int index) {
    // 如果数组为空，或者 arr.length = 0
    if(arr == null || arr.length == 0) {
        System.out.println("数组为空，不能按照二叉树的前序遍历");
    }
    // 输出当前这个元素
    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);
    }
}

} ``` 课后练习：请同学们完成对数组以二叉树中序，后序遍历方式的代码

2.3 顺序存储二叉树应用实例

八大排序算法中的堆排序，就会使用到顺序存储二叉树，关于堆排序，我们放在<<树结构实际应用>>章节讲解。

3、线索化二叉树

3.1 先看一个问题

将数列 { 1, 3, 6, 8, 10, 14} 构建成一颗二叉树. n+ 1=7

问题分析：

当我们对上面的二叉树进行中序遍历（左中右）时，数列为 {8, 3, 10, 1, 6, 14 }
但是6、8、10、14这几个节点的左右指针，并没有完全的利用上
如果我们希望充分的利用各个节点的左右指针，让各个节点可以指向自己的前后节点，怎么办？
解决方案：线索二叉树

3.2 线索二叉树基本介绍
n个结点的二叉链表中含有 n+ 1【公式 2n-(n- 1)=n+ 1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为”线索”）
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树（Threaded BinaryTree）。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
一个结点的前一个结点，称为前驱结点（8没有前驱节点）
一个结点的后一个结点，称为后继结点（14没有后继节点）

3.3 线索二叉树应用案例
应用案例说明：将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}
思路分析：中序遍历的结果：{8, 3, 10, 1, 14, 6}

说明：当线索化二叉树后，Node节点的属性 left 和 right，有如下情况:
left可能指向的是左子树，也可能是指向的前驱节点。比如①节点 left 指向的左子树, 而⑩节点的 left 指向的就是前驱节点。
right可能指向的是右子树，也可能是指向后继节点，比如①节点 right 指向的是右子树，而⑩节点的 right 指向的是后继节点。
3.4 遍历线索化二叉树
1) 说明：对前面的中序线索化的二叉树，进行遍历
2) 分析：因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致。
3) 代码：

3.5 线索化二叉树的课后作业

我这里讲解了中序线索化二叉树，前序线索化二叉树和后序线索化二叉树的分析思路类似，同学们作为课后作业完成.

三、树结构实际应用

1、堆排序

1.1 堆排序基本介绍

1) 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn) ，它也是不稳定排序。
2) 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
3) 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
4) 大顶堆举例说明

1.2 堆排序基本思想

堆排序的基本思想是：
1) 将待排序序列构造成一个大顶堆
2) 此时，整个序列的最大值就是堆顶的根节点。
3) 将其与末尾元素进行交换，此时末尾就为最大值。
4) 然后将剩余 n- 1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序序列了。

可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.

1.3 堆排序步骤图解说明

要求：给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序。

步骤一构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。原始的数组 [4, 6, 8, 5, 9] 1) .假设给定无序序列结构如下

得到第二大元素。如此反复进行交换、重建、交换。 1) .将堆顶元素 9 和末尾元素 4 进行交换

4) 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

再简单总结下堆排序的基本思路： 1).将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆; 2).将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端; 3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

1.4 堆排序代码实现

要求：给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序。
代码实现：看老师演示:
说明：
1) 堆排序不是很好理解，老师通过 Debug 帮助大家理解堆排序
2) 堆排序的速度非常快，在我的机器上 8 百万数据 3 秒左右。O(nlogn)
3) 代码实现

2、赫夫曼树

2.1 基本介绍

1) 给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。
2) 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近

2.2 赫夫曼树几个重要概念和举例说明

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

2.3 赫夫曼树创建思路图解

给你一个数列 { 13, 7, 8, 3, 29, 6, 1} ，要求转成一颗赫夫曼树.
思路分析(示意图)： { 13, 7, 8, 3, 29, 6, 1}
构成赫夫曼树的步骤：
1) 从小到大进行排序, 将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树
2) 取出根节点权值最小的两颗二叉树
3) 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

4) 再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复 1-2-3-4 的步骤，直到数列中，所有的数
据都被处理，就得到一颗赫夫曼树
5) 图解:

2.4 赫夫曼树的代码实现

代码实现：

3、赫夫曼编码

3.1 基本介绍

1) 赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法
2) 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
3) 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%～90%之间
4) 赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，称之为最佳编码

3.2 原理剖析

通信领域中信息的处理方式 1-定长编码

通信领域中信息的处理方式 2-变长编码

通信领域中信息的处理方式 3-赫夫曼编码
步骤如下;

传输的字符串
1) i like like like java do you like a java
2) d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
3) 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值
步骤：
构成赫夫曼树的步骤：
1) 从小到大进行排序, 将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树
2) 取出根节点权值最小的两颗二叉树
3) 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
4) 再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

4) 根据赫夫曼树，给各个字符,规定编码(前缀编码) ，向左的路径为0 向右的路径为1 ，编码如下: o: 1000 u: 10010 d: 100110 y: 100111 i: 101
a : 110 k: 1110 e: 1111 j: 0000 v: 0001 l: 001 : 01
5) 按照上面的赫夫曼编码，我们的”i like like like java do you like a java” 字符串对应的编码为(注
意这里我们使用的无损压缩)
10101001101111011110100110111101111010011011110111101000011000011100110011110000110
01111000100100100110111101111011100100001100001110 通过赫夫曼编码处理长度为 133 6）长度为： 133
说明:
原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%

此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性赫夫曼编码是无损处理方案

注意事项
注意, 这个赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是 wpl 是一样的，都是最小的, 最后生成的赫夫曼编码的长度是一样，比如: 如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树为:

3.3 最佳实践-数据压缩（创建赫夫曼树）

将给出的一段文本，比如 “i like like like java do you like a java” ，根据前面的讲的赫夫曼编码原理，对其进行数
据压缩处理，形式如

“1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100 110111101111011100100001100001110
“

步骤 1 ：根据赫夫曼编码压缩数据的原理，需要创建 “i like like like java do you like a java” 对应的赫夫曼树.

思路：前面已经分析过了，而且我们已然讲过了构建赫夫曼树的具体实现。
代码实现：看老师演示:

3.4 最佳实践-数据压缩（生成赫夫曼编码和赫夫曼编码后的数据）

我们已经生成了赫夫曼树, 下面我们继续完成任务
1) 生成赫夫曼树对应的赫夫曼编码 , 如下表:
=01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010j=0010 k=1111 l=000 o=0011
2) 使用赫夫曼编码来生成赫夫曼编码数据 , 即按照上面的赫夫曼编码，将”i like like like java do you like a java” 字符串生成对应的编码数据, 形式如下.
10101000101111111100100010111111110010001011111111001001010011011100011100000110111010001111001010
00101111111100110001001010011011100
3) 思路：前面已经分析过了，而且我们讲过了生成赫夫曼编码的具体实现。
4) 代码实现：看老师演示:

3.5 最佳实践-数据解压(使用赫夫曼编码解码)

使用赫夫曼编码来解码数据，具体要求是
1) 前面我们得到了赫夫曼编码和对应的编码
byte[] , 即:[-88, -65, -56, -65, -56, -65, -55, 77
, -57, 6, -24, - 14, - 117, -4, -60, -90, 28]
2) 现在要求使用赫夫曼编码，进行解码，又
重新得到原来的字符串”i like like like java do you like a java”
3) 思路：解码过程，就是编码的一个逆向操作。
4) 代码实现：看老师演示:

3.6 最佳实践-文件压缩

我们学习了通过赫夫曼编码对一个字符串进行编码和解码, 下面我们来完成对文件的压缩和解压，具体要求：
给你一个图片文件，要求对其进行无损压缩, 看看压缩效果如何。
1) 思路：读取文件-> 得到赫夫曼编码表 -> 完成压缩
2) 代码实现：

3.7 最佳实践-文件解压（文件恢复）

具体要求：将前面压缩的文件，重新恢复成原来的文件。
1) 思路：读取压缩文件(数据和赫夫曼编码表)-> 完成解压(文件恢复)
2) 代码实现：

3.8 代码汇总，把前面所有的方法放在一起

3.9 赫夫曼编码压缩文件注意事项

1) 如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件 [举例压一个 .ppt]
2) 赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件) [举例压一个.xml 文件]
3) 如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显.

4、二叉排序树

4.1 先看一个需求

给你一个数列 (7, 3, 10, 12, 5, 1, 9) ，要求能够高效的完成对数据的查询和添加

4.2 解决方案分析

使用数组
数组未排序，优点：直接在数组尾添加，速度快。缺点：查找速度慢. [示意图]
数组排序，优点：可以使用二分查找，查找速度快，缺点：为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢。[示意图]

使用链式存储-链表
不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动。[示意图]

使用二叉排序树

4.3 二叉排序树介绍

二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点

比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：

4.4 二叉排序树创建和遍历

一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9) ，创建成对应的二叉排序树为 :

4.5、二叉排序树的删除

二叉排序树的删除情况比较复杂，有下面三种情况需要考虑
1) 删除叶子节点 (比如：2, 5, 9, 12)
2) 删除只有一颗子树的节点 (比如：1)
3) 删除有两颗子树的节点. (比如：7, 3 ，10 )
4) 操作的思路分析

4.6 二叉排序树删除结点的代码实现:

4.7 课后练习：完成老师代码，并使用第二种方式来解决

如果我们从左子树找到最大的结点，然后前面的思路完成.

5、平衡二叉树（AVL 树）

5.1 看一个案例（说明二叉排序树可能的问题）

给你一个数列{1,2,3,4,5,6} ，要求创建一颗二叉排序树(BST), 并分析问题所在.
左边 BST 存在的问题分析:
1) 左子树全部为空，从形式上看，更像一个单链表.
2) 插入速度没有影响
3) 查询速度明显降低(因为需要依次比较), 不能发挥 BST

的优势，因为每次还需要比较左子树，其查询速度比
单链表还慢
4) 解决方案-平衡二叉树(AVL)

5.2 基本介绍

1) 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为 AVL 树，可以保证查询效率较高。
2) 具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1 ，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL 、替罪羊树、Treap 、伸展树等。
3) 举例说明, 看看下面哪些 AVL 树, 为什么?

5.3 应用案例 - 单旋转（左旋转）

1) 要求: 给你一个数列，创建出对应的平衡二叉树.数列 {4,3,6,5,7,8}
2) 思路分析(示意图)

3) 代码实现

5.4 应用案例 - 单旋转（右旋转）

1) 要求: 给你一个数列，创建出对应的平衡二叉树.数列 { 10, 12, 8, 9, 7, 6}
2) 思路分析(示意图)

3) 代码实现

5.5 应用案例 - 双旋转

前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列
int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL 树.
int[] arr = {2, 1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL 树
1) 问题分析

2) 解决思路分析
1. 当符号右旋转的条件时
2. 如果它的左子树的右子树高度大于它的左子树的高度

先对当前这个结点的左节点进行左旋转
4. 在对当前结点进行右旋转的操作即可
3) 代码实现[AVL 树的汇总代码(完整代码)]

四、多路查找树

1、二叉树与B 树

1.1 二叉树的问题分析

二叉树的操作效率较高，但是也存在问题, 请看下面的二叉树

1) 二叉树需要加载到内存的，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多(比如1 亿) ，就存在如下问题:
2) 问题 1 ：在构建二叉树时，需要多次进行 i/o 操作(海量数据存在数据库或文件中) ，节点海量，构建二叉树时，速度有影响
3) 问题 2 ：节点海量，也会造成二叉树的高度很大，会降低操作速度.

1.2 多叉树

1) 在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树（multiway tree）
2) 后面我们讲解的 2-3 树，2-3-4 树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。
3) 举例说明(下面 2-3 树就是一颗多叉树)

1.3 B 树的基本介绍

B 树通过重新组织节点，降低树的高度，并且减少 i/o 读写次数来提升效率。

1) 如图B 树通过重新组织节点，降低了树的高度.
2) 文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(页得大小通常为 4k)，这样每个节点只需要一次 I/O 就可以完全载入
3) 将树的度 M 设置为 1024 ，在 600 亿个元素中最多只需要 4 次 I/O 操作就可以读取到想要的元素, B 树(B+)广泛应用于文件存储系统以及数据库系统中

2、2-3 树

2.1 2-3 树是最简单的 B 树结构, 具有如下特点:

1) 2-3 树的所有叶子节点都在同一层.(只要是 B 树都满足这个条件)
2) 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点.
3) 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点.
4) 2-3 树是由二节点和三节点构成的树。

2.2 2-3 树应用案例

将数列{16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20} 构建成 2-3 树，并保证数据插入的大小顺序。(演示一下构建 2-3 树的过程.)

插入规则:
1) 2-3 树的所有叶子节点都在同一层.(只要是 B 树都满足这个条件)
2) 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点.
3) 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
4) 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面 3 个条件。
5) 对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则

2.3 其它说明

除了23 树，还有234 树等，概念和23 树类似，也是一种B 树。如图:

3、B 树、B+树和B*树

3.1 B 树的介绍

B-tree 树即 B 树，B 即 Balanced ，平衡的意思。有人把 B-tree 翻译成 B-树，容易让人产生误解。会以为B-树是一种树，而 B 树又是另一种树。实际上，B-tree 就是指的 B 树。

3.2 B 树的介绍

前面已经介绍了 2-3 树和 2-3-4 树，他们就是 B 树(英语：B-tree 也写成 B-树) ，这里我们再做一个说明，我们在学习 Mysql 时，经常听到说某种类型的索引是基于B 树或者B+树的，如图:

对上图的说明:
1) B 树的阶：节点的最多子节点个数。比如 2-3 树的阶是 3 ，2-3-4 树的阶是 4
2) B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点

3) 关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据.
4) 搜索有可能在非叶子结点结束
5) 其搜索性能等价于在关键字全集内做一次二分查找

3.3 B+树的介绍

B+树是 B 树的变体，也是一种多路搜索树。

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

3.4 B*树的介绍

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

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

五、图

1、图基本介绍

1.1 为什么要有图

1) 前面我们学了线性表和树
2) 线性表局限于一个直接前驱和一个直接后继的关系
3) 树也只能有一个直接前驱也就是父节点
4) 当我们需要表示多对多的关系时，这里我们就用到了图。

1.2 图的举例说明

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

1.3 图的常用概念

1) 顶点(vertex)
2) 边(edge)
3) 路径
4) 无向图(右图
5) 有向图
6) 带权图

2、图的表示方式

图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。

2.1 邻接矩阵

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于 n 个顶点的图而言，矩阵是的row 和col 表示的是1….n 个点。

2.2 邻接表

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

3、图的快速入门案例

1) 要求: 代码实现如下图结构.

2) 思路分析 ( 1) 存储顶点 String 使用 ArrayList (2) 保存矩阵 int[][] edges
3) 代码实现

4、图的深度优先遍历介绍

4.1 图遍历介绍

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

4.2 深度优先遍历基本思想

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

4.3 深度优先遍历算法步骤

1) 访问初始结点 v ，并标记结点 v 为已访问。
2) 查找结点v 的第一个邻接结点 w。
3) 若 w 存在，则继续执行 4 ，如果 w 不存在，则回到第 1 步，将从 v 的下一个结点继续。
4) 若w 未被访问，对w 进行深度优先遍历递归（即把w 当做另一个 v ，然后进行步骤 123）。
5) 查找结点v 的w 邻接结点的下一个邻接结点，转到步骤3。
6) 分析图

4.4 深度优先算法的代码实现

5、图的广度优先遍历

5.1 广度优先遍历基本思想

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

5.2 广度优先遍历算法步骤

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

非线性结构