数据结构.md · vvwhy/java_algorithm

# Java数据结构

[TOC]

## 一、数据结构和算法的关系

数据结构时一门研究组织数据方式的学科

**程序  = 数据结构 + 算法**

## 二、数据结构

**线性结构：**

- 最常用的数据结构，数据元素之间存在一对一的线性关系
- 两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中存储的元素是连续的
- 链式存储的线性表叫链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
- 线性结构常见的有：数组、队列、链表和栈

**非线性结构：**

- 包括：二维数组，多维数组，广义表，树结构，图结构

## 三、稀疏数组

#### 3.1 稀疏数组的应用场景

**问题：**五子棋程序，存盘退出和续上盘的功能

**定义：**二维数组很多值都是默认值0，或者大多数值都相同，这些数据没有意义，该数组可用稀疏数组保存。

**处理方法：**

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

**举例**

![image-20201015202619020](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126170051728-2069335385.png)

**用二维数组记录行列值**

#### 3.2 稀疏数组思路分析

**二维数组转稀疏数组**

1. 遍历原始二维数组，得到有效数据的个数sum
2. 根据sum创建稀疏数组aparseArr int【sum+1】
3. 将二维数组的有效数据存入到稀疏数组中

**稀疏数组转二维数组的思路**

1. 读取稀疏数组的第一行，根据第一行数据创建原始二维数组
2. 读取后几行数据，并赋值给原始的二维数组

#### 3.3 稀疏数组代码实现

```Java
package com.why.data_structure;

import com.sun.nio.sctp.SctpStandardSocketOptions;

/**
 * @Description TODO 稀疏数组实现类
 * @Author why
 * @Date 2020/10/15 20:49
 * Version 1.0
 **/
public class SparseArr {

/**
     * 创建原始的二维数组11*11
     * 1-表示黑子，2-表示白子
     */
    int[][] chessArr1 = new int[11][11];

public int[][] getChessArr1() {
        return chessArr1;
    }

public void setChessArr1(int[][] chessArr1) {
        this.chessArr1 = chessArr1;
    }

public SparseArr() {
        chessArr1[1][2] = 1;
        chessArr1[3][3] = 2;
    }

/**
     * 原始二维数组转换为稀疏数组
     * @param arr
     * @return
     */
    public static int[][] change1(int[][] arr){
        //打印输出原始二维数组
        System.out.println("原始二维数组");
        //设置两个计数器计数行数和列数
        int count1 = 0;
        int count2 = 0;
        for (int i = 0; i < 1; i++) {
            for (int data: arr[0]
                 ) {
                count2++;
            }
        }
        for (int[] row : arr) {
            count1++;
            System.out.println();
            for (int data : row) {
                System.out.printf("%d\t",data);
            }
        }
        //先遍历获得二维数组的数据个数
        int sum = 0;
        for (int i = 0; i < count1; i++) {
            for (int j = 0; j < count2; j++) {
                if (arr[i][j]!=0){
                    sum++;
                }
            }
        }

//创建对应的稀疏数组
        int[][] sparseArr = new int[sum+1][3];
        //给稀疏数组赋值
        sparseArr[0][0] = count1;
        sparseArr[0][1] = count2;
        sparseArr[0][2] = sum;

System.out.println("sun=m"+sum);
        System.out.println();

int count = 1;
        //遍历二维数组将非零的值存放至稀疏数组中
        for (int i = 0; i < count1; i++) {
            for (int j = 0; j < count2; j++) {
                if (arr[i][j]!=0){
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = arr[i][j];
                    count++;
                }
            }
        }
        return sparseArr;
    }

/**
     * 稀疏数组转二维数组
     * @param arr
     * @return
     */
    public static int[][] change2(int[][] arr){
        //打印输出原始二维数组
        System.out.println("稀疏数组");
        //设置两个计数器计数行数和列数
        int count1 = 0;
        int count2 = 0;
        for (int i = 0; i < 1; i++) {
            for (int data: arr[0]
            ) {
                count2++;
            }
        }
        for (int[] row : arr) {
            count1++;
            System.out.println();
            for (int data : row) {
                System.out.printf("%d\t",data);
            }
        }

int row = 0;int column = 0;int sum = 0;
        row = arr[0][0];
        column = arr[0][1];
        sum = arr[0][2];

int[][] newArr = new int[row][column];

for (int i = 1; i < sum+1; i++) {
            newArr[arr[i][0]][arr[i][1]] = arr[i][2];
        }

for (int[] rowx: newArr
             ) {
            for (int data: rowx
                 ) {
                if (data != 1 || data != 2){
                    data = 0;
                }
            }
        }

return newArr;
    }

public static void main(String[] args) {
        SparseArr sparseArr = new SparseArr();
        int[][] arr = change1(sparseArr.getChessArr1());
        System.out.println();
        System.out.println("稀疏数组为：");
        for (int[] row : arr) {
            System.out.println();
            for (int data : row) {
                System.out.printf("%d\t",data);
            }
        }

System.out.println();

System.out.println();
        int[][] arr2 = change2(arr);
        System.out.println();
        System.out.println("原数组：");
        for (int[] row : arr2) {
            System.out.println();
            for (int data : row) {
                System.out.printf("%d\t",data);
            }
        }
    }
}
```

## 四、队列（Queue）

#### 4.1 队列的应用场景

银行排队案例，买票案例

**队列概述**

- 队列是一个有序列表，可以用**数组**或是**链表**来表现
- 遵循先进先出的元组

#### 4.2 队列的实现方式

##### 4.2.1 数组形式

![image-20201016083130818](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126170216769-613126359.png)

![image-20201016083429638](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126170221291-644034698.png)

**代码实现**

```Java
package com.why.data_structure.queue;

import java.awt.*;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @Description TODO 用数组模拟队列
 * @Author why
 * @Date 2020/10/16 8:40
 * Version 1.0
 **/
public class ArrayQueueDemo {
    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(20);
        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 'a':
                    System.out.println("输入一个数");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = arrayQueue.subQueue();
                        System.out.printf("取出的数据是%d\n",res);
                    }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;
                case 'e':
                    scanner.close();
                    loop = false;
                    System.out.println("程序退出");
                    break;
                default:
                    break;

}
        }
    }
}

//编写一个数组模拟队列的类
class ArrayQueue{
    private int maxSize;//数组最大容量
    private int front;//队列头
    private int rear;//队列尾部
    private int[] arr;//存放数据，模拟队列

/**
     * 队列初始化，构造队列
     * @param maxSize
     */
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = -1;//指向队列头部
        rear = -1;//指向队列尾部
    }

/**
     * 判断队列是否为满
     * @return
     */
    public boolean isFull(){
        return rear == maxSize - 1;
    }

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

/**
     * 入队，添加数据
     * @param n
     */
    public void addQueue(int n){
        //判满
        if (isFull()){
            System.out.println("队列已满！不可添加数据！");
            return;
        }
        rear+=1;//rear后移
        arr[rear] = n;
    }

/**
     * 出队获得队列的值
     * @return
     */
    public int subQueue(){
        //判空
        if (isEmpty()){
            throw new RuntimeException("队列为空！");
        }
        return arr[front+=1];
    }

/**
     * 显示队列所有数据
     */
    public void showQueue(){
        //遍历
        if (isEmpty()){
            System.out.println("队列空");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n",i,arr[i]);
        }
    }

/**
     * 显示头数据
     * @return
     */
    public int headQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列空");
        }
        return arr[front+1];
    }
    public ArrayQueue() {
    }

public int getMaxSize() {
        return maxSize;
    }

public void setMaxSize(int maxSize) {
        this.maxSize = maxSize;
    }

public int getFront() {
        return front;
    }

public void setFront(int front) {
        this.front = front;
    }

public int getRear() {
        return rear;
    }

public void setRear(int rear) {
        this.rear = rear;
    }

public int[] getArr() {
        return arr;
    }

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

@Override
    public String toString() {
        return "ArrayQueue{" +
                "maxSize=" + maxSize +
                ", front=" + front +
                ", rear=" + rear +
                ", arr=" + Arrays.toString(arr) +
                '}';
    }
}
```

**问题分析**

- 目前数组使用一次就不能使用，达不到复用的效果
- 使用算法，改进成环形队列

#### 4.3 数组模拟环形队列

**思路如下**

1. front变量含义做调整，front指向数组队列的第一个元素，也就是说arr[front]是队列的第一个元素

2. rear变量含义做调整，rear指向队列的最后一个元素的后一个位置，希望空出一个空间作为一个约定

3. 初始化 front = 0；rear = 0；

4. 当队列满时，条件是（rear+1）% maxSize == front（满）

5. 当队列为空时，条件是rear == front(空)

6. 队列中有效的数据个数为：（rear+maxSize-front）% maxSize

**环形队列代码实现**

```Java
package com.why.data_structure.queue;

import java.util.Scanner;
import java.util.concurrent.CountDownLatch;

/**
 * @Description TODO 环形队列实现与测试
 * @Author why
 * @Date 2020/10/16 11:01
 * Version 1.0
 **/
public class RingQueueDemo {
    public static void main(String[] args) {

//设置5有效数据最大为4，有一个预留空间
        RingQueue ringQueue = new RingQueue(5);
        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':
                    ringQueue.getAll();
                    break;
                case 'a':
                    System.out.println("输入一个数");
                    int value = scanner.nextInt();
                    ringQueue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = ringQueue.subQueue();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = ringQueue.headQueue();
                        System.out.printf("数据头数据是%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    System.out.println("程序退出");
                    break;
                default:
                    break;
            }
        }
    }
}

class RingQueue{
    private int front;//头指针
    private int  rear;//尾指针
    private int[] arrayArr;//存放数据的数组
    private int maxSize;//最大容量

/**
     * 初始化设置最大容量，将front = 0; rear = 0
     * @param maxSize
     */
    public RingQueue(int maxSize) {
        this.maxSize = maxSize;
        front = 0;
        rear = 0;
        arrayArr = new int[maxSize];
    }

/**
     * 判满
     */
    public boolean isFull(){
        return (rear +1) % maxSize == front;
    }

/**
     * 判空
     */
    public boolean isEmpty(){
        return rear == front;
    }

/**
     * 入队，添加数据
     * @param n
     */
    public void addQueue(int n){
        if (isFull()){
            System.out.println("队列已满，不可添加数据");
            return;
        }
        arrayArr[rear] = n;
        rear = (rear+1) % maxSize;
    }

/**
     * 出队
     * @return
     */
    public int subQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空，无数据可取");
        }
        int value = arrayArr[front];
        front = (front+1)%maxSize;
        return value;
    }

/**
     * 输出所有数据
     */
    public void getAll(){
        //遍历
        if (isEmpty()){
            System.out.println("队列空");
            return;
        }
        //思路
        //从front开始遍历遍历（rear+maxSize-front）% maxSize个元素
        for (int i = front; i <front+size(); i++) {
            System.out.printf("arr[%d]=%d\n",i%maxSize,arrayArr[i%maxSize]);
        }
    }

/**
     * 显示头数据
     * @return
     */
    public int headQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列空");
        }
        return arrayArr[front];
    }

public int size(){
        return (rear+maxSize-front)% maxSize;
    }

public RingQueue() {
    }
}
```

## 五、链表（Linked-List）

### 5.1 单链表

链表（linked list）有序列表，但是存储不连续

**特点：**

- 以节点形式存储
- 每个节点包括data域，next域：指向下一节点
- 链表的各个节点不一定时连续存放的
- 链表分带头节点的链表和无头节点的链表，根据实际需求确定

#### 5.1.1 应用实例

使用带head节点的单向链表实现——水浒英雄排行榜管理

1. 完成对英雄人物的增删改查操作
2. 添加时两种方法，直接添加至链表尾部，或插入至指定位置

**分析：**

- **创建英雄节点（class，存放信息**），创建头节点时，不存放数据表示单链表的头

```Java
  /**
   * 定义一个HeroNode,每隔HeroNode对象就是一个节点
   */
  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;
      }
  
      public HeroNode() {
      }
  
      @Override
      public String toString() {
          return "HeroNode{" +
                  "no=" + no +
                  ", name='" + name + '\'' +
                  ", nickname='" + nickname + '\'' +
                  '}';
      }
  
  
  }
  ```

- **添加功能（不考虑顺序）**

1. 先创建head节点，作用是表示单链表的头
  2. 后面没添加一个节点，就直接加入到链表的尾部

```Java
  /**
   * 添加节点到单项链表
   * 思路当不考虑编号顺序是
   * 1.找到链表的最后一个节点
   * 2.将最后节点的next指向新节点
   * @param heroNode
   */
  public void add(HeroNode heroNode){
      //定义一个辅助变量
      HeroNode temp = head;
  
      //遍历链表，找到最后
      while (true){
          //找到链表最后
          if (temp.next == null){
              break;
          }
          //如果没有找到temp后移
          temp = temp.next;
      }
      //退出循环找到最后的节点
      //将最后这个节点指向新的节点
      temp.next = heroNode;
  }
  ```

- **添加功能（考虑顺序）**

1. 首先找到新添加节点的位置，通过辅助变量
  2. 新的节点.next = temp.next
  3. 将temp.next = 新的节点

```Java
  /**
   * 添加功能考虑顺序
   * @param heroNode
   */
  public void addOrder(HeroNode heroNode){
      //定义辅助变量
      HeroNode temp = head;
  
      //标志添加编号是否存在，默认为false
     boolean flag = false;
     while (true){
         if (temp.next == null){//已经在链表最后
             break;
         }
         if (temp.next.no>heroNode.no){
             //位置找到了，在temp后插入
             break;
         }else if (temp.next.no == heroNode.no){
             //数据已存在
             flag = true;
             break;
         }
         temp = temp.next;//后移，遍历当前链表
     }
  
     //判断flag的值
      if (flag == true){
          //不能添加，编号存在
          System.out.println("编号存在:"+temp.next.no+","+temp.next.name);
      }else {
          heroNode.next = temp.next;
          temp.next = heroNode;
      }
  }
  ```

- **遍历：**通过辅助变量，遍历单链表

- **修改功能**

编号不变，昵称等其他信息改变

```Java
  /**
   * 根据根节点的id修改相应的值
   * @param heroNode
   */
  public void update(HeroNode heroNode){
      HeroNode temp = head.next;
      while (true){
          if (temp.no == heroNode.no){
              break;
          }
          temp = temp.next;
      }
      temp.name = heroNode.name;
      temp.nickname = heroNode.nickname;
  }
  ```

- **删除节点**

```Java
  /**
   * 根据id删除节点
   * @param id
   */
  public void delete(int id){
      HeroNode temp = head;
      while (true){
          if (temp.next.no == id){
              break;
          }
          temp = temp.next;
      }
      temp.next = temp.next.next;
  }
  ```

- **清空链表**

```Java
  /**
   * 清空链表
   */
  public void clear(){
      HeroNode temp = head;
      temp = temp.next = null;
  }
  ```

#### 5.1.2 单链表的面试题

1. 求单链表中节点的个数

```Java
   /**
    * 求单链表中节点的个数
    * 遍历单链表
    * 计数器
    */
   public void getLen(){
   
       HeroNode temp = head;
       int count = 0;
       while (true){
           if (temp.next==null){
               break;
           }
           temp = temp.next;
           count++;
       }
       System.out.println("共有"+count+"个节点！");
   }
   ```

2. 查找单链表中倒数第k个节点

```Java
   /**
    * 查找单链表倒数第k个节点
    * 思路：
    * 链表 从头到尾遍历
    * 链表长度-id，结尾查找的节点
    * @param id
    */
   public HeroNode selectByID(int id){
       int len = getLen();
       HeroNode temp = head.next;
       for (int i = 0; i < len-id; i++) {
           temp = temp.next;
       }
       return temp;
   }
   ```

3. 单链表的反转

```Java
   /**
        * 反转链表
        * 思路：
        *      1.定义一个节点reverseHead = new HeroNode()
        *      2.从头到尾遍历原理啊的链表，每遍历一个节点，将其取出，并放在新的链表的最前端
        *      3.原来的链表的head.next=reverseHead.next
        */
       public void reverse(){
           HeroNode reverseHead = new HeroNode();
           HeroNode temp1 = head.next;
           //指向当前节点的下一节点
           HeroNode next = null;
           if (temp1 == null || temp1.next == null){
               return ;
           }
   
           //遍历原来的链表，每遍历一个节点，将其取出，并放在新的链表的最前端
           while (temp1 != null){
               next = temp1.next;//暂时保存当前节点的下一节点
               temp1.next = reverseHead.next;//将temp1的下一节点指向新链表的最前端
               reverseHead.next = temp1;//将temp1连接到新的链表上
               temp1 = next;//后移一次
           }
           //将head.next指向reverseHead.next，实现反转
           head.next = reverseHead.next;
       }
   }
   ```

4. 从尾到头打印单链表【要求方式1：反向遍历。方式2：Stack栈】

```Java
   /**
        * 从尾到头打印单链表
        * 思路一：
        *      先将单链表反转，然后遍历
        *      缺点：破坏原来单链表的结构
        * 思路二：
        *      利用栈，压栈后，利用栈先进后出的特点，实现逆序打印
        *
        */
       public void reversePrint(){
           //创建栈
           Stack<HeroNode> stack = new Stack<>();
           HeroNode temp = head.next;
           if (temp == null){
               return;
           }
           while (temp != null){
               stack.push(temp);
               temp = temp.next;
           }
           while (stack.size()>0){
               System.out.println(stack.pop());
           }
       }
   }
   ```

5. 合并两个有序的单链表，合并之后链表依然有序

### 5.2 双向链表

```Java
package com.why.linkedlist;

/**
 * @Description TODO 双向链表创建，功能和测试类
 * @Author why
 * @Date 2020/10/19 10:23
 * Version 1.0
 **/

import java.util.List;

/**
 * 测试类
 */
public class BidirectionalListDemo {
    public static void main(String[] args) {
        BidirectionalList bl = new BidirectionalList();
        ListNode node1 = new ListNode(1,"lrx","123");
        ListNode node2 = new ListNode(2,"cjl","123");
        ListNode node3 = new ListNode(3,"why","123");
        ListNode node4 = new ListNode(3,"wl","123");

bl.insert(node1);
        bl.insert(node2);
        bl.insert(node3);
        System.out.println("原数据");
        bl.list();

System.out.println("修改");
        System.out.println();
        bl.update(node4);
        bl.list();

System.out.println("删除");
        System.out.println();
        bl.delete(3);
        bl.list();
    }
}

/**
 * 功能实现类
 */
class BidirectionalList{

//建立头节点
    ListNode head = new ListNode(0,"","");

/**
     * 判空
     * @return
     */
    public boolean isEmpty(){
        if (head.next == null){
            System.out.println("链表为空");
            return true;
        }
        return false;
    }

/**
     * 从头至尾遍历，显示
     * @return
     */
    public void list(){
        boolean empty = isEmpty();
        ListNode temp = head.next;
        if (empty == true){
            return;
        }
        while (temp!=null){
            System.out.println(temp);
            temp = temp.next;
        }
    }

/**
     * 添加到双向链表的最后
     * @param node
     */
    public void insert(ListNode node){
        ListNode temp = head;
        while (temp.next != null){
            temp = temp.next;
        }
        temp.next = node;
        node.pre = temp;
    }

/**
     * 添加到指定位置之后
     */
    public void insertSpecified(ListNode node,int id){
        ListNode temp = head.next;
        while (true){
            if (temp.no == id){
                node.next = temp.next;
                temp.next.pre = node;
                temp.next = node;
                node.pre = temp;
                break;
            }
            temp = temp.next;
        }
    }

/**
     * 修改数据，根据no查找
     * @param node
     */
    public void update(ListNode node){
        boolean empty = isEmpty();
        if (empty){
            return;
        }
        ListNode temp = head.next;
        while (true){
            if (temp.no == node.no){
               break;
            }
            temp = temp.next;
        }
        temp.name = node.name;
        temp.password = node.password;
    }

/**
     * 删除节点
     * 对于双向链表可直接找到要删除的节点，
     * 找到后自我删除即可
     * @param id
     */
    public void delete(int id){
        //判断当前链表是否为空
        if (isEmpty()){
            System.out.println("不存在");
            return;
        }
        ListNode temp = head.next;
        while (true){
            if (temp == null){
                return;
            }
            if (temp.no == id){
                break;
            }
            temp = temp.next;
        }
        temp.pre.next = temp.next;
        //这里有问题，如果最后一个节点不需要执行，否则会出现空指针异常
        if (temp.next !=null){
            temp.next.pre = temp.pre;
        }
    }
}

/**
 * 节点类
 */
class ListNode{
    public int no;
    public String name;
    public String password;
    public ListNode pre;
    public ListNode next;

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

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

### 5.3 环形链表和约瑟夫问题（约瑟夫环）

#### 5.3.1 约瑟夫(Josephu)问题

设编号为1，2，...，n的n个人围坐一圈，约定编号weik（1<=k<=n）的人从1开始报数，疏导m的那个人出列，他的下一位又从1开始报数，数到m的那个人又出列，依此类推，直到所有人出列为止，由此产生一个出队编号的序列

**解决思路：**

使用环形链表

#### 5.3.2 环形列表

**创建环形链表思路：**

1. 创建第一个节点，让first指向该节点，并形成环形
2. 后面每创建一个新的节点，就把该节点加入到已有的环形链表中

**遍历环形链表思路：**

1. 先让辅助指针temp，指向first节点
2. 然后通过while循环遍历该环形链表即可
3. 循环结束条件temp.next = =first

**删除指定位置节点**

1. 根据用户输入id，删除
2. 找到节点
3. temp.pre.next = temp.next
4. temp.next.pre = temp.pre

**代码实现**

```Java
package com.why.linkedlist;

import java.awt.*;

/**
 * @Description TODO 环形链表节点，功能实现，测试类
 * @Author why
 * @Date 2020/10/20 10:07
 * Version 1.0
 **/
public class RingLinkedListDemo {
    public static void main(String[] args) {
        RingLinkedList rl = new RingLinkedList();
        rl.add(20);
        System.out.println("原数据");
        rl.list();
        rl.delete(5);
        System.out.println("删除后：");
        rl.list();
    }
}

/**
 * 功能实现类
 */
class RingLinkedList{
    //创建first节点目前不要赋值，当前无编号
    private RingNode first = new RingNode();

/**
     * 添加节点
     * @param nums
     */
    public void add(int nums){
        //nums做数据校验
        if (nums<1){
            System.out.println("数据不合法！！！");
            return;
        }
        RingNode temp = null;//辅助指针帮助构建环形链表
        //使用循环创建环形链表
        for (int i = 1; i <= nums; i++) {
            //根据编号创建节点
            RingNode node = new RingNode(i);
            //第一个节点，赋值,，形成环状
            if (i == 1){
                first = node;
                first.next = first;
                first.pre = first;
                temp = first;
            }else {
                temp.next = node;
                first.pre = node;
                node.pre = temp;
                node.next = first;
                temp = node;
            }
        }
    }

/**
     * 遍历打印
     */
    public void list(){
        //判空
        if (first == null){
            System.out.println("链表空");
            return;
        }
        RingNode temp = first;
        while (true){
            System.out.println(temp);
            if (temp.next == first){
                break;
            }
            temp = temp.next;
        }
    }

public void delete(int id){
        RingNode temp = first;
        while (true){
            if (id == temp.no){
                temp.pre.next = temp.next;
                temp.next.pre = temp.pre;
                System.out.println("出队的："+temp);
                break;
            }
            temp = temp.next;
        }
    }
}

/**
 * 节点类
 */
class RingNode{
    public int no;
    public RingNode next;
    public RingNode pre;

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

public RingNode() {
    }

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

public int getNo() {
        return no;
    }

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

}
```

## 六、栈(Stack)

### 6.1 实际需求

计算7*2*2-5+1-5+3-3

对于计算机而言，其接收到的就是一个字符串

计算机底层如何计算获得结果？

### 6.2 栈的介绍

- 栈是一个先入后出的有序列表
- 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底。
- 最先放入的元素在栈底，最后放入的元素在栈顶
- 删除元素从栈顶开始删除

### 6.3 栈的应用场景

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

### 6.4 用数组模拟栈，并实现其功能

#### 6.4.1 思路分析

1. 使用数组模拟栈
2. 定义top变量，表示栈顶，初始化：top = -1
3. **入栈**：当有数据加入到栈时top++；stack[top] = data;
4. **出栈**：value = stack[top];top--;return value
5. **遍历栈：**从栈顶开始显示

#### 6.4.2 代码实现

```Java
/**
 * 表示栈
 */
class StackModel{
    private int maxSize;//栈的最大容量
    private int top = -1;//栈顶
    private int[] stack;//数组模拟栈

public StackModel(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

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

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

/**
     * 入栈
     * @param data
     */
    public void push(int data){
       if (isFull()){
           System.out.println("栈满");
           return;
       }
       top++;
       stack[top] = data;
    }

/**
     * 出栈
     * @return
     */
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空");
        }
        int value = stack[top];
        top--;
        return value;
    }

/**
     * 遍历栈
     * 从栈顶显示数据
     */
    public void list(){
        if (isEmpty()){
            System.out.println("栈空");
            return;
        }
        for (int i = top; i >=0; i--) {
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }

public StackModel() {
    }

public int getMaxSize() {
        return maxSize;
    }

public void setMaxSize(int maxSize) {
        this.maxSize = maxSize;
    }

public int getTop() {
        return top;
    }

public void setTop(int top) {
        this.top = top;
    }

public int[] getStack() {
        return stack;
    }

public void setStack(int[] stack) {
        this.stack = stack;
    }

@Override
    public String toString() {
        return "StackModel{" +
                "maxSize=" + maxSize +
                ", top=" + top +
                ", stack=" + Arrays.toString(stack) +
                '}';
    }
}
```

### 6.5 用链表实现栈

```Java
class LinkStack{
    private StackNode first;
    private int top = -1;
    private int maxSize;

public LinkStack(int maxSize) {
        this.maxSize = maxSize;
        first = new StackNode();
    }

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

/**
     * 判空
     * @return
     */
   public boolean isEmpty() {
       return top == -1;
   }

/**
     * 压栈
     * @param data
     */
   public void push(int data){
       if (isFull()){
           System.out.println("栈满");
           return;
       }
       top++;
       StackNode temp = first;
       temp.setData(data);
       temp = temp.getNext();
   }

public int pop(){
       if (isEmpty()){
           throw new RuntimeException("栈空");
       }
       StackNode temp = first;
       while (temp.getNext() != null){
           temp = temp.getNext();
       }
       int value = temp.getData();
       temp = temp.getPre();
       top--;
       return value;
   }
    /**
     * 显示栈
     */
   public void list(){
       if (isEmpty()){
           System.out.println("栈空");
           return;
       }
       StackNode temp = first;
       while (temp.getNext() != null){
           temp = temp.getNext();
       }
       for (int i = top; i >=0 ; i--) {
           System.out.println(i+"-"+temp.getData());
           temp = temp.getPre();
       }
   }
}

class StackNode{
    private int data;
    private StackNode next;
    private StackNode pre;

public StackNode(int data) {
        this.data = data;
    }

public StackNode() {
    }

public int getData() {
        return data;
    }

public void setData(int data) {
        this.data = data;
    }

public StackNode getNext() {
        return next;
    }

public void setNext(StackNode next) {
        this.next = next;
    }

public StackNode getPre() {
        return pre;
    }

public void setPre(StackNode pre) {
        this.pre = pre;
    }

@Override
    public String toString() {
        return "StackNode{" +
                "data=" + data +
                '}';
    }
}
```

### 6.6 栈实现综合计算器

#### 6.6.1 思路

1. 设计两个栈，数栈（numStack，存放数据）和符号栈（operStack，存放运算符）
2. 通过index索引，遍历计算的表达式
3. 若index得到一个数字，直接放入数栈，若得到符符号，分如下两种情况：
   - 3.1 若当前符号栈为空，直接入栈
   - 3.2 若符号栈不为空，就进行比较。
     - 3.2.1 如果当前的操作符的优先级小于或等于栈中的操作符，就需要从数栈中pop出两个数，再从符号栈中pop出一个符号，进行运算，将得到的结果入数栈，把当前的操作符入符号栈
     - 如果当前操作符优先级大于栈中的操作符，直接入符号栈
4. 扫描完毕后，就顺序的从数栈和符号栈pop出相应的书和符号并运算
5. 最后在数栈中只有一个数据，即为表达式结果

### 6.7 前缀、中缀和后缀表达式

**前缀表达式（波兰表达式）**

- 运算符位于操作数之前
- 如：（3+4）* 5 - 6对应的前缀表达式 - * + 3 4 5 6
- **求值流程：**
  1. 从右向左扫描表达式
  2. 遇到数字，将数字压到堆栈，遇到运算符，弹出栈顶两个数，进行运算
  3. 结果入栈
  4. 重复上述操作，直到扫描完毕

**中缀表达式**

即为常见的表达式，3+4-5

**后缀表达式（逆波兰表达式）**

- 运算符位于操作数之和
- 如：（3+4）* 5 - 6，对应的表达式 3 4 + 5 * 6 -
- **求值流程**
  1. 从左至右扫描
  2. 遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个元素进行计算
  3. 结果入栈
  4. 重复上述过程，直至表达式结束

**中缀表达式转后缀表达式**

- 初始化两个栈：运算符栈s1和存储中间结果的栈s2
- 从左至右扫描中缀表达式
- 遇到操作时时，压入s2
- 遇到运算符时，比较与s1栈顶运算符的优先级
  1. 若s1为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈
  2. 若优先级比栈顶运算符高，也将其压入s1
  3. 否则s1栈顶运算符出栈，并压入s2中，再次与新的栈顶运算符做比较

## 七、递归（Recursion）回溯算法

- **概念：**方法自己调用自己
- 有助于编程者解决复杂问题

**递归调用机制**

- Java有三个分区，栈，堆，方法区
- 当程序执行到一个方法是开辟一个独立空间，在栈之中
- 每隔空间的数据（局部变量）是独立的

**打印问题**

```Java
public static void test(int n){
    if (n>0){
        test(n-1);
    }
    System.out.println("n = "+n);
}
```

**阶乘问题**

```Java
public static int factorial(int n){
    if (n==1){
       return 1;
    }else {
        return factorial(n-1)*n;
    }
}
```

### 7.1 递归解决的问题

- 各种数学问题：8皇后，汉诺塔，阶乘，迷宫，球和篮子的问题
- 快速排序，归并排序，二分查找，分治算法
- 将用栈解决的问题

**使用递归须遵循的规则**

- 执行一个方法时，就创建一个新的受保护的独立空间
- 方法的局部变量是独立的，不会相互影响
- 递归必须向退出递归的条件逼近，否则就会无限递归
- 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

### 7.2 迷宫回溯问题

**需求**

- 小球从某一点开始移动，移动到规定的某一点，求最短路径

**代码实现及分析**

```Java
package com.why.recursion;

/**
 * @Description TODO 迷宫回溯问题
 * @Author why
 * @Date 2020/10/25 10:39
 * Version 1.0
 **/
public class LabyrinthBacktrack {
    public static void main(String[] args) {
        //创建二维数组模拟迷宫
        //地图
        int[][] map = new int[8][7];
        //使用1表示墙
        //上下全部置为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //左右全部置为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //设置挡板
        map[3][1] = 1;
        map[3][2] = 1;
        map[2][2] = 1;
        //输出地图
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j]+"   ");
            }
            System.out.println();
        }

//使用递归回溯给小球找路
        boolean b = setWay(map, 1, 1);
        System.out.println("新的地图");
        //输出小球探测并表示的地图
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j]+"   ");
            }
            System.out.println();
        }
    }

/**
     * 使用递归给小球找路
     * 小球能到 map[6][5]，通路找到
     *
     * 约定 map[i][j] = 0 时该点没有走过，
     * 为 1 时表示墙，
     * 为 2 表示通路可以走，
     * 为 3 表示该点已走过，但是走不通
     *
     * 在走迷宫时需要确定一个行走策略：
     * 下 --> 右 --> 上 --> 左
     * 如果该点走不通再回溯
     *
     * @param map 地图
     * @param i 从那个位置开始找，行
     * @param j 从那个位置开始找，列
     * @return 找到路返回true，否则返回false
     */
    public static boolean setWay(int[][] map,int i,int j){
        if (map[6][5] == 2){//通路已找到
            return true;
        }else {
            if (map[i][j] == 0){//当前未走过
                //按照策略走
                map[i][j] = 2;//假定该点可以走通
                if (setWay(map,i+1,j)){//向下走
                    return true;
                }else if (setWay(map,i,j+1)){//向右走
                    return true;
                }else if (setWay(map,i-1,j)){//向上走
                    return true;
                } else if (setWay(map,i,j-1)){//向左走
                    return true;
                }else {//该点走不通
                    map[i][j] = 3;
                    return false;
                }
            }else {//map[i][j]不等于0，可能是1，2，3
                return false;
            }
        }
    }
}
```

### 7.3 八皇后问题

**需求**

- 8 x 8的表格，摆放8个皇后
- 要求横竖及斜线上只有一个皇后
- 寻求摆法种树

**分析**

- 第一个皇后放在第一行第一列
- 第二个皇后依次放在第二行的每一列，去尝试是否与第一行皇后冲突
- 继续第三行皇后，依次尝试每一列，看是否与前两行皇后冲突
- 重复上述步骤，直至第八行得到一个正确解
- 得到正确解时，在栈回退到上个栈时就开始回溯，即将第一个皇后，放到第一列的所有正确解全部得到
- 然后回它继续第一个皇后放第二列，继续 重复上述步骤

按理来说需要二维数组来完成，但是可以通过算法用一维数组实现

用一维数组下标表示行数和第几个皇后，数据表示列数

**代码实现**

```Java
package com.why.recursion;

/**
 * @Description TODO
 * @Author why
 * @Date 2020/10/27 10:48
 * Version 1.0
 **/
public class EightQueen {

//定义数组，表示皇后及其位置
    int max = 8;
    int[] arr = new int[max];
    static int count = 0;
    public static void main(String[] args) {
        EightQueen eightQueen = new EightQueen();
        eightQueen.check(0);
        System.out.printf("一共有%d种解法",count);
    }

/**
     * 打印皇后数组
     */
    private void print(){
        count++;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"   ");
        }
        System.out.println();
        System.out.println();
    }

/**
     * 查看放置的第n个皇后，检测是否和前面的皇后冲突
     */
    private boolean judge(int n){
        for (int i = 0; i < n; i++) {
            //arr[i] = arr[n]是否在同一列
            //Math.abs(n-i) == Math.abs(arr[n] - arr[i])是否和第i个皇后在同一斜线
            // 行减行是否等于列减列，等腰三角形在同一斜线
            //Math.abs(n-i)求绝对值
            //n每次都在递增，不需要判断在同一行
            if (arr[i] == arr[n] || Math.abs(n-i) == Math.abs(arr[n] - arr[i])){
                return false;
            }
        }
        return true;
    }

/**
     * 放置第n个皇后
     * 特别注意，check每一次递归时进入daocheck方法都有一套for循环
     */
    private void check(int n){
        if (n == max){
            print();
            return;
        }
        //依次放置，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前皇后n，放到该行的第一列
            arr[n] = i;
            //判断当放置第n个皇后到i列时是否冲突
            if (judge(n)){//不冲突,接着放，即开始递归
                check(n+1);
            }
            //如果冲突继续执行arr[n] = i，即将arr[n]第n个皇后放置在本行的下一列位置
        }
    }
}
```

##  八、算法复杂度

### 8.1 算法时间复杂度

**度量一个程序执行时间的两种方法**

1. **事后统计的方法**

两个问题：

1. 相对设计的算法的运行行能进行评测，需要实际运行程序
   2. 所得时间的通缉令依赖于计算机的硬件、软件等环境因素

2. **事前估计法**

通过分析某个算法的时间复杂度来判断那个算法更优

**时间频度**

一个算法花费的时间与算法中语句的执行此时成正比，语句执行次数叫时间频度（语句频度），记为T(n)

**对于时间频度，可以忽略常数项，低次项和系数**

**时间复杂度**

算法中的基本操作语句的重复执行次数时问题规模n的某个函数用T(n)表示，若某个辅助函数，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常熟，则称f(n)是T(n)同数量级函数，记作T(n) = O(f(n))，称O(f(n))为算法的渐近时间复杂度，简称时间复杂度

T(n)不同，但时间复杂度可能相同

**计算时间复杂度的方法**

- 常数1代替运行时间中的所有加法常数
- 修改后的运行次数函数中，只保留最高阶项
- 取出最高阶项的系数

![image-20201027131249222](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126171016441-1166317565.png)

![image-20201027131433959](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126171023780-542105653.png)

**平均时间复杂度和最坏时间复杂度**

1. 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间
2. 最坏情况下的时间复杂度称为最坏时间复杂度，一般讨论时间复杂度军事最坏情况下的时间复杂度

![image-20201027131808028](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126171028765-1310859880.png)

### 8.2 算法的空间复杂度

![image-20201027131934392](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126171032954-950790507.png)

## 九、排序算法（Sort Algorithm）

### 9.1 排序算法介绍和分类

将一组数据，依指定顺序进行排列

**排序的分类**

1. **内部排序**

指将需要处理的所有数据都加载到内部存储器中进行排序

2. **外部排序**

数据量过大，无法全部加载到内存中，需借助外部存储进行排序

**常见的排序算法**

![image-20201027123631072](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126171500172-1743457841.png)

### 9.2 冒泡排序（Bubble Sort）

**基本思想**

通过对待排序序列从前向后(从下表较小的元素 开始)，依次比较相邻元素的值，若发现逆序，交换相邻元素的值

**基本代码**

```Java
public static void bubbleSorting(int[] arr){
    for (int i = 0; i < arr.length-1; i++) {
        for (int j = 0; j < arr.length-i-1; j++) {
            if (arr[j]>arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
}
```

**优化**

因为排序过程 中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，，因此要在排序过程中设置一个标志flag判断元素是否交换，从而减少不必要的比较

**优化后代码**

```Java
public static void bubbleSorting(int[] arr){
        int temp = 0;
        //标志变量，表示是否进行过交换
        boolean flag = false;
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-i-1; j++) {
                if (arr[j]>arr[j+1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if (flag = false){//在一趟排序中一次都没有交换
                break;
            }else {
                flag = false;//重置flag进行下次判断
            }
        }
//        for (int i = 0; i < arr.length; i++) {
//            System.out.print(arr[i]);
//        }
//        System.out.println();
    }
```

### 9.3 选择排序（Select Sort）

**基本思想**

第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，然后一次从后面的数据选取最小值，与数组前的值交换

```Java
public static void selectSorting(int[] arr){
    for (int i = 0; i < arr.length-1; i++) {
        int temp = arr[i];
        for (int j = i; j < arr.length; j++) {
            if (arr[i]>arr[j]){//从小到大排序
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i]);
    }
    System.out.println();
}
```

### 9.4 插入排序（Insert Sort）

**基本思想**

插入排序属于内部排序，是对于排序的元素以插入的方式 找寻该元素的适当位置，以达到排序的目的

把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序吗一次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，是指成为新的有序表。

**代码实现**

```Java 
public static void insertionSorting(int[] arr){
    int insert = arr[0];//第一个插入的数，直接插入
    int insertIndex = 0;//arr[1]起那面这个数的下标
    arr[insertIndex] = insert;
    for (int i = 1; i < arr.length-1; i++) {
        //insertIndex >= 0，保证给insert找插入位置时不越界
        //insert < arr[insertIndex,待插入的数即arr[insertIndex]后移
        insert = arr[i];
        insertIndex = i - 1;
        while (insertIndex >= 0 && insert < arr[insertIndex]){
            arr[insertIndex+1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex+1] = insert;
    }
    System.out.println(Arrays.toString(arr));
}
```

**问题**

- 若数据过于小，后移的次数较多影响效率

### 9.5 希尔排序（Shell  Sort)

- 希尔排序是简单排序改进后更高效的排序
- 也称缩小增量排序

**基本思想**

- 把记录按下标的一定增量分组
- 对每组使用直接插入排序算法
- 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法终止

#### 9.5.1 交换式算法实现

```Java
/**
 * 交换法，实现希尔排序，效率低
 * @param arr
 */
public static void shellSortExchange(int[] arr){

//将数据根据数组长度进行分组
    int len = (int) Math.floor(arr.length/2);
    int temp = 0;
    while (len>=1){
        for (int i = len; i < arr.length; i++) {
            //遍历各组所有的元素,(共有len组，每组2个元素），步长len
            for (int j = i-len; j >= 0; j -= len) {
                //从小到大排序
                //如果当前元素大于加上步长的元素，需要交换
                if (arr[j] >  arr[j+len]){
                    temp = arr[j];
                    arr[j] = arr[j+len];
                    arr[j+len] = temp;
                }
            }
        }
        len = (int) Math.floor(len/2);
    }
    System.out.println(Arrays.toString(arr));
}
```

#### 9.5.2 移位式算法实现

```Java
/**
 * 移位式，效率高
 * @param arr
 */
public static void shellSortShift(int[] arr){
    int len = (int) Math.floor(arr.length/2);
    int temp = 0;
    //增量len，并逐步缩小增量
    while (len >= 1){
        //从第len个元素，诸葛对其所在的组进行直接插入排序
        for (int i = len; i < arr.length; i++) {
            int j = i;
            temp = arr[j];
            if (arr[j]<arr[j-len]){
                while (j-len >= 0 && temp < arr[j-len]){
                    //移动
                    arr[j] = arr[j-len];
                    j -= len;
                }
                //退出循环后找到了插入的位置
                arr[j] = temp;
            }
        }
        len = (int) Math.floor(len/2);
    }
    System.out.println(Arrays.toString(arr));
}
```

### 9.6 快速排序（Quick Sort）

快速排序是对冒泡排序的一种改进

**基本思想**

- 通过一趟排序将要排序的数据分割为独立的两部分
- 一部分所有的数据都比另一部分所有的数据小
- 按上述方法对两部分数据进行快速排序
- 整个排序过程可以递归进行，达到整个数据编程有序序列

**找一个基准，将数据序列分成两部分**

**代码实现**

```Java
/**
 * 快速排序
 * @param arr
 * @param left
 * @param right
 */
public static void quickSort(int[] arr,int left,int right){
    int l = left;//左下标
    int r = right;//右下标
    int pivot = arr[(left+right)/2];//基准数
    int temp = 0;//临时变量

//左边索引大于等于右边索引时结束循环
    //将比pivot小的数据放到左边，大的放到右边
    while (l < r){
        //在pivot左边找到大于或等于pivot的值，才退出
        while (arr[l] < pivot){
            l += 1;
        }
        //在pivot右边找到小于或等于pivot的值，才退出
        while (arr[r] > pivot){
            r -= 1;
        }
        //l >= r,pivot左右两边的值，已按照左边全部是小于等于pivot的值
        //右边大于等于pivot的值
        if (l >= r){
            break;
        }
        //交换
        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
        //如果交换完后发现arr[l] == pivot,则r--,前移一步
        if (arr[l] == pivot){
            r -= 1;
        }
        //如果交换完后发现arr[r] == pivot,则l++,后移一步
        if (arr[r] == pivot){
            l += 1;
        }
    }
    //如果l == r，必须l++，r--，否则会出现栈溢出
    if (l == r){
        l++;
        r--;
    }
    //向左递归
    if (left < r){
        quickSort(arr,left,r);
    }
    //向右递归
    if(right > l){
        quickSort(arr,l,right);
    }
}
```

### 9.7 归并排序（Merge Sort）

归并排序是利用归并的思想实现的排序方法，采用分治的策略。

**基本思想**

最后一次合并

**代码实现**

```Java
/**
 * 归并排序
 * @param arr
 * @param left
 * @param right
 * @param temp
 */
public static void mergeSort(int[] arr,int left,int right,int[] temp){
    if (left < right){
        int mid = (left + right) / 2;
        //向左递归进行分解
        mergeSort(arr,left,mid,temp);
        //向右递归进行分解
        mergeSort(arr,mid+1,right,temp);

//到合并
        merge(arr,left,mid,right,temp);
    }
}
/**
 * 归并排序合并的方法
 * @param arr   待排序的数组
 * @param left  左边有序序列的初始索引
 * @param mid   中间索引
 * @param right 右边索引
 * @param temp  中转临时数组
 */
public static void merge(int[] arr,int left,int mid,int right,int[] temp){
    //初始化i，j
    int i = left; //左边序列的初始索引
    int j = mid + 1; //右边有序序列的初始索引
    int t = 0; //temp的索引

//（一）
    //先把左右两边（有序）的数据按规则填充到temp数组
    //直到左右两边有一边的有序序列处理完毕
    while (i <= mid && j <= right){
        //左边有序序列的当前元素小于或等于右边有序序列的当前元素
        if (arr[i] <= arr[j]){
            //将左边当前数据加入到temp中
            // 并且将temp索引t和右边索引i，分别+=1
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }else {//左边有序序列的当前元素大于右边有序序列的当前元素
            //将右边当前数据加入到temp中
            // 并且将temp索引t和右边索引j，分别+=1
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
    }

//（二）
    //把有剩余的一边的数据一次全部填充到temp
    while (i <= mid){//左边还有剩余元素，全部填充到temp
        temp[t] = arr[i];
        t +=  1;
        i += 1;
    }
    while (j <= right){//右边还有剩余元素，全部填充到temp
        temp[t] = arr[j];
        t +=  1;
        j += 1;
    }

//（三）
    //将temp数组的元素拷贝到arr
    //注意并不是每次都拷贝所有数据
    t = 0;
    int tempLeft = left;
    System.out.println("tempLeft = "+tempLeft+" , "+right);
    while (tempLeft <= right){
        arr[tempLeft] = temp[t];
        t += 1;
        tempLeft += 1;
    }
}
```

### 9.8 基数排序（Radix Sort）【桶排序】

**基本介绍**

- 基数排序属于分配式排序，通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
- 基数排序法是属于稳定性的排序，基数排序法是效率高的稳定性排序法
- 基数排序是桶排序的扩展
- 是1887年赫尔曼·何乐礼发明的，实现方法：将整数按位数切割成不同的数字，然后按每个位数分别比较

**基本思想**

- 将所有待比较的数值统一为同样的位数长度，数位较短的数前面补0
- 然后从最低位开始，依次进行一次排序。
- 这样从最低位排序一直到最高位排序完成后，数列就变成一个有序序列

**第一轮示意图**

按个位

![image-20201031154755329](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126171521004-1209672278.png)

后面按照十位，百位......依次排序

**代码实现**

```Java
/**
 * 基数排序
 * @param arr
 */
public static void radixSort(int[] arr){
    //定义一个二维数组表示10个桶
    //二维数组包含10个一维数组
    //为防止溢出，每隔一维数组大小只能定为arr.length
    //空间换时间
    int[][] bucket = new int[10][arr.length];

//为记录每个桶中实际存放了多少个数据
    // 定义一个一维数组记录各桶每次放入的数据个数
    int[] bucketElementCount = new int[10];

//得到数组中最大数
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max){
            max = arr[i];
        }
    }
    //得到最大数的位数
    int maxLength = (max + "").length();

for (int i = 0,n = 1; i < maxLength; i++,n *= 10) {
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的位，第一次是个位，第二次是是十位...
            int digitOfElement = arr[j] / n % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j];
            bucketElementCount[digitOfElement]++;
        }

//依照桶中的顺序放入原数组
        int index = 0;
        for (int j = 0; j < bucketElementCount.length; j++) {
            //如果桶中有数据，才放入到原数组
            if (bucketElementCount[j] != 0){//对应的桶中有数据
                //循环第i个桶，即dii个一维数组
                for (int k = 0; k < bucketElementCount[j]; k++) {
                    //取出元素放入到arr中
                    arr[index] = bucket[j][k];
                    index++;
                }
            }
            //每一轮处理后需要将bucketElementCount[i]置零（各桶中数据个数）
            bucketElementCount[j] = 0;
        }
    }
    System.out.println(Arrays.toString(arr));
}
```

**基数排序说明**

1. 基数排序是对传统桶排序的扩展，速度很快
2. 基数排序是经典的空间换时间的方式，占用内存很大，容易造成OutOfMemoryError
3. 基数排序是稳定的
4. **稳定：**若序列中存在多个相同的数据，排序后这些数据的前后顺序不变，则排序算法稳定

**内排序和外排序**

- 内排序：所有排序在内存中完成
- 外排序：由于数据量较大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行

**稳定：**排序后相等的元素前后位置不变

**在位：**排序时不借助外部空间

## 十、查找算法

**常用的查找算法：**

- 顺序（线性）查找
- 二分查找/折半查找
- 插值查找
- 斐波那契查找

### 10.1 线性查找

- 一个数列可有序，可无序

**代码实现**

```Java
/**
 * 线性查找
 * 这里是找到一个即返回
 * @param arr 查找的数据数列
 * @param val 需要查找的值
 * @return
 */
public static int seqSearch(int[] arr,int val){
    //线性查找是逐一比对，发现相同值，返回下标
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == val){
            return i;
        }
    }
    return -1;
}
```

### 10.2 二分查找(Binary Search)

- **有序数列才可使用二分查找**

**思路分析**

1. 首先确定该数组的中间下标mid = （left  + right）/ 2
2. 然后让需要查找的数findVal和arr【mid】比较
   - findVal > arr[mid]，向右查询
   - findVal < arr[mid]，向右查询
   - findVal == arr[mid]，找到，返回
3. 结束递归的条件
   - 找到就结束
   - 递归完整个数组，未找到，结束递归，left > right

**基本写法**

```Java
public static int binarySearch(int[] arr,int left,int right,int findVal){
    if (left > right){
        return -1;
    }
    //确定中间数组的下标
    int mid = (left + right)/2;
    int midVal = arr[mid];

//与中间数组比较
    if (findVal > midVal){//向右查找
        return binarySearch(arr,mid+1,right,findVal);
    }else if (findVal < midVal){
        return binarySearch(arr,left,mid-1,findVal);
    }else {
        return mid;
    }
}
```

**新需求**

当一个数组中有多个相同的数值是 ，将所有数值都查到

**代码实现**

```Java
package com.why.search;

import com.sun.jdi.PathSearchingVirtualMachine;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.ListIterator;
import java.util.logging.Level;

/**
 * @Description TODO 当一个数组中有多个相同的数值是 ，将所有数值都查到,使用二分查找
 * @Author why
 * @Date 2020/11/1 16:35
 * Version 1.0
 **/
public class NewBinarySearch {
    public static void main(String[] args) {
        int[] arr = {1,8,8,10,10,10,10,11};
        List res = newBinarySearch(arr, 0, arr.length - 1, 8);
        if (!res.isEmpty()){
            System.out.println(res);
        }else {
            System.out.println("未找到");
        }
    }

/**
     * 二分查找查找多条数据
     *
     * 思路：
     * 找到mid值时，不要马上返回
     * 向mid 索引值的左边扫描将所有满足查找值的元素下标加入到集合
     * 向右扫描将所有满足查找值的元素下标加入到集合
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @return
     */
    public static List<Integer> newBinarySearch(int[] arr, int left, int right, int findVal){

if (left > right){
            return new ArrayList<Integer>();
        }
        int  mid = (left + right) / 2;
        int midVal = arr[mid];

if (findVal > midVal){
            return newBinarySearch(arr,mid + 1,right,findVal);
        }else if (findVal < midVal){
            return newBinarySearch(arr,left,mid - 1,findVal);
        }else {
            List<Integer> resIndexList = new ArrayList<>();
            //向左边扫描
            int temp = mid - 1;
            while (true){
                if (temp < 0 || arr[temp] != findVal){
                    break;
                }
                resIndexList.add(temp);
                temp -= 1;
            }
            //中间值
            resIndexList.add(mid);
            //向右扫描
            temp = mid + 1;
            while (true){
                if (temp > arr.length || arr[temp] != findVal){
                    break;
                }
                resIndexList.add(temp);
                temp += 1;
            }
            return resIndexList;
        }
    }
}
```

### 10.3 插值查找

**基本原理**

1. 插值查找算法类似于二分查找算法，不同的是插值查找每次从自适应mid处开始查找

2. mid索引的公式，low表示左边索引，high表示右边索引,key表示查找的值
   $$
   mid = low + (key - a[low]) / (a[high] - a[low]) * (high - low)
   $$
   
3. 插值索引，对应代码：

```java 
   int mid = left + (right + left)*(findVal - arr[left]) / (arr[right] - arr[left]);
   ```

**解决的问题**

用于查找类似于[1,2,3,4,...,n]的数据序列中的值

**代码实现**

```Java
/**
 * 插值查找算法
 * @param arr
 * @param left
 * @param right
 * @param findVal
 * @return
 */
public static int insertSearch(int[] arr,int left,int right,int findVal){
    if (left >right || findVal <arr[0] ||findVal > arr[arr.length - 1]){
        return -1;
    }

int mid = left + (right + left)*(findVal - arr[left]) / (arr[right] - arr[left]);
    if (findVal < arr[mid]){
        return insertSearch(arr,left,mid - 1,findVal);
    }else if (findVal > arr[mid]){
        return insertSearch(arr,mid + 1,right,findVal);
    }else {
        return mid;
    }
}
```

### 10.4 斐波那契（黄金分割法）查找算法（Fibonacci Search）

**黄金分割点**

指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值0.618，此比例称为黄金分割，也称中外比

**斐波那契数列**

斐波那契数列{1，1，2，3，5，8，13，21，34，55}，发现相邻两数的比例无限接近黄金分隔值0.618

**基本原理**

改变中间节点mid的位置，mid不再是中间节点，二十位于黄金分割点附近，即
$$
mid = low + F[k - 1] - 1
$$
F代表斐波那契数列，如图所示

![image-20201102163840552](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126171955233-827966210.png)

**对F(k - 1) - 1的理解**

1. 由斐波那契数列F[k] = F[k-1] + F[k-2]的性质可得，
   $$
   F[k] - 1 = (F[k-1] - 1) + (F[k-2] - 1) + 1
   $$
   该式说明，只要顺序表的长度为F(k) - 1，则可将该表分为长度为F(k-1) - 1和F(k-2) - 1的两段，即如上图所示
   $$
   mid = low +F[k-1] - 1
   $$

2. 类似的，每一子段也可分割

3. 顺序表长度不一定刚好等于F[k] - 1，故需将原来长度n增加至F[k] - 1，k使F[k] - 1刚好大于或等于n即可，新增的位置，都赋为n位置的值即可

**有序数组才可使用此查找算法**

**代码实现**

```Java
package com.why.search;

import com.sun.source.tree.IfTree;

import java.security.Key;
import java.util.Arrays;

/**
 * @Description TODO 斐波那契查找算法
 * @Author why
 * @Date 2020/11/2 16:53
 * Version 1.0
 **/
public class FibonacciSearch {
    public static int maxSize = 20;
    public static void main(String[] args) {
        int[] arr = {1,8,10,89,1000,1234};
        int i = fibSearch(arr, 1000);
        if (i == -1){
            System.out.println("未找到");
        }else {
            System.out.println("下标是："+i);
        }
    }

/**
     * 需要使用斐波那契数列，首先获取到斐波那契数列
     * 非递归方式
     * @return
     */
    public static int[] fib(){
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < f.length; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

/**
     * 斐波那契查找算法
     * 非递归
     * @param a
     * @param findVal
     * @return
     */
    public static int fibSearch(int[] a,int findVal){
        int low = 0;
        int high = a.length - 1;
        int k = 0;//表示斐波那契分割数值的下标
        int mid = 0;//存放mid值

//获取斐波那契数列
        int[] f = fib();
        //获取斐波那契分割数值的下标
        while (high > f[k] - 1){
            k++;
        }
        //因为f[k]值可能大于数组长度，
        // 因此需要使用Arrays类，构造新的数组，并指向temp[]
        //不足的部分使用0填充
        int[] temp = Arrays.copyOf(a,f[k]);
        //实际上需使用a数组最后 的数填充temp
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = a[high];
        }

//循环处理查找数
        while (low <= high){
            mid = low +f[k-1] -1;
            if (findVal < temp[mid]){//继续向数组左半部分查找
                high = mid - 1;
                //说明：
                //1.全部元素 =  前面元素 + 后面元素
                //2.F[k] = F[k-1] + f[k-2]
                //因为前面有F[k-1]个元素，所以可以继续拆分
                //F[k-1] = F[k-2] + F[k-3]
                //即在F[k-1]前面继续查找，k--
                k--;
            }else if (findVal > temp[mid]){//向右查找
                low = mid + 1;
                k -= 2;
            }else {//找到
                //需要确定返回那个下标
                if (mid <= high){
                    return mid;
                }else {
                    return high;
                }
            }
        }
        return -1;//未找到
    }
}
```

## 十一、哈希表（散列）

**应用场景**

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

要求：不适用数据库，尽量节省内存，速度越快越好

**基本介绍**

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

![image-20201102173455937](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126172213330-870163857.png)

**实现缓存层**

![image-20201103170713180](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126172217239-936157055.png)

定义哈希表可以自己实现缓存层：

- 数组+链表
- 数组+二叉树

### 11.1 使用哈希表管理雇员信息

**需求**

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

要求：不适用数据库，尽量节省内存，速度越快越好

**思路分析**

![image-20201103171541293](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201126172222092-1251436795.png)

1. 创建员工类，实现存储员工信息
2. 创建链表头指针指向第一个员工
3. 创建哈希表，建立数组属性，存储这些链表；创建散列函数，决定id对应的链表（数组的元素）
4. 通过哈希表实现增删改查

**代码实现**

```Java
package com.why.a;

/**
 * @Description TODO 哈希表
 * @Author why
 * @Date 2020/11/3 18:00
 * Version 1.0
 **/
public class HashTable {
    public static void main(String[] args) {
        hashTable hashTable = new hashTable(3);
        Employee e1 = new Employee(1,"why","男",14,"兰州");
        Employee e2 = new Employee(2,"why","男",14,"兰州");
        hashTable.add(e1);
        hashTable.add(e2);
        hashTable.list();
    }
}

/**
 * 管理多条链表
 */
class hashTable{
    int size;
    private HashLinkedList[] hashLinkedListsArr;

public hashTable(int size) {
        this.size = size;
        hashLinkedListsArr = new HashLinkedList[size];
        //不要忘记分别初始化每一条链表
        for (int i = 0; i < size; i++) {
            hashLinkedListsArr[i] = new HashLinkedList();
        }
    }

/**
     * 添加雇员
     * @param node
     */
    public void add(Employee node){
        //根据员工id，得到该员工应该添加到哪条链表
        int empLinkedListNo = hasFun(node.getId());
        //将employee添加到对应的链表中
        hashLinkedListsArr[empLinkedListNo].insert(node);
    }

/**
     * 遍历hash表
     */
    public void list(){
        for (int i = 0; i < hashLinkedListsArr.length; i++) {
            hashLinkedListsArr[i].show();
        }
    }
    /**
     * 编写散列函数，使用简单的取模法
     * @param id
     * @return
     */
    public int hasFun(int id){
        return id % size;
    }
}

class HashLinkedList {
    //头指针
    private Employee head = new Employee();

/**
     * 添加功能
     */
    public void insert(Employee employee){
        Employee temp = head;
        while (true){
            if (temp == null){
                break;
            }
            temp = temp.getNext();
        }
        temp.setNext(employee);
    }
    /**
     * 删除
     * @param id
     */
    public void delete(int id){
        if (head == null){
            System.out.println("空");
        }
        Employee temp = head;
        while (true){
            if (temp.getId() == id){
                temp.setNext(temp.getNext());
                break;
            }
            temp = temp.getNext();
        }
    }
    /**
     * 更新
     * @param employee
     */
    public void update(Employee employee){
        if (head == null){
            System.out.println("空");
        }
        Employee temp = head;
        while (true){
            if (temp.getId() == employee.getId()){
                temp.setId(employee.getId());
                temp.setName(employee.getName());
                temp.setAddress(employee.getAddress());
                temp.setAge(employee.getAge());
                temp.setGender(employee.getGender());
                break;
            }
            temp = temp.getNext();
        }
    }

/**
     * 根据id查询一条记录
     * @param id
     * @return
     */
    public Employee findById(int id){
        if (head.getNext() == null){
            System.out.println("空");
        }
        Employee temp = head;
        while (true){
            if (temp.getId() == id){
                Employee employee = temp;
                return employee;
            }
            temp = temp.getNext();
        }
    }
    /**
     * 遍历显示
     */
    public void show(){
        //判空
        if (head == null){
            System.out.println("空");
        }
        Employee temp = head;
        while (true){
            if (temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            temp = temp.getNext();
        }
    }
}

class Employee {
    private int id;
    private String name;
    private String gender;
    private int age;
    private String address;
    private Employee next;

public Employee() {
    }

public Employee(int id, String name, String gender, int age, String address) {
        this.id = id;
        this.name = name;
        this.gender = gender;
        this.age = age;
        this.address = address;
    }

public Employee getNext() {
        return next;
    }

public void setNext(Employee next) {
        this.next = next;
    }

public int getId() {
        return id;
    }

public void setId(int id) {
        this.id = id;
    }

public String getName() {
        return name;
    }

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

public String getGender() {
        return gender;
    }

public void setGender(String gender) {
        this.gender = gender;
    }

public int getAge() {
        return age;
    }

public void setAge(int age) {
        this.age = age;
    }

public String getAddress() {
        return address;
    }

public void setAddress(String address) {
        this.address = address;
    }

@Override
    public String toString() {
        return "Employee{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", gender='" + gender + '\'' +
                ", age=" + age +
                ", address='" + address + '\'' +
                '}';
    }
}
```

## 十二、数组、链表和树存储方式分析

### 12.1 数组

**优点**

- 通过下标方式访问元素，速度快
- 对于有序数组，可以使用二分查找提高检索效率

**缺点**

- 要检索或插入某个具体值，数组会整体移动，效率低

### 12.2 链表

**优点**

- 在一定程度上，是对数组的优化

**缺点**

- 进行检索时，效率较低

### 12.3 树结构

- 能提高数据存储，读取速率
- 利用二叉排序树，即可保证数据的检索速度，同时可保证数据的插入、删除和修改的速度

## 十三、树

### 13.1 树的概念和常用术语

**常用术语**

- 节点
- 根节点
- 父节点
- 子节点
- 叶子节点：没有子节点的节点
- 节点的权：节点的值
- 路径：节点A到节点B的路径
- 层
- 子树
- 树的高度：最大层数
- 森林：多颗子树构成森林

**二叉树概念**

- 每个节点最多只有两个子节点的树，叫二叉树
- 若该二叉树是**满二叉树**，节点数是2^n - 1，n为层数
- **完全二叉树**：每一层节点都是连续的，即有子节点的父节点都有两个子节点

### 13.2 建立二叉树

**思路分析**

- 建立节点类
- 包含信息，左孩子指针，右孩子指针

### 13.3 二叉树的前中后序遍历算法

#### 13.3.1 前序遍历

**前序遍历**

- 先输出父节点，再遍历左子树和右子树
- 中，左，右

**思路分析**

1. 先输出当前节点，初始是root节点
2. 如果左子节点不为空，则递归继续前序遍历
3. 如果右子节点不为空，则递归继续前序遍历

#### 13.3.2 中序遍历

**中序遍历**

- 先遍历左子树，在输出父节点，再遍历右子树
- 左，中，右

**思路分析**

1. 如果左子节点不为空，则递归继续中序遍历
2. 输出当前节点
3. 如果右子节点不为空，则递归继续中序遍历

#### 13.3.3 后序遍历

**后序遍历**

- 先遍历左子树，再遍历右子树，最后输出父节点
- 左，右，中

**思路分析**

1. 如果左子节点不为空，则递归继续中序遍历
2. 如果右子节点不为空，则递归继续中序遍历
3. 输出当前节点

#### 13.3.4 代码实现

```Java
package com.why.tree;

import java.sql.SQLOutput;

/**
 * @Description TODO 前中后序遍历
 * @Author why
 * @Date 2020/11/4 16:49
 * Version 1.0
 **/
public class BinaryTreeDemo {
    public static void main(String[] args) {
        //创建二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建需要的节点
        BNode root = new BNode(1,"why");
        BNode node1 = new BNode(1,"cjl");
        BNode node2 = new BNode(1,"wl");
        BNode node3 = new BNode(1,"lrx");

//手动创建二叉树，后边以递归方式建立二叉树
        root.setLeftChild(node1);
        root.setRightChild(node2);
        node2.setRightChild(node3);

//设置根节点
        binaryTree.setRoot(root);
        System.out.println("前序遍历：");
        binaryTree.preOrder();
        System.out.println();
        System.out.println("中序遍历：");
        binaryTree.midOrder();
        System.out.println();
        System.out.println("后序遍历：");
        binaryTree.postOrder();
    }
}

/**
 * 定义二叉树
 */
class BinaryTree{
    private BNode root;

public BNode getRoot() {
        return root;
    }

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

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

/**
     * 中序遍历
     */
    public void midOrder(){
        if (this.root != null){
            this.root.midOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }

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

/**
 * 创建节点类
 */
class BNode{
    private int id;
    private String name;
    private BNode leftChild;//左孩子节点
    private BNode rightChild;//右孩子节点

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

public int getId() {
        return id;
    }

public void setId(int id) {
        this.id = id;
    }

public String getName() {
        return name;
    }

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

public BNode getLeftChild() {
        return leftChild;
    }

public void setLeftChild(BNode leftChild) {
        this.leftChild = leftChild;
    }

public BNode getRightChild() {
        return rightChild;
    }

public void setRightChild(BNode rightChild) {
        this.rightChild = rightChild;
    }

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

/**
     * 前序遍历
     */
    public void preOrder(){
        //先输出当前(父节点）节点
        System.out.println(this);
        //递归左子树
        if (this.leftChild != null){
            this.leftChild.preOrder();
        }
        //递归右子树
        if (this.rightChild != null){
            this.rightChild.preOrder();
        }
    }

/**
     * 中序遍历
     */
    public void midOrder(){
        //先中序遍历左子树
        if (this.leftChild != null){
            this.leftChild.midOrder();
        }
        //输出当前节点
        System.out.println(this);
        //中序遍历右子树
        if (this.rightChild != null){
            this.rightChild.midOrder();
        }
    }

/**
     * 后序遍历
     */
    public void postOrder(){
        //后序遍历左子树
        if (this.leftChild != null){
            this.leftChild.preOrder();
        }
        //后序遍历右子树
        if (this.rightChild != null){
            this.rightChild.postOrder();
        }
        //输出当前节点
        System.out.println(this);
    }
}
```

### 13.4 二叉树的前中后序查找算法

#### 13.4.1 前序查找

**思路分析**

1. 和当前节点比较，若相等返回当前节点
2. 若不相等
   - 左子树不为空，左递归前序查找，找到节点返回
   - 右子树不为空，右递归前序查找，找到节点返回，找不到显示没有搜索结果

**代码实现**

节点类

```Java
/**
 * 前序查找
 * @param no
 * @return
 */
public BNode preSearch(int no){
    if (this.getId() == no){//与当前节点比较，相等返回
        return this;
    }

//遍历左子树查找
    BNode bNode = null;
    if (this.leftChild != null){
        bNode = this.leftChild.preSearch(no);
    }
    if (bNode != null){//左子树找到
        return bNode;
    }

//遍历右子树
    if (this.rightChild != null){
        bNode = this.rightChild.preSearch(no);
    }
    return bNode;
}
```

二叉树类

```Java
/**
 * 前序查找
 * @param no
 */
public void preSearch(int no){
    if (this.root != null){
        BNode bNode = this.root.preSearch(no);
        if (bNode != null){
            System.out.println(bNode);
        }else {
            System.out.println("未找到");
        }
    }else {
        System.out.println("二叉树为空");
    }
}
```

#### 13.4.2 中序查找

**思路分析**

1. 左子树不为空，左递归中序查找，找到节点返回
2. 若未找到
   - 和当前节点比较，若相等返回当前节点
   - 右子树不为空，右递归中序查找，找到节点返回，找不到显示没有搜索结果

**代码实现**

节点类

```Java
/**
 * 中序查找
 * @param no
 * @return
 */
public BNode midSearch(int no){

BNode bNode = null;
    //遍历左子树
    if (this.leftChild != null){
        bNode = this.leftChild.midSearch(no);
    }
    if (bNode != null){
        return bNode;
    }

//与当前节点比较
    if (this.getId() == no){
        return this;
    }

//遍历右子树
    if (this.rightChild != null){
        bNode = this.rightChild.midSearch(no);
    }
    return bNode;
}
```

二叉树类

```Java
/**
 * 中序查找
 * @param no
 */
public void midSearch(int no){
    if (this.root != null){
        BNode bNode = this.root.midSearch(no);
        if (bNode != null){
            System.out.println(bNode);
        }else {
            System.out.println("未找到");
        }
    }else {
        System.out.println("二叉树为空");
    }
}
```

#### 13.4.3 后序查找

**思路分析**

1. 左子树不为空，左递归后序查找，找到节点返回
2. 若未找到
   - 右子树不为空，右递归后序查找，找到节点返回
   - 和当前节点比较，若相等返回当前节点，找不到显示没有搜索结果

**代码实现**

节点类

```Java
/**
 * 后序查找
 * @param no
 * @return
 */
public BNode postSearch(int no){
    BNode bNode = null;
    //遍历左子树
    if (this.leftChild != null){
        bNode = this.leftChild.postSearch(no);
    }
    if (bNode != null){
        return bNode;
    }

//遍历右子树
    if(this.rightChild != null){
        bNode = this.rightChild.postSearch(no);
    }
    if (bNode != null){
        return bNode;
    }

//与当前节点比较
    if (this.getId() == no){
        bNode = this;
    }
    return bNode;
}
```

二叉树类

```Java
/**
 * 后序查找
 * @param no
 */
public void postSearch(int no){
    if (this.root != null){
        BNode bNode = this.root.postSearch(no);
        if (bNode != null){
            System.out.println(bNode);
        }else {
            System.out.println("未找到");
        }
    }else {
        System.out.println("二叉树为空");
    }
}
```

### 13.5 删除二叉树指定的节点

**要求**

- 若删除的是叶子节点，则删除该节点
- 如果删除的节点是非叶子节点，则删除该子树

**思路**

- 因为二叉树是单向的，所以判断 当前节点的子节点是否是待删除的节点
- 不能判断当前节点是不是需要删除的节点
- 如果当前节点的左孩子节点不为空，并且左孩子节点是待删除的节点将this.left置空，返回
- 如果当前节点的左孩子节点不为空，并且左孩子节点是待删除的节点将this.left置空，返回
- 如果上述步骤，没有删除节点，那么就需要向左/右子树递归删除
- 如果只有一个root节点，则等价于将二叉树指控

**代码实现**

BNode.java

```java 
/**
 * 删除指定的节点
 * @param no
 */
public void delete(int no){
    if(this.getLeftChild() != null && this.getLeftChild().getId() == no){
        this.setLeftChild(null);
        return;
    }
    if (this.getRightChild() != null && this.getRightChild().getId() == no){
        this.setRightChild(null);
        return;
    }
    //向左子树递归
    if (this.getRightChild() != null){
        this.getLeftChild().delete(no);
    }
    //向右子树递归
    if (this.getRightChild() != null){
        this.getRightChild().delete(no);
    }
}
```

BinaryTree.java

```java 
/**
 * 根据id删除节点/子树
 * @param no
 */
public void delete(int no){
    if (this.root != null){
        if(this.root.getId() == no){
            this.root = null;
        }else {
            this.root.delete(no);
        }
    }else {
        System.out.println("二叉树为空");
    }
}
```

### 13.6 顺序存储二叉树

**存储结构**

**要求**

1. 上图二叉树的节点，要求以数组的方式来存放[1,2,3,4,5,6,]
2. 但是仍然能够以树的形式来遍历

**顺序存储二叉树的特点**

1. 顺序二叉树通常只考虑完全二叉树
2. 第n个元素的左孩子节点是2*n + 1
3. 第n个元素的右子节点是2*n + 2
4. 第n个元素的父节点为（n-1)/2

**代码实现**

```Java
package com.why.tree;

/**
 * @Description TODO
 * @Author why
 * @Date 2020/11/12 15:14
 * Version 1.0
 **/
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7};
        ArrBinaryTree abt = new ArrBinaryTree(arr);
//        abt.preOrder();
//        abt.midOrder();
        abt.postOrder();
    }
}

class ArrBinaryTree{
    private int[] arr;

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

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

/**
     * 重载方法
     */
    public void preOrder(){
        this.preOrder(0);
    }

/**
     * 中序遍历
     * @param index
     */
    public void midOrder(int index){
        if (arr == null || arr.length == 0){
            System.out.println("数组为空");
        }
        //左递归
        if ((2 * index + 1) < arr.length){
            midOrder(2 * index + 1);
        }
        //输出当前元素
        System.out.println(arr[index]);
        if ((2 * index + 2) < arr.length){
            midOrder(2 * index + 2);
        }
    }

public void midOrder(){
        midOrder(0);
    }

/**
     * 后序遍历
     * @param index
     */
    public void postOrder(int index){
        if (arr == null || arr.length == 0){
            System.out.println("数组为空");
        }
        //左递归
        if ((2 * index + 1) < arr.length){
            postOrder(2 * index + 1);
        }
        //右递归
        if ((2 * index + 2) < arr.length){
            postOrder(2 * index + 2);
        }
        //输出当前元素
        System.out.println(arr[index]);
    }
    public void postOrder(){
        postOrder(0);
    }
}

```

**作用：**堆排序用到二叉树的顺序存储

### 13.7 线索化二叉树

**基本介绍**

1. n个节点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向节点在某种遍历次序下的前驱和后继节点的指针（附加的指针叫线索）
2. 加上了线索的二叉链表叫做线索链表，相应的二叉树称为线索二叉树（threaded BinaryTree）根据线索性质不同，线索二叉树可分为前序线索二叉树，中序线索二叉树，后序线索二叉树三种
3. 一个节点的前一节点是**前驱节点**
4. 一个节点的后一节点是**后继结点**

**说明**

当线索化二叉树后，Node节点的属性left和right，有如下情况：

1. left指向的是左子树，也可能指向前驱节点

2. right指向右子树也可能指向后继结点

**代码实现**

```Java
   package com.why.tree;
   
   import javax.swing.*;
   
   /**
    * @Description TODO
    * @Author why
    * @Date 2020/11/24 15:08
    * Version 1.0
    **/
   public class ThreadBinaryTreeDemo {
       public static void main(String[] args) {
           //测试中序线索二叉树
           int[] arr = {8,3,10,1,14,6};
   
           Node root = new Node(1);
           Node node1 = new Node(3);
           Node node2 = new Node(6);
           Node node3= new Node(8);
           Node node4 = new Node(10);
           Node node5 = new Node(14);
   
   
           //手动创建二叉树
           ThreadBinaryTree tbt = new ThreadBinaryTree(root);
           root.setLeft(node1);
           root.setRight(node2);
           node1.setLeft(node3);
           node1.setRight(node4);
           node2.setLeft(node5);
   
           tbt.midOrder();
   
           tbt.threadedNodes();
           //测试中序线索化是否正确,验证10号节点前驱后继节点是否正确
           System.out.println("前驱："+node4.getLeft());
           System.out.println("后继：" + node4.getRight());
       }
   }
   
   class ThreadBinaryTree{
       //定义根节点
       private Node root = new Node();
       //为实现线索化，创建一个指向当前节点的前驱节点的指针
       //递归进行线索化时，pre保留前一个节点
       private Node pre = null;
   
       public ThreadBinaryTree(Node root) {
           this.root = root;
       }
   
       public Node getRoot() {
           return root;
       }
   
       public void setRoot(Node root) {
           this.root = root;
       }
   
       /**
        * 判空
        * @return
        */
       boolean isEmpty(){
           if (this.root == null){
               return true;
           }
           return false;
       }
       /**
        * 中序线索化
        * @param node
        */
       public void threadedNodes(Node node){
           //如果node == null,不能线索化
           if (node == null){
               return;
           }
           //第一步，线索化左子树
           threadedNodes(node.getLeft());
           //第二步，线索化当前节点
           //2.1.处理当前节点的前驱节点
           if (node.getLeft() == null){
               //当前节点的左指针指向前驱节点
               node.setLeft(pre);
               //修改当前节点的左指针类型
               node.setLeftType(1);
           }
           //2.2.处理当前节点的后继结点,下一次处理，pre指向上一次node
           if (pre != null && pre.getRight() == null){
               //让前驱节点的右指针指向当前节点
               pre.setRight(node);
               //修改前驱节点的右指针类型
               pre.setRightType(1);
           }
           //每处理一个节点后让当前节点是下一个节点的前驱节点
           pre = node;
           //第三步，线索化右子树
           threadedNodes(node.getRight());
       }
       //重载
       public void threadedNodes(){
           threadedNodes(root);
       }
       /**
        * 中序遍历
        */
       public void midOrder(){
           if (this.root != null){
               this.root.midOrder();
           }else {
               System.out.println("二叉树为空");
           }
       }
   }
   //线索化二叉树节点
   class Node{
       private int no;//数值
       private Node left;//左孩子节点 || 前驱节点
       private Node right;//右孩子节点 || 后继结点
       /**
        * 说明：
        * leftType == 0 表示指向左子树
        * leftType == 1 表示指向前驱节点
        */
       private int leftType;
       /**
        * 说明：
        * rightType == 0 表示指向有子树
        * rightType == 1 表示指向后继结点
        */
       private int rightType;
   
       public Node() {
       }
   
       public Node(int no) {
           this.no = no;
       }
   
       public int getNo() {
           return no;
       }
   
       public void setNo(int no) {
           this.no = no;
       }
   
       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 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;
       }
   
       @Override
       public String toString() {
           return "Node{" +
                   "no=" + no +
                   '}';
       }
       public void midOrder(){
           //遍历左子树
           if (this.getLeft() != null){
              this.left.midOrder();
           }
           //输出当前节点
           System.out.println(this);
           //遍历右子树
           if (this.getRight() != null){
               this.right.midOrder();
           }
       }
   }
   ```
   
   **遍历线索化二叉树**
   
   分析：由于线索化后各个节点的指向有变化，因此原来的遍历方式不能够再去使用
   
   各个节点可以使用线性的方式遍历，无需使用递归，提高了遍历效率，遍历次序应和线索化方式相同
   
   代码实现：
   
   ```Java
   /**
    * 中序遍历线索化二叉树
    */
   public void midOrder(){
      Node node = root;
      while (node != null){
          //存储当前便利的节，从root开始
          //循环找到leftType == 1的节点
          while (node.getLeftType() == 0){
              node = node.getLeft();
          }
          //打印当前节点
          System.out.println(node);
          //如果当前节点的右指针指向的是后继节点就一直输出
          while (node.getRightType() == 1){
              //获取到当前节点的后继节点
              node = node.getRight();
              System.out.println(node);
          }
          //替换这个遍历的节点
          node = node.getRight();
      }
   }
   ```

### 13.8 堆

#### 13.8.1 堆基本介绍

- 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，最坏，最好，平均时间复杂度都是O（nlogn），不稳定的排序
- 堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值称为大顶堆
- 小于或等于左右孩子节点的值称为小顶堆

#### 13.8.2 堆排序

**基本思想**

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

**基本步骤**

1. 构造初始堆，顺序存放
2. 从最后一个非叶子节点：arr.length/2-1,开始，从左至右，从下至上进行调整
3. 找到第二个非叶子节点，比较其与子节点的大小进行交换
4. 这会导致其交换子树的顺序混乱则继续向下交换
5. 堆顶出堆，针对剩余元素重复上列步骤

**代码实现**

```java
package com.why.tree;

import java.util.Arrays;
import java.util.jar.JarEntry;

/**
 * @Description TODO 堆排序
 * @Author why
 * @Date 2020/11/26 18:05
 * Version 1.0
 **/
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4,6,8,5,9};
        heapSort(arr);
    }

/**
     * 堆排序
     * @param arr
     */
    public static void heapSort(int[] arr){
        int temp = 0;
        //调整成大顶堆
        for (int i = arr.length/2 - 1; i >= 0 ; i--) {
            adjustHeap(arr,i,arr.length);
        }
        //将堆顶元素与末尾元素交换，将最大元素沉到数组末端
        for (int i = arr.length - 1; i > 0; i--) {
            //交换
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr,0, i);
        }
        System.out.println(Arrays.toString(arr));
    }

/**
     * 将数组（二叉树）调整为大顶堆
     * 完成将i对应的的非叶子节点调整成大顶堆
     * 自下向上调整
     * @param arr 待调整的数组
     * @param i 表示非叶子节点在数组中的索引
     * @param lengt    表示对多少个元素进行调整，lengt逐渐减小
     */
    public static void adjustHeap(int[] arr,int i,int lengt){
        //取出当前的值，保存至临时变量
        int temp = arr[i];
        //开始调整
        //j = i * 2 + 1,j是i节点的左子节点
        for (int j = i * 2 + 1; j < lengt; j = j * 2 + 1) {
            if(j + 1< lengt &&arr[j] < arr[j+1]){//左子节点小于右子节点
                j++;//j指向右子节点
            }
            if (arr[j] > temp){//如果子节点大于父节点
                arr[i] = arr[j];//把子节点较大的值与父节点交换
                i = j;//i指向j继续循环比较
            }else {
                break;
            }
        }
        //for循环结束后已将以i为父节点的的树的的最大值放到了堆顶（局部）
        arr[i] = temp;//将temp赋值放到最后的位置
    }
}
```

### 13.9 霍夫曼树

#### 13.9.1 基本介绍和创建

**基本介绍**

- 又称哈夫曼树，赫夫曼树
- 给定n个权值作为n个叶子节点，构造一棵二叉树，若该树的带权路径长度（wpl）达到最小，称为最优二叉树
- 霍夫曼树是带权路径长度最短的树，权值较大的节点离根较近

**几个重要的概念**

- **路径和路径长度**：一棵树中从一个节点往下可以达到的子节点之间的通路叫做路径，通路中分支的数目称为路径长度。如规定根节点的层数为1，则从根节点到L层节点的路径长度为L - 1
- **节点的权及带权路径长度：**若将书中的节点赋值给一个有着某种含义的数值，则这个数值称为节点的权，带权路径长度为路径与权值的成绩
- **树的带权路径长度：**所有叶子节点的带权路径长度之和，记为WPL，权值越大的节点离根节点越近的二叉树才是最优二叉树
- WPL最小的就是霍夫曼树

举例说明：

**创建霍夫曼树**

1. 将数据从小到大排序，每个数据看成一个节点，每个节点是最简单的二叉树
2. 取出根节点权值最小的两颗二叉树
3. 组成一棵新的二叉树，该新的二叉树的根节点的权值是前面两颗二叉树根节点权值之和
4. 再将这颗心的二叉树，以根节点的权值大小再次排序，不断重复上述步骤
5. 直到数列中，所有的数据都被处理就得到一棵霍夫曼树

**创建霍夫曼树的过程图解**

1. 数据为：{13，7，8，3，29，6，1}

2. 排序：{1，3，6，7，8，13，29}

3. 取出1，3创建，根节点权值为两节点权值之和，数据：{4，6，7，8，13，29}

![image-20201128131417563](https://img2020.cnblogs.com/blog/2211066/202011/2211066-20201128131416843-96432062.png)

4. 处理4，6，数据：{7，8，10，13，29}

5. 后面依次处理剩余数据……直到所有数据处理完毕

**代码实现创建霍夫曼树**

```Java
package com.why.tree;

import javax.swing.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Description TODO 创建霍夫曼树
 * @Author why
 * @Date 2020/11/28 13:23
 * Version 1.0
 **/
public class HuffmanTreeDemo {
    public static void main(String[] args) {
        int[] arr = {13,7,8,3,29,6,1};
        HuffmanNode root = creatHuffmanTree(arr);
        preOrder(root);
    }

/**
     * 创建霍夫曼树
     * @param arr
     * @return
     */
    public static HuffmanNode creatHuffmanTree(int[] arr){
        //构建Node，装入list
        List<HuffmanNode> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            list.add(new HuffmanNode(arr[i]));
        }

//从小到大排序
        Collections.sort(list);

//循环处理
        while (list.size() > 1){
            //取出权值最小的两个二叉树
            HuffmanNode left = list.get(0);
            HuffmanNode right = list.get(1);
            //构建新的二叉树
            HuffmanNode root = new HuffmanNode(left.value+right.value);
            root.left = left;
            root.right = right;
            //从list中删除处理过的二叉树
            list.remove(left);
            list.remove(right);
            //将root加入list
            list.add(root);
            //重新排序
            Collections.sort(list);
        }

return list.get(0);
    }

public static void preOrder(HuffmanNode root){
        if (root != null){
            root.preOrder();
        }else {
            System.out.println("空树");
        }
    }
}

/**
 * 创建节点类
 * 为了让Node对象支持Collections排序，让Node实现Comparable接口
 */
class HuffmanNode implements Comparable<HuffmanNode>{
    int value;//节点权值
    HuffmanNode left;//左指针
    HuffmanNode right;//右指针

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

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

/**
     * 排序比较
     * @param o
     * @return
     */
    @Override
    public int compareTo(HuffmanNode o) {
        //从小到大排序
        int a = this.value - o.value;
        return a;
    }

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

### 13.10 霍夫曼编码

**基本介绍**

1. 是霍夫曼树在电讯通信的一种经典应用
2. 霍夫曼编码广泛应用于数据文件压缩，压缩率通常在20% ~ 80%之间
3. 霍夫曼编码是可变字长编码（VLC）的一种

**通信领域中处理方式**

1. 定长编码,利用其ASCII码值对应的二进制进行传输
2. 变长编码：用特定的数字或数字组合对应不同的字符
3. 前缀编码：字符的编码都不能是其他字符编码的前缀，即不能匹配到重复的编码，无二义性

#### 13.10.1 霍夫曼编码的原理

**基本步骤**

1. 拿到传输的字符串

2. 统计各个字符串出现的个数

3. 按照字符出现的次数构建一棵霍夫曼树，次数位权值（构建步骤参考上文）

4. 根据霍夫曼树进行编码，向左的路径为0，向右的路径为1，如：

**说明**

1. 霍夫曼编码是无损压缩
2. 霍夫曼树根据排序方法不同，也可能不太一样，对应的霍夫曼编码不同，但树的权值（WPL）相同，编码的长度相同

#### 13.10.2 数据压缩

**字符串**

“I like like like java do you like a java”

##### **13.10.2.1 创建霍夫曼树**

**思路：**

- 节点类

Node{data(存放数据),weight(权值),left和right}

- 得到字符串对应的byte数组

- 编写方法，准备构建霍夫曼树的Node节点放到list，形式{Node[data= , weight = ,],…}

- 通过list创建霍夫曼树

**代码实现**

- 节点类

```Java
  /**
   * 创建Node，数据和权值
   * implements Comparable<HuffNode>,支持排序
   */
  class HuffNode implements Comparable<HuffNode>{
      Byte data;//存放数据
      int weight;//权值
      HuffNode left;
      HuffNode right;
  
      public HuffNode(Byte data, int weight) {
          this.data = data;
          this.weight = weight;
      }
  
      /**
       * 支持比较
       * @param o
       * @return
       */
      @Override
      public int compareTo(HuffNode o) {
          //从小到大排
          return this.weight - o.weight;
      }
  
      @Override
      public String toString() {
          return "HuffNode{" +
                  "data=" + data +
                  ", weight=" + weight +
                  '}';
      }
  
      /**
       * 前序遍历
       */
      public void preOrder(){
          System.out.println(this);
          if (this.left != null){
              this.left.preOrder();
          }
          if (this.right != null){
              this.right.preOrder();
          }
      }
  }
  ```

- 创建霍夫曼树

```java
  /**
   * 用list存放Node
   * @param bytes
   * @return
   */
  private static List<HuffNode> getNodes(byte[] bytes){
      //创建list
      List<HuffNode> nodes = new ArrayList<>();
  
      //存储每隔byte出现的次数->map
      Map<Byte,Integer> counts = new HashMap<>();
      for (byte b: bytes
           ) {
          Integer count = counts.get(b);
          if (count == null){//map还没有这个byte
              //存放
              counts.put(b,1);
          }else {//
              counts.put(b,count + 1);
          }
      }
  
      //把每个键值对转成Node对象，并加入到nodes集合
      for (Map.Entry<Byte,Integer> entery: counts.entrySet()
           ) {
          nodes.add(new HuffNode(entery.getKey(),entery.getValue()));
      }
  
      return nodes;
  }
  
  /**
   * 建立霍夫曼树
   * @param nodes
   * @return
   */
  private static HuffNode creatHuffTree(List<HuffNode> nodes){
      while (nodes.size() > 1){
          //排序
          Collections.sort(nodes);
          HuffNode left = nodes.get(0);
          HuffNode right = nodes.get(1);
          HuffNode parent = new HuffNode(null,left.weight + right.weight);
          parent.left = left;
          parent.right = right;
          nodes.remove(left);
          nodes.remove(right);
          nodes.add(parent);
      }
      return nodes.get(0);//返回根节点
  }
  
  /**
   * 前序遍历
   * @param root
   */
  private static void preOrder(HuffNode root){
      if (root != null){
          root.preOrder();
      }else {
          System.out.println("空树");
      }
  }
  ```

- 测试

```java
  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<HuffNode> nodes = getNodes(bytes);
      System.out.println(nodes);
  
      //测试创建的二叉树
      System.out.println("霍夫曼树：" );
      HuffNode huffNode = creatHuffTree(nodes);
      preOrder(huffNode);
  }
  ```

##### 13.10.2.2 生成霍夫曼编码表

- 根据霍夫曼树进行编码，向左的路径为0，向右的路径为1

**思路**

1. 将霍夫曼编码表存放在map中Map<Byte,String>
2. 在生成霍夫曼编码表时，需要拼接路径，定义StringBulider，存储某个叶子节点的路径

**代码实现**

- 生成霍夫曼编码表

```Java
  static Map<Byte,String> huffCodes = new HashMap<>();
  static StringBuilder stringBuilder = new StringBuilder();
  
  /**
   * 功能：将传入的node节点的所有的叶子节点的霍夫曼编码得到，并放入到huffCodes
   * @param node 传入的节点
   * @param code 路径，左0，右1
   * @param stringBuilder 用于拼接路径
   */
  private static void getCodes(HuffNode node,String code,StringBuilder stringBuilder){
      StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
      //将传入的code加入到stringBulider2
      stringBuilder2.append(code);
      if (node != null){//node == null 不处理
          //判断当前node，是叶子节点还是非叶子节点
          if (node.data == null){//非叶子节点
              //递归处理
              //向左递归
              getCodes(node.left,"0",stringBuilder2);
              //向右递归
              getCodes(node.right,"1",stringBuilder2);
          }else {//叶子节点
              //表示找到某个叶子节点的最后
              huffCodes.put(node.data,stringBuilder2.toString());
          }
      }
  }
  
  /**
   * 重载
   * @param root
   */
  private static Map<Byte,String> getCodes(HuffNode root){
      if (root == null){
          return null;
      }else {
          //处理root
          //处理左子树
          getCodes(root.left,"0",stringBuilder);
          //处理右子树
          getCodes(root.right,"1",stringBuilder);
      }
      return huffCodes;
  }
  ```

- 测试

```Java
  //测试是否生成了霍夫曼编码表
  getCodes(huffNode);
  System.out.println("霍夫曼编码表：" + huffCodes);
  ```

##### 13.10.2.3 生成霍夫曼编码后字符串的数据

编写方法，将字符串对应的byte数组，通过生成的霍夫曼编码表，返回一个霍夫曼编码压缩后的byte[]

- 生成霍夫曼编码后的字节数组

```java
  /**
       * 编写方法，将字符串对应的byte数组，通过生成的霍夫曼编码表，返回一个霍夫曼编码压缩后的byte[]
       * @param bytes 原始字符串 对应的byte[]
       * @param huffCodes 生成的霍夫曼编码map
       * @return  返回霍夫曼编码处理后的byte[]
       *  补码 = 反码 + 1
       *  源码 = 反码符号位不变，其余取反
       */
      private static byte[] zip(byte[] bytes,Map<Byte,String> huffCodes){
          //1.利用huffCodes将bytes转成霍夫曼编码后的字符串
          StringBuilder stringBuilder = new StringBuilder();
          //遍历byte【】
          for (byte b: bytes
               ) {
              stringBuilder.append(huffCodes.get(b));
          }
  //        System.out.println(stringBuilder);
          //将字符串转成byte数组
          //统计返回huffCodesBytes长度
          int len;
          if (stringBuilder.length() % 8 == 0){
              len = stringBuilder.length()/8;
          }else {
              len = stringBuilder.length()/8 + 1;
          }
          //创建存储压缩后的byte数组
          byte[] huffCodeBytes = new byte[len];
          int index = 0;//记录第几个byte
          for (int i = 0; i < stringBuilder.length(); i += 8) {//每8位对应一个byte
              String strByte;
              if (i + 8 > stringBuilder.length()){//不够八位
                  strByte = stringBuilder.substring(i);
              }else {
                  strByte = stringBuilder.substring(i,i+8);
              }
              //将strByte转成一个byte
              huffCodeBytes[index] = (byte) Integer.parseInt(strByte,2);
              index++ ;
          }
          //拿到霍夫曼编码对应的字节数组返回
          return huffCodeBytes;
      }
  ```

- 测试

```java
  byte[] zip = zip(bytes, huffCodes);
  System.out.println("霍夫曼编码后的bytes：" + Arrays.toString(zip));
  ```

##### 13.10.2.4 封装测试方法得到霍夫曼编码后的字节数组

```java
/**
 * 封装得到霍夫阿曼编码对应的数组
 * @param bytes
 * @return
 */
private static byte[] huffmanZip(byte[] bytes) {

List<HuffNode> nodes = getNodes(bytes);

//测试创建的二叉树
    HuffNode huffNode = creatHuffTree(nodes);

//测试是否生成了霍夫曼编码表
    getCodes(huffNode);

byte[] zip = zip(bytes, huffCodes);
    return zip;
}
```

#### 13.10.3 数据解压

- 使用霍夫曼编码表进行解码
- 编码的逆过程

**思路**

- 将编码后的byte[] 转成二进制字符串
- 将霍夫曼编码对应的二进制字符串，对照霍夫曼编码表转成字符串对应的字节数组

##### 13.10.3.1 将byte[]转为bitString

```java
/**
 * 将byte转成二进制字符串
 * @param b
 * @param flag 标志是否需要补高位
 * @return 按补码返回
 */
private static String byteToBitString(byte b,boolean flag){
    int temp = b;//将b转成int

String str = Integer.toBinaryString(temp);
    //返回temp对应二进制的补码，正数的时候需要补位
    if (flag){
        temp |= 256;//按位与，256 1 0000 0000 | 0000 0001 ==> 1 0000 0001
        return str.substring(str.length() - 8);//返回后8位
    }else {//后面不满8位不需要补齐
        return str;
    }
}
```

##### 13.10.3.2 数据解码

```java
/**
 * 数据解压缩
 * @param huffCodes 霍夫曼编码表
 * @param huffBytes 压缩后的byte[]
 * @return //返回字符串byte[]
 */
private static byte[] decode(Map<Byte,String> huffCodes,byte[] huffBytes){
    //1.得到huffBytes对应的二进制字符串
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0; i < huffBytes.length; i++) {
        if (i == huffBytes.length - 1){
            String str = byteToBitString(huffBytes[i], false);
            stringBuilder.append(str);
        }else {
            String str = byteToBitString(huffBytes[i], true);
            stringBuilder.append(str);
        }
    }
    //把字符串按照指定的霍夫曼编码表进行解码
    Map<String,Byte> map = new HashMap<>();//将huffCodes键值对反转
    for (Map.Entry<Byte,String> entry:huffCodes.entrySet()){
        map.put(entry.getValue(),entry.getKey());
    }
    //创建list，存放byte
    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);
            //count移动，直到匹配到一个字符
            b = map.get(key);
            if (b != null){//匹配到
                flag = false;
            }else {//未匹配到
                count ++;
            }
        }
        list.add(b);
        i += count;//i移动到count
    }
    //list中存放了所有字符
    byte[] bytes = new byte[list.size()];
    for (int i = 0; i < list.size(); i++) {
        bytes[i] = list.get(i);
    }
    return bytes;
}
```

#### 13.10.4 文件压缩

**思路**

读取文件 —> 得到霍夫阿曼编码表 —-> 完成压缩

**代码实现**

```java
/**
 * 将文件进行压缩
 * @param srcFile   传入希望压缩文件的全路径
 * @param dstFile   压缩后文件目录
 */
public static void zipFile(String srcFile,String dstFile){
    //创建文件输入流，读取文件
    FileInputStream is = null;
    //创建输出流，存放压缩文件
    FileOutputStream os = null;
    //创建一个和文件输出流关联的ObjectOutputStream
    ObjectOutputStream oos = null;
    try {
        is = new FileInputStream(srcFile);
        //创建和源文件大小 相同的byte[]
        byte[] b = new byte[is.available()];
        //读取文件
        is.read(b);
        //使用霍夫曼编码进行编码，获取霍夫曼编码表
        //直接对源文件进行压缩
        byte[] huffmanBytes = huffmanZip(b);
        //存放压缩文件
        os = new FileOutputStream(dstFile);
        //new一个和文件输出流关联的ObjectOutputStream
        oos = new ObjectOutputStream(os);
        //把霍夫曼编码后的字节数组写入压缩文件
        oos.write(huffmanBytes);
        //这里以对象流的方式写入霍夫曼编码，目的是为了以后恢复原文件时使用
        //一定要把霍夫曼编码写入压缩文件
        oos.writeObject(huffCodes);
    } catch (Exception e) {
        e.printStackTrace();
    } finally {
        try {
            is.close();
            os.close();
            oos.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
```

#### 13.10.5 文件解压

**思路**

读取压缩文件(数据和霍夫曼编码表) —->完成解压

**代码实现**

```java
//编写一个方法，完成对压缩文件的解压
/**
 *
 * @param zipFile 准备解压的文件
 * @param dstFile 将文件解压到哪个路径
 */
public static void unZipFile(String zipFile, String dstFile) {

//定义文件输入流
    InputStream is = null;
    //定义一个对象输入流
    ObjectInputStream ois = null;
    //定义文件的输出流
    OutputStream os = null;
    try {
        //创建文件输入流
        is = new FileInputStream(zipFile);
        //创建一个和  is关联的对象输入流
        ois = new ObjectInputStream(is);
        //读取byte数组  huffmanBytes
        byte[] huffmanBytes = (byte[])ois.readObject();
        //读取赫夫曼编码表
        Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();

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

try {
            os.close();
            ois.close();
            is.close();
        } catch (Exception e2) {
            // TODO: handle exception
            System.out.println(e2.getMessage());
        }

}
}
```

#### 13.10.6 霍夫曼编码注意事项

1. 如果文件本身时经过压缩处理的，那么编码后效果不明显
2. 霍夫曼编码是按字节来处理的，可以处理所有的文件
3. 如果一个文件中的内容不多，重复的数据不多，压缩效果不明显

### 13.11 二叉排序树（BST)

#### 13.11.1 需求

给定数列{7，3，10，12，5，1，9}，要求能够高效的完成对数据的查询和添加

**思路三则**

1. 使用数组，缺点：插入和排序速度较慢
2. 链式存储，添加较快，但查找速度慢
3. 使用二叉排序树

#### 13.11.2 基本介绍

对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大

**图解**

**步骤**

1. 从数列取出第一个数成为根节点
2. 取出第二个数，从根结点开始比较，大于当前节点，与右子节点比较，小于当前节点与左子节点比较
3. 直到放到叶子节点
4. 取出剩余的数值，重复上述步骤

#### 13.11.3 建立二叉排序树

**代码实现：BinarySortTree.java**

```java
package com.why.binary_sort_tree;

/**
 * @Description TODO 建立二叉排序树
 * @Author why
 * @Date 2020/12/1 14:38
 * Version 1.0
 **/
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7,3,10,12,5,1,9};
        BinarySortTree bst = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node(arr[i]);
            bst.add(node);
        }
        System.out.println("中序遍历二叉排序树；");
        bst.midOrder();
    }
}

/**
 * 二叉排序树
 */
class BinarySortTree{
    private Node root;

/**
     * 添加节点
     * @param node
     */
    public void add(Node node){
        if (root == null){//直接放上
            root = node;
        }else {
            root.add(node);
        }
    }

/**
     * 中序遍历
     */
    public void midOrder(){
        if (root != null){
            root.midOrder();
        }else {
            System.out.println("二叉排序树为空");
        }
    }
}
/**
 * 节点类
 */
class Node{
    int value;
    Node left;
    Node right;

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

/**
     * 添加节点，递归形式，需满足二叉排序树的要求
     * @param node
     */
    public void add(Node node){
        if (node == null){
            return;
        }
        //判断传入的节点的值和当前子树的根节点的值的关系
        if (node.value < this.value){
            if (this.left == null){//当前节点左子节点为空
                this.left = node;
            }else {//不为空，递归向左子树添加
                this.left.add(node);
            }
        }else {
            if (this.right == null){
                this.right = node;
            }else {
                this.right.add(node);
            }
        }
    }

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

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

#### 13.11.3 二叉排序树删除

##### 13.11.3.1 删除的节点是叶子节点

**思路**

1. 先找到要删除的节点targetNode
2. 找到targetNode的父节点parent
3. 确定targetNode是parent的左子节点还是右子节点
4. 根据前面的情况对应删除

##### 13.11.3.2 删除的节点只有一棵子树的情况

**思路**

1. 先找到要删除的节点targetNode
2. 找到targetNode的父节点parent
3. 确定targetNode的子节点是左子节点还是右子节点
4. 确定targetNode是parent的左子节点还是右子节点
5. 如果targetNode有左子节点
   - targetNode是parent的左子节点 parent.left = targetNode.left
   - targetNode是parent的右子节点parent.right = tsrgetNode.left
6. 如果targetNode有右子节点
   - targetNode是parent的左子节点parent.left = targetNode.right
   - targetNode是parent的右子节点parent.right = psrent.right

##### 13.11.3.3 删除的节点有两颗子树

**思路**

1. 先找到要删除的节点targetNode
2. 找到targetNode的父节点parent
3. 从targetNode的右子树找到最小的节点
4. 用一个临时变量，将最小的节点的值保存temp
5. 删除最小节点
6. targetNode.value = temp.value

##### 13.11.3.4 代码实现

```java
package com.why.binary_sort_tree;

/**
 * @Description TODO 建立二叉排序树
 * @Author why
 * @Date 2020/12/1 14:38
 * Version 1.0
 **/
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7,3,10,12,5,1,9,0,2,4,6,8,};
        BinarySortTree bst = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node(arr[i]);
            bst.add(node);
        }
        System.out.println("中序遍历二叉排序树；");
        bst.midOrder();

System.out.println("删除后");
        bst.deleteNode(5);
        bst.midOrder();

}
}

/**
 * 二叉排序树
 */
class BinarySortTree{
    private Node root;

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

/**
     * 查找需删除的节点
     * @param value
     * @return
     */
    public Node search(int value){
        if (root == null){
            return null;
        }else {
            return root.search(value);
        }
    }

/**
     * 查找父节点
     * @param value
     * @return
     */
    public Node searchParent(int value){
        if (root == null){
            return null;
        }else {
            return root.searchParent(value);
        }
    }

public void deleteNode(int value){
        if (root == null){
            return;
        }else {
            //找到需删除的节点
            Node targetNode = search(value);
            if (targetNode == null){//未找到
                return;
            }
            //如果二叉排序树只有一个节点
            if (root.left == null && root.right == null){
                return;
            }

//查找需删除的节点的父节点
            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) ||
                    (targetNode.right != null && targetNode.left == null)) {//只有一棵子树
                    //确定targetNode的节点是左节点还是右节点
                    if (targetNode.left != null) {//左子节点
                        if (parent != null){//非根节点
                            //确定targetNode是parent的左子节点还是右子节点
                            if (parent.left.value == value) {//左子节点
                                parent.left = targetNode.left;
                            } else {//右子节点
                                parent.right = targetNode.left;
                            }
                        }else {
                            root = targetNode.left;
                        }
                    } else {//右子节点
                        if (parent != null){
                            //确定targetNode是parent的左子节点还是右子节点
                            if (parent.left.value == value) {//左子节点
                                parent.left = targetNode.right;
                            } else {//右子节点
                                parent.right = targetNode.right;
                            }
                        }else {
                            root = targetNode.right;
                        }
                    }
            }else {//删除的节点有两颗子树
                //找到最小值并删除
                int minValue = deleteRightMin(targetNode.right);
                //将最小值赋值给targetNode.value
                targetNode.value = minValue;
            }
        }
    }

/**
     * 寻找最小值
     * @param node
     * @return
     */
    public int deleteRightMin(Node node){
        Node target = node;
        while (target.left != null){
            target = target.left;
        }
        //这时target指向最小节点
        //删除最小节点
        deleteNode(target.value);
        //返回最小节点的value
        return target.value;
    }
}
/**
 * 节点类
 */
class Node{
    int value;
    Node left;
    Node right;

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

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

/**
     * 寻找需要删除的节点
     * @param value
     * @return
     */
    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
     */
    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;//没有找到父节点
            }
        }
    }
}

```

### 13.12 平衡二叉树（AVL树）

**二叉排序树问题分析**

1. 左子树全部为空，从形式上看更像一个单链表
2. 插入速度没有影响
3. 查询速度明显降低
4. 解决方案：平衡二叉树

**基本介绍**

1. 平衡二叉树也叫二叉搜索树，保证查询效率较高
2. 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两棵子树都是一棵平衡二叉树
3. 常用的实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等

#### 13.12.1 平衡二叉树左旋转

**使用条件**

右子树高度与左子树高度插值大于1的时候，使用左旋转

**要求**

给定数列{4，3，6，5，7，8}，创建对应的平衡二叉树

**创建二叉排序树**

此时若转换为平衡二叉树，降低右子树的高度

**思路分析**

1. 创建一个新节点newNode ，值等于当前根节点的值
2. 把新节点的左子树设置为当前节点的左子树，newnode.left = left
3. 把新结点的右子树设置为当前节点右子树的左子树newNode.right = right.left
4. 把当前节点的值换位右子节点的值 value = right.value
5. 把当前节点的右子树设置成右子树的右子树right = right.right
6. 把当前节点的左子树设置为新节点 left = newLeft

**转换后**

#### 13.12.2 平衡二叉树右旋转

**要求**

使用数列{10，12，8，9，7，6}，创建平衡二叉树

**创建二叉排序树**

**基本思路**

1. 创建新的节点newNode，使得newNode.value = this.value
2. 将newNode的右子树设置为this的右子树,newNode.right = this.right
3. 将newNode的左子树设置为this左子树的右子树，newNode.left = this.left.right
4. 把this节点的值换为左子节点的值，this.value = this.left.value
5. 将this节点的左子树设置为左子树的左子树，this.left = this.left.left
6. 将this节点的右子树 设置为newNode，this.right = newNode

**转换后**

#### 13.12.3 平衡二叉树双旋转

**要求**

使用数列{10，11，7，6，8，9}，创建平衡二叉树

**创建二叉排序树**

**思路分析**

- 当孩子节点满足左旋转或右旋转条件时，先平衡孩子 节点，后平衡父节点

#### 13.12.4 创建平衡二叉树代码实现

```Java
package com.why.tree;

/**
 * @Description TODO 平衡二叉树
 * @Author why
 * @Date 2020/12/6 15:56
 * Version 1.0
 **/
public class AVLTreeDemo {
    public static void main(String[] args) {
        int[] arr = {10,11,7,6,8,9};
        //创建AVLTree对象
        AVLTree avlTree = new AVLTree();

//添加节点
        for (int i = 0; i < arr.length; i++) {
            avlTree.add(new AVLNode(arr[i]));
        }

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

//根节点树的高度
        System.out.println("根节点树的高度: " + avlTree.height());
        System.out.println("左子树高度：" + avlTree.leftHeight());
        System.out.println("右子树高度：" + avlTree.rightHeight());
        System.out.println("根节点：" + avlTree.getRoot());

}
}

/**
 * AVL,平衡二叉树
 */
class AVLTree{
    private AVLNode root;

public AVLNode getRoot() {
        return root;
    }

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

/**
     * 添加节点
     * @param node
     */
    public void add(AVLNode node){
        if (root == null){//直接放上
            root = node;
        }else {
            root.add(node);
        }
    }

/**
     * 查找需删除的节点
     * @param value
     * @return
     */
    public AVLNode search(int value){
        if (root == null){
            return null;
        }else {
            return root.search(value);
        }
    }

/**
     * 查找父节点
     * @param value
     * @return
     */
    public AVLNode searchParent(int value){
        if (root == null){
            return null;
        }else {
            return root.searchParent(value);
        }
    }

public void deleteNode(int value){
        if (root == null){
            return;
        }else {
            //找到需删除的节点
            AVLNode targetNode = search(value);
            if (targetNode == null){//未找到
                return;
            }
            //如果二叉排序树只有一个节点
            if (root.left == null && root.right == null){
                return;
            }

//查找需删除的节点的父节点
            AVLNode 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) ||
                    (targetNode.right != null && targetNode.left == null)) {//只有一棵子树
                //确定targetNode的节点是左节点还是右节点
                if (targetNode.left != null) {//左子节点
                    if (parent != null){//非根节点
                        //确定targetNode是parent的左子节点还是右子节点
                        if (parent.left.value == value) {//左子节点
                            parent.left = targetNode.left;
                        } else {//右子节点
                            parent.right = targetNode.left;
                        }
                    }else {
                        root = targetNode.left;
                    }
                } else {//右子节点
                    if (parent != null){
                        //确定targetNode是parent的左子节点还是右子节点
                        if (parent.left.value == value) {//左子节点
                            parent.left = targetNode.right;
                        } else {//右子节点
                            parent.right = targetNode.right;
                        }
                    }else {
                        root = targetNode.right;
                    }
                }
            }else {//删除的节点有两颗子树
                //找到最小值并删除
                int minValue = deleteRightMin(targetNode.right);
                //将最小值赋值给targetNode.value
                targetNode.value = minValue;
            }
        }
    }

/**
     * 寻找最小值
     * @param node
     * @return
     */
    public int deleteRightMin(AVLNode node){
        AVLNode target = node;
        while (target.left != null){
            target = target.left;
        }
        //这时target指向最小节点
        //删除最小节点
        deleteNode(target.value);
        //返回最小节点的value
        return target.value;
    }

/**
     * 返回根节点树的高度
     * @return
     */
    public int height(){
        return root.height();
    }

/**
     * 左子树的高度
     * @return
     */
    public int leftHeight(){
        return root.leftHeight();
    }

/**
     * 右子树的高度
     * @return
     */
    public int rightHeight(){
        return root.rightHeight();
    }

}

/**
 * 节点类
 */
class AVLNode{
    int value;
    AVLNode left;
    AVLNode right;

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

/**
     * 添加节点，递归形式，需满足二叉排序树的要求
     * @param node
     */
    public void add(AVLNode node){
        if (node == null){
            return;
        }
        //判断传入的节点的值和当前子树的根节点的值的关系
        if (node.value < this.value){
            if (this.left == null){//当前节点左子节点为空
                this.left = node;
            }else {//不为空，递归向左子树添加
                this.left.add(node);
            }
        }else {
            if (this.right == null){
                this.right = node;
            }else {
                this.right.add(node);
            }
        }

//当添加完节点后，若右子树的高度比左子树的高度的数值大于1
        if (rightHeight() - leftHeight() > 1){
            if (right != null && right.leftHeight() > right.rightHeight()){
                //对右子树 右旋转
                right.rightRotate();
            }
            //左旋转
            this.leftRotate();
            return;
        }
        //当添加完节点后leftHeight - rightHeight > 1
        if (leftHeight() - rightHeight() > 1){
            if (left != null && left.rightHeight() > left.leftHeight()){
                //对左子树左旋转
                left.leftRotate();
            }
            //右旋转
            this.rightRotate();
            return;
        }
    }

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

/**
     * 寻找需要删除的节点
     * @param value
     * @return
     */
    public AVLNode 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
     */
    public AVLNode 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;//没有找到父节点
            }
        }
    }

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

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

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

/**
     * 左旋转方法
     */
    private void leftRotate(){
        //创建新的节点，以当前根节点的值创建
        AVLNode newNode = new AVLNode(this.value);
        //把新的节点的左子树设置为当前节点的左子树
        newNode.left = this.left;
        //把新节点的右子树设置为当前节点右子树的左子树
        newNode.right = this.right.left;
        //将当前节点的值修改为右子树的值
        this.value = this.right.value;
        //将当前节点的右子树设置为右子树的右子树
        this.right = this.right.right;
        //将当前节点的左子节点设置为新的节点
        this.left = newNode;
    }

/**
     * 右旋转
     */
    private void rightRotate(){
        //以当前节点的值创建新的节点
        AVLNode newNode = new AVLNode(this.value);
        //将新节点的右子树设置为当前节点的右子树
        newNode.right = this.right;
        //将当前节点的左子树设置为当前节点左子节点的右子树
        newNode.left = this.left.right;
        //将当前节点的值用左子节点的值替换
        this.value = this.left.value;
        //将当前节点的左子节点设置为当节点左子节点的左子树
        this.left = this.left.left;
        //将当前节点的右子节点设置为新节点
        this.right = newNode;
    }
}
```

### 13.13 多路查找树

#### 13.13.1 二叉树和B树

##### 13.13.1.1 二叉树的问题分析

- 二叉树操作效率高
- 二叉树需要加载到内存，若二叉树的节点多存在如下问题：
  1. 问题1：构建二叉树时，需多次进行I/O操作，对与速度有影响
  2. 问题2：节点海量造成二叉树的高度很大，会降低操作速度

##### 13.13.1.2 多叉树

1. 在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据线和更多的子节点，就是多叉树（multiway tree)
2. 多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化

##### 13.13.1.3 B树的基本介绍

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

![image-20201206200951660](https://img2020.cnblogs.com/blog/2211066/202012/2211066-20201206200952372-338464149.png)

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

节点度：节点子树的个数

树的度：节点度的最大值是树的度

#### 13.13.2 2-3树

**基本介绍**

1. 2-3树是最简单的B-树结构
2. 2-3树的所有叶子节点都在同一层
3. 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点
4. 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
5. 2-3树是由二节点和三节点构成的树

##### **13.13.2.1 2-3树应用案例**

**要求**

将数列{16，24，12，32，14，26，34，10，8，28，38，20}构建成2-3树，并保证数据插入的大小顺序。

![image-20201206202756955](https://img2020.cnblogs.com/blog/2211066/202012/2211066-20201206202909477-1992385871.png)

**插入规则**

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

**构建过程图解**

![image-20201207163842325](https://img2020.cnblogs.com/blog/2211066/202012/2211066-20201207163902586-87168233.png)

#### 13.13.3 B树、B+树和B*树

##### 13.13.3.1 B树

- B-tree即B树，B即Balanced，平衡的意思。

- 2-3树和2-3-4树都是B树

B树如图：

![image-20201207164226814](https://img2020.cnblogs.com/blog/2211066/202012/2211066-20201207164225463-856832187.png)

**说明**

1. B树的阶：节点的最多的子节点个数
2. B树的搜索，从根节点开始，对节点内的关键字（有序）序列进行二分查找，命中则退出，否则查找孩子节点，直到所对应的孩子指针为空，或已经是叶子节点
3. 关键字分布在整棵树中，即叶子节点和非叶子节点都存放数据
4. 搜索有可能在非叶子节点结束
5. 其搜索性等价于在关键字全集内做一次二分查找

##### 13.13.3.2 B+树

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

如图：

![image-20201207164734623](https://img2020.cnblogs.com/blog/2211066/202012/2211066-20201207164809613-1458932325.png)

**说明**

1. B+树的搜索与B树基本相同，区别是B+树只有达到叶子节点才命中，其性能也等价于在关键字全集做一次二分查找
2. 所有关键字都出现在叶子节点的链表中，数据只能在叶子节点（稠密索引），且链表中的关键字是有序的
3. 非叶子节点相当于是叶子节点的所有（稀疏索引），叶子节点相当于是存储（关键字）数据的数据层
4. 更适合文件索引系统
5. B树和B+树各有自己的应用场景

##### 13.13.3.3 B*树

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

如图

![image-20201207165326321](https://img2020.cnblogs.com/blog/2211066/202012/2211066-20201207165359718-1132870804.png)

**说明**

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

## 十四、图

### 14.1 图的基本介绍

**为什么要有图？**

1. 线性表局限于一个直接前去和一个直接后继的关系
2. 树也只能有一个直接前去也就是父节点
3. 当我们表示 多对多的关系是=时，就用到了图

**图的举例说明**

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

如图：

![image-20201207171852808](https://img2020.cnblogs.com/blog/2211066/202012/2211066-20201207171851452-1684963733.png)

**图的常用概念**

- 顶点：节点
- 边：顶点间的连接
- 路径：节点A到节点B的通路
- 无向图：顶点之间的连接没有方向
- 有向图：顶点之间的连接有方向
- 带权图：边带有权值的图

**图的表示方式**

1. **邻接矩阵**（二维数组表示）

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

![image-20201207172801153](https://img2020.cnblogs.com/blog/2211066/202012/2211066-20201207172759746-941414553.png)

- 0表示不直接连通，1表示直接连通

2. **邻接表**（链表表示）

- 邻接矩阵需要为每隔顶点都分配n个边的空间，其实有很多边都是不存在的，会造成空间损失

- 邻接表只关心存在的边

- 邻接表由数组 + 链表组成

![image-20201207173258302](https://img2020.cnblogs.com/blog/2211066/202012/2211066-20201207173256924-1227187966.png)

- 二维数组表示各个节点标号，链表存储与之连通的节点标号

### 14.2 图的创建

**要求**

1. 代码实现如下图

![image-20201207173706293](https://img2020.cnblogs.com/blog/2211066/202012/2211066-20201207173704860-1004140461.png)

**思路分析**

1. 存储顶点 String 使用 ArrayList
2. 保存邻接矩阵矩阵，使用二维数组

**代码实现**

```java
package com.why.graph;

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

/**
 * @Description TODO 图
 * @Author why
 * @Date 2020/12/7 17:42
 * Version 1.0
 **/
public class Graph {

private ArrayList<String> vertexList;//存储顶点

private int[][] edges;//存储图的邻接矩阵

private int numOfEdges;//边的个数

public static void main(String[] args) {

//测试创建图
        int n = 5;//节点个数
        String[] Vertexs = {"A","B","C","D","E"};
        //创建图
        Graph graph = new Graph(n);
        //循环添加节点
        for (String value : Vertexs
             ) {
            graph.insertVertex(value);
        }
        //添加边
        //A-B,A-C,B-C,B-D,B-E互相连接
        graph.insertEdge(0,1,1);
        graph.insertEdge(0,2,1);
        graph.insertEdge(1,2,1);
        graph.insertEdge(1,3,1);
        graph.insertEdge(1,4,1);
        //打印
        graph.showGraph();
    }

/**
     * 构造器
     * @param n 顶点个数
     */
    public Graph(int n) {
        //初始化矩阵和顶点列表
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;
    }

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

/**
     * 添加边
     * @param v1 节点下标
     * @param v2 节点下标
     * @param weight 权值
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

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

/**
     * 返回边的数目
     * @return
     */
    public int getNumOfEdges(){
        return numOfEdges;
    }

/**
     * 返回下标为i的节点
     * @param i
     * @return
     */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

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

/**
     * 显示图的矩阵
     */
    public void showGraph(){
        //遍历二维数组
        for (int[] link : edges
             ) {
            System.err.println(Arrays.toString(link));
        }
    }
}
```

### 14.3 图的遍历

图的遍历，即是对节点的访问

#### 14.3.1 深度优先(Depth First Search , DFS)遍历

**基本思想**

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

**算法步骤**

1. 访问初始节点v,并标记节点v为已访问
2. 查找节点v的第一个邻接点w
3. 若w存在，则继续执行4，若不存在，则回到第1步，将从v的下一个节点继续
4. 若w未被访问，对w进行深度优先遍历递归
5. 查找节点v的w邻接节点的下一个邻接节点

**具体案例**

**代码实现**

1. 创建标志数组，标志节点是否被访问

```Java
   private boolean[] isVisited ;//标志节点是否被访问
   ```

2. dfs，深度优先遍历及其方法

```Java
   /**
    * 得到第一个邻接节点的下标
    * @return
    */
   public int getFirstNeighbor(int index){
       for (int i = 0; i < vertexList.size(); i++) {
           if (edges[index][i] > 0){//存在邻接节点返回 下标
               return i;
           }
       }
       return -1;
   }
   
   /**
    * 根据上一个邻接节点的下标获取下一个邻接节点
    * @param v1 当前节点
    * @param v2 当前节点已被访问的邻接节点
    * @return
    */
   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;
   }
   
   /**
    * 深度优先遍历
    * @param isVisited 标志数组
    * @param i 第一次就是0
    */
   private void dfs(boolean[] isVisited,int i){
       //首先访问该节点
       System.out.print(getValueByIndex(i) + "->");
       //将该节点设置为已访问
       isVisited[i] = true;
   
       //以i下标的节点为当前节点进行深度遍历
       //寻找第一个邻接节点
       int w = getFirstNeighbor(i);
       while (w != -1){//找到邻接节点
           if (!isVisited[w]){//没有被访问
               dfs(isVisited,w);
           }
           //如果w节点已经被访问，查找邻接节点的下一个节点
           w = getNextNeighbor(i,w);
       }
   }
   
   /**
    * 重载dfs，遍历所有的节点，对节点进行dfs深度优先遍历
    */
   public void dfs(){
       //遍历所有节点
       for (int i = 0; i < getNumOfVertex(); i++) {
           if (!isVisited[i]){//没有被访问过，进行深度遍历
               dfs(isVisited,i);
           }
       }
   }
   ```

3. 测试

```Java
   //测试深度优先遍历
   System.out.println("深度优先遍历：");
   graph.dfs();
   ```

#### 14.3.2 广度优先（Broad First Search，BFS）遍历

**基本介绍**

1. 类似于分层搜索的过程
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。

**代码实现**

```Java
/**
 * 对一个节点进行广度优先遍历
 * @param isVisited 标志数组
 * @param i 节点
 */
private void bfs(boolean[] isVisited,int i){
    int u;//表示队列的头节点对应的下标
    int w;//邻接节点w
    //队列，记录节点访问的顺序
    LinkedList queue = new LinkedList();
    //访问当前节点，输出信息
    System.out.print(getValueByIndex(i) + "->");
    //标记为已访问
    isVisited[i] = true;
    //将节点加入队列
    queue.addLast(i);
    while (!queue.isEmpty()) {//队列非空
        //取出队列的头节点下标
        u = (Integer) queue.removeFirst();
        //得到第一个邻接点下标
        w = getFirstNeighbor(u);
        while (w != -1) {//w存在
            //是否访问过
            if (!isVisited[w]) {//没有访问过
                System.out.print(getValueByIndex(w) + "->");
                //标记已经访问
                isVisited[w] = true;
                //入队列
                queue.addLast(w);
            }
            //以u为前驱点，找w后面的下一个邻接点
            w = getNextNeighbor(u,w);//体现出广度优先
        }
    }
}

/**
 * 重载，遍历所有的节点，对其都进行广度优先搜索
 */
public void bfs() {
    for (int i = 0; i < getNumOfVertex(); i++) {
        if (!isVisited[i]) {//没有被访问过
            bfs(isVisited, i);
        }
    }
}
```

#### 14.3.3 深度优先 VS 广度优先

![image-20201208162129967](https://img2020.cnblogs.com/blog/2211066/202012/2211066-20201208162131517-105098012.png)

### 14.4 图的代码汇总

```Java
package com.why.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.jar.JarEntry;

/**
 * @Description TODO 图
 * @Author why
 * @Date 2020/12/7 17:42
 * Version 1.0
 **/
public class Graph {

private ArrayList<String> vertexList;//存储顶点

private int[][] edges;//存储图的邻接矩阵

private int numOfEdges;//边的个数

private boolean[] isVisited ;//标志节点是否被访问

public static void main(String[] args) {

//        //测试深度优先遍历
//        System.out.println("深度优先遍历：");
//        graph.dfs();
//        System.out.println();

//测试广度优先遍历
        System.out.println("广度优先遍历：");
        graph.bfs();
    }

/**
     * 构造器
     * @param n 顶点个数
     */
    public Graph(int n) {
        //初始化矩阵和顶点列表
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;
        isVisited = new boolean[n];
    }

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

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

/**
     * 返回边的数目
     * @return
     */
    public int getNumOfEdges(){
        return numOfEdges;
    }

/**
     * 返回下标为i的节点
     * @param i
     * @return
     */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

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

/**
     * 显示图的矩阵
     */
    public void showGraph(){
        //遍历二维数组
        for (int[] link : edges
             ) {
            System.err.println(Arrays.toString(link));
        }
    }

/**
     * 得到第一个邻接节点的下标
     * @return
     */
    public int getFirstNeighbor(int index){
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0){//存在邻接节点返回 下标
                return i;
            }
        }
        return -1;
    }

/**
     * 根据上一个邻接节点的下标获取下一个邻接节点
     * @param v1 当前节点
     * @param v2 当前节点已被访问的邻接节点
     * @return
     */
    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;
    }

/**
     * 深度优先遍历
     * @param isVisited 标志数组
     * @param i 第一次就是0
     */
    private void dfs(boolean[] isVisited,int i){
        //首先访问该节点
        System.out.print(getValueByIndex(i) + "->");
        //将该节点设置为已访问
        isVisited[i] = true;

//以i下标的节点为当前节点进行深度遍历
        //寻找第一个邻接节点
        int w = getFirstNeighbor(i);
        while (w != -1){//找到邻接节点
            if (!isVisited[w]){//没有被访问
                dfs(isVisited,w);
            }
            //如果w节点已经被访问，查找邻接节点的下一个节点
            w = getNextNeighbor(i,w);
        }
    }

/**
     * 重载dfs，遍历所有的节点，对节点进行dfs深度优先遍历
     */
    public void dfs(){
        //遍历所有节点
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]){//没有被访问过，进行深度遍历
                dfs(isVisited,i);
            }
        }
    }

/**
     * 对一个节点进行广度优先遍历
     * @param isVisited 标志数组
     * @param i 节点
     */
    private void bfs(boolean[] isVisited,int i){
        int u;//表示队列的头节点对应的下标
        int w;//邻接节点w
        //队列，记录节点访问的顺序
        LinkedList queue = new LinkedList();
        //访问当前节点，输出信息
        System.out.print(getValueByIndex(i) + "->");
        //标记为已访问
        isVisited[i] = true;
        //将节点加入队列
        queue.addLast(i);
        while (!queue.isEmpty()) {//队列非空
            //取出队列的头节点下标
            u = (Integer) queue.removeFirst();
            //得到第一个邻接点下标
            w = getFirstNeighbor(u);
            while (w != -1) {//w存在
                //是否访问过
                if (!isVisited[w]) {//没有访问过
                    System.out.print(getValueByIndex(w) + "->");
                    //标记已经访问
                    isVisited[w] = true;
                    //入队列
                    queue.addLast(w);
                }
                //以u为前驱点，找w后面的下一个邻接点
                w = getNextNeighbor(u,w);//体现出广度优先
            }
        }
    }

/**
     * 重载，遍历所有的节点，对其都进行广度优先搜索
     */
    public void bfs() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {//没有被访问过
                bfs(isVisited, i);
            }
        }
    }
}
```

vvwhy/java_algorithm

简介

发行版

贡献者

近期动态

vvwhy/java_algorithm .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

vvwhy/java_algorithm