algorithm--这个是算法的英文单词（三）-阿里云开发者社区

快速排序案例

要求: 对 [-9,78,0,23,-567,70] 进行从小到大的排序，要求使用快速排序法。【测试 8w 和 800w】说明[验证分析]:

如果取消左右递归，结果是 -9 -567 0 23 78 70
如果取消右递归,结果是 -567 -9 0 23 78 70
如果取消左递归,结果是 -9 -567 0 23 70 78

public static void quickSort(int[] arr, int left, int right) {
        //  left index
        int l = left;
        int r = right;
        //    pivot 中轴值
        int pivot = arr[(left + right) / 2];
        //临时变量
        int temp = 0;
        //    while 循环的目的是比比中轴的pivot值小的放在左边
        //    比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 += 1;
            r -= 1;
        }
        //向左递归
        if (left < r) {
            quickSort(arr, left, r);
        }
        //向右递归
        if (right > l) {
            quickSort(arr, l, right);
        }
    }

排序过程断点调试

int arr[] = {-9, 78, 0, 23, -567};

我们的测试数组是一个五位数的数组，

进入循环，此时我们看到，中位数和左右两边的索引，0和4

这里我们可以看第一组数据，

下标0 arr[l] =- 9, -9小于0于是左边下标后移继续寻找，找到78，此时l = 1 是78对应的数组下标此时的78 比中位 0 要大，进入右侧比对

显然 arr[r] = -567 比中位数小，不需要改变下标，跳出循环，

此时我们对比因为我们之后需要重复的递归，这里就是我们递归的跳出条件，如果左边大于右边了，代表左边已经没有大于中位数的数了，反之右边也一定没有小于中位数的

此时，交换两边不符合条件的数字，将比0大的七十八交换到右边吗，将比0小的-567交换到左边

交换完成之后，判断左右两边此时小标的数字是否与中位数相等，如果相等就后移，不需要重复比对

此时我们的第一次循环就结束了，可以看到，数组已经被交换到了，我们的思路第一步的样子，

比中位数0 小的都在左边，比中位数0大的都在右边，之后我们需要重复递归，一直到交换不了为止

此时 r 与l相等，就代表都到中位数了，左右两边都递归有序了，此时我们需要将l后一位，r前移一位，防止栈溢出，并且再继续向下，再最后一次递归之前会结束，

后面的递归就是重复的分组重复的交换，一直到左索引小于又索引，代表还可以继续分组排序，直到左边递归完毕

右索引大于左索引代表可以继续向右边递归，一直到右边递归完毕

快速排序测速

八十万长度存放0-80w的随机数

可以看到，效率是十分的快速

有兴趣的小伙伴可以自己试试写一个冒泡排序测试一下，再拿小冷的快速排序测试一下，算法的精妙之处一下就能感受到了

归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

基本思想:

分开：将数组递归拆分成最小子序列，之后分组排序

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将

[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]

动态图

思路实现

给你一个数组, val arr = Array(8, 4, 5, 7, 1, 3, 6, 2 ), 请使用归并排序完成排序。

package com.hyc.DataStructure.sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class MergetSort {
    public static void main(String[] args) {
        int arr[] = {8, 4, 5, 7, 1, 3, 6, 2}; //
        //测试快排的执行速度
        // 创建要给80000个的随机的数组
        //int[] arr = new int[8000000];
        //for (int i = 0; i < 8000000; i++) {
        //    arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
        //}
        System.out.println("排序前");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);
        int temp[] = new int[arr.length]; //归并排序需要一个额外空间
        mergeSort(arr, 0, arr.length - 1, temp);
        Arrays.toString(arr);
        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的时间是=" + date2Str);
        //System.out.println("归并排序后=" + Arrays.toString(arr));
    }
    //分+合方法
    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) {
        int i = left; // 初始化i, 左边有序序列的初始索引
        int j = mid + 1; //初始化j, 右边有序序列的初始索引
        int t = 0; // 指向temp数组的当前索引
        //(一)
        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i <= mid && j <= right) {//继续
            //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
            //即将左边的当前元素，填充到 temp数组
            //然后 t++, i++
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else { //反之,将右边有序序列的当前元素，填充到temp数组
                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; //
        //第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
        //最后一次 tempLeft = 0  right = 7
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }
}

速度测试

长度为 8000000，每个内容为0-800000的随机数，

可以很稳定，两秒左右，同样是排序，思想不同带来的优化肉眼可见的，以上就是归并排序的内容啦

基数排序

经典空间换时间的思想流排序算法

基数排序(桶排序)介绍

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
基数排序(Radix Sort)是桶排序的扩展
基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个

位数分别比较。

基数排序基本思想

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

将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序

创建一个二维数组，arr[10][n] 10是作为的桶，n是每个桶要装的数，按照个位数取出放到桶里，之后再按照十位数，分桶，一般来说排序的次数和最大数的位数一致，但是空间占用会越来越大，金典的空间换时间的算法

第二轮

最后

动图演示

代码思路实验

要求：将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序

package com.hyc.DataStructure.sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class RadixSort {
    public static void main(String[] args) {
        int arr[] = {53, 3, 542, 748, 14, 214};
        // 80000000 * 11 * 4 / 1024 / 1024 / 1024 =3.3G
//  int[] arr = new int[8000000];
//  for (int i = 0; i < 8000000; i++) {
//    arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
//  }
        System.out.println("排序前");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);
        radixSort(arr);
        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的时间是=" + date2Str);
        System.out.println("基数排序后 " + Arrays.toString(arr));
    }
    //基数排序方法
    public static void radixSort(int[] arr) {
        //根据前面的推导过程，我们可以得到最终的基数排序代码
        //1. 得到数组中最大的数的位数
        int max = arr[0]; //假设第一数就是最大数
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();
        //定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
        //说明
        //1. 二维数组包含10个一维数组
        //2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
        //3. 名明确，基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //可以这里理解
        //比如：bucketElementCounts[0] , 记录的就是  bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];
        //这里我们使用循环将代码处理
        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][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
            int index = 0;
            //遍历每一桶，并将桶中是数据，放入到原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中，有数据，我们才放入到原数组
                if (bucketElementCounts[k] != 0) {
                    //循环该桶即第k个桶(即第k个一维数组), 放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入到arr
                        arr[index++] = bucket[k][l];
                    }
                }
                //第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
                bucketElementCounts[k] = 0;
            }
            //System.out.println("第"+(i+1)+"轮，对个位的排序处理 arr =" + Arrays.toString(arr));
        }
  /*
  //第1轮(针对每个元素的个位进行排序处理)
  for(int j = 0; j < arr.length; j++) {
   //取出每个元素的个位的值
   int digitOfElement = arr[j] / 1 % 10;
   //放入到对应的桶中
   bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
   bucketElementCounts[digitOfElement]++;
  }
  //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
  int index = 0;
  //遍历每一桶，并将桶中是数据，放入到原数组
  for(int k = 0; k < bucketElementCounts.length; k++) {
   //如果桶中，有数据，我们才放入到原数组
   if(bucketElementCounts[k] != 0) {
    //循环该桶即第k个桶(即第k个一维数组), 放入
    for(int l = 0; l < bucketElementCounts[k]; l++) {
     //取出元素放入到arr
     arr[index++] = bucket[k][l];
    }
   }
   //第l轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
   bucketElementCounts[k] = 0;
  }
  System.out.println("第1轮，对个位的排序处理 arr =" + Arrays.toString(arr));
  //==========================================
  //第2轮(针对每个元素的十位进行排序处理)
  for (int j = 0; j < arr.length; j++) {
   // 取出每个元素的十位的值
   int digitOfElement = arr[j] / 10  % 10; //748 / 10 => 74 % 10 => 4
   // 放入到对应的桶中
   bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
   bucketElementCounts[digitOfElement]++;
  }
  // 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
  index = 0;
  // 遍历每一桶，并将桶中是数据，放入到原数组
  for (int k = 0; k < bucketElementCounts.length; k++) {
   // 如果桶中，有数据，我们才放入到原数组
   if (bucketElementCounts[k] != 0) {
    // 循环该桶即第k个桶(即第k个一维数组), 放入
    for (int l = 0; l < bucketElementCounts[k]; l++) {
     // 取出元素放入到arr
     arr[index++] = bucket[k][l];
    }
   }
   //第2轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
   bucketElementCounts[k] = 0;
  }
  System.out.println("第2轮，对个位的排序处理 arr =" + Arrays.toString(arr));
  //第3轮(针对每个元素的百位进行排序处理)
  for (int j = 0; j < arr.length; j++) {
   // 取出每个元素的百位的值
   int digitOfElement = arr[j] / 100 % 10; // 748 / 100 => 7 % 10 = 7
   // 放入到对应的桶中
   bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
   bucketElementCounts[digitOfElement]++;
  }
  // 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
  index = 0;
  // 遍历每一桶，并将桶中是数据，放入到原数组
  for (int k = 0; k < bucketElementCounts.length; k++) {
   // 如果桶中，有数据，我们才放入到原数组
   if (bucketElementCounts[k] != 0) {
    // 循环该桶即第k个桶(即第k个一维数组), 放入
    for (int l = 0; l < bucketElementCounts[k]; l++) {
     // 取出元素放入到arr
     arr[index++] = bucket[k][l];
    }
   }
   //第3轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
   bucketElementCounts[k] = 0;
  }
  System.out.println("第3轮，对个位的排序处理 arr =" + Arrays.toString(arr)); */
    }
}

速度测试

八百万长度，内容为 0-8000000的随机数只需要一秒钟

我们简单计算一下用来多少内容

8000000 * 11 * 4 / 1024 / 1024 / 1024 =1G

从公式可以看出我们排序八百万使用到了1g的内存，从各方面都可以看出，基数排序是经典的空间换时间的算法

基数排序的说明:

基数排序是对传统桶排序的扩展，速度很快.
基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。
基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i]在 r[j]之前，而在排序后的序列中，r[i]仍在 r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]
有负数的数组，我们不用基数排序来进行排序, 如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9

哈希表

哈希表的基本介绍

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

技术前景：在还没有缓存产品的时候是如何解决的

图形化实现后的散列表

实现思路就是以数组来做为映射唯一标识，每一个数组内的索引对饮一条链表

举例部门编号就可以理解为数组的值

部门编号：姓名（链表保存的值）

google 上机题

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

要求:

不使用数据库,,速度越快越好=>哈希表(散列)
添加时，保证按照 id 从低到高插入 [课后思考：如果 id 不是从低到高插入，但要求各条链表仍是从低到高，怎么解决?
使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息

思路分析并画出示意图

思路实现

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.hashtable
 * @className: hashtebDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/1 3:01
 * @version: 1.0
 */
public class hashtebDemo {
    public static void main(String[] args) {
        //创建哈希表
        hashtable hashTab = new hashtable(7);
        //写一个简单的菜单
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add:  添加雇员");
            System.out.println("list: 显示雇员");
            System.out.println("find: 查找雇员");
            System.out.println("exit: 退出系统");
            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("输入id");
                    int id = scanner.nextInt();
                    System.out.println("输入名字");
                    String name = scanner.next();
                    //创建 雇员
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的id");
                    id = scanner.nextInt();
                    hashTab.findEmpById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}
//创建 hashtab 管理多条链表，就是用数组来映射， 哈希表的实现方式有两种
//1. 数组+ 链表
//2。 二叉树
class hashtable {
    //用于映射链表的数组
    private EmpLinkedList[] empLinkedListArrays;
    // 用来 记录长度
    private int size;
//    构造器 初始化
    public hashtable(int size) {
        this.size = size;
        //    初始化 Emplinkedlistarrays
        empLinkedListArrays = new EmpLinkedList[size];
        //   此处 这个时候不要分开初始化每一个链表，我们一次性初始化好
        for (int i = 0; i < size; i++) {
            empLinkedListArrays[i] = new EmpLinkedList();
        }
    }
    //    添加成员
    public void add(Emp emp) {
        //  根据员工id 得到员工应该添加再那个链表
        int emplinkedlistNo = hashFun(emp.id);
        //   将emp 添加对应的链表
        empLinkedListArrays[emplinkedlistNo].add(emp);
    }
    //遍历所有的链表 遍历hashtab
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListArrays[i].list(i);
        }
    }
    //查找id
    public void findEmpById(int id) {
        //       使用散列函数，确定到那条链表
        int empLinkedListNo = hashFun(id);
        Emp empByid = empLinkedListArrays[empLinkedListNo].findEmpByid(id);
        if (empByid == null) {
            System.out.println("并没有找到雇员");
        } else {
            System.out.println("在" + (empLinkedListNo + 1) + "链表中找到雇员,id为=>" + empByid.id);
        }
    }
    //    用取模法来根据id 来算出链表对应映射的id数组
    public int hashFun(int id) {
        return id % size;
    }
}
class Emp {
    public int id;
    public String name;
    public Emp next;
    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}
class EmpLinkedList {
    //头指针，执行第一个EMP 因此我们这个链表 的head是直接指向第一个emp
    private Emp head;
    //    添加雇员到列表
//    1. 假定 当添加雇员的时候 id 自增长 即是id的分配总是从小到大，所以我们不需要处理id是否有序的判断，
//    直接添加到当前链表的最后即可
    public void add(Emp emp) {
        //如果头节点是空的那么就将头节点添加，因为是第一个雇员
        if (head == null) {
            head = emp;
            return;
        }
        //    如果头节点不是空的那代表不是第一个，我们需要一个指针指向head节点
        Emp curEmp = head;
        //   之后循环链表到末尾添加
        while (true) {
            //如果进入这个if 那么代表链表到了最后
            if (curEmp == null) {
                break;
            }
            //每次循环将curEmp 后移一直到触发if 执行 break
            curEmp = curEmp.next;
        }
        //   退出循环代表curEmp 已经是最后一个了，这里我们将next 指向参数的 emp即可
        curEmp.next = emp;
    }
    //  遍历链表,参数是为了确定是属于那个链表
    public void list(int no) {
        if (head == null) {
            //   进入这个判断说明链表为空
            System.out.println("第" + (no + 1) + "链表为空");
            return;
        }
        System.out.print("第" + (no + 1) + "当前链表信息为");
        Emp curEmp = head;
        while (true) {
            System.out.printf("=>id%dname=%s\t", curEmp.id, curEmp.name);
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next;
        }
        System.out.println();
    }
    //根据id 查找链表
    public Emp findEmpByid(int id) {
        if (head == null) {
            System.out.println("该链表为空");
            return null;
        }
        Emp curemp = head;
        while (true) {
            if (curemp.id == id) {
                break;
            }
            if (curemp.next == null) {
                System.out.println("此链表没有要查找的雇员");
                break;
            }
            //后移
            curemp = curemp.next;
        }
        return curemp;
    }
}

效果演示

新增与遍历

查找

树的结构学习

二叉树简介

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

二叉树的概念

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

![image-20220217224612770](https://gitee.com/cold-abyss_admin/my-image-host/raw/master/ img /image-20220217224612770.png)

如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数二

层的叶子节点在右边连续，我们称为完全二叉树

数组

数组存储方式的分析

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

画出操作示意图：

链表

链式存储方式的分析

优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，

删除效率也很好)。

缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)

操作示意图：

二叉树

树存储方式的分析

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

可以保证数据的插入，删除，修改的速度

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

认识树结构

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

节点
根节点
父节点
子节点
叶子节点 (没有子节点的节点) 6) 节点的权(节点值) 7) 路径(从 root 节点找到该节点的路线) 8) 层
子树
树的高度(最大层数)
森林 :多颗子树构成森林

二叉树遍历的说明

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

二叉树遍历应用实例(前序,中序,后序)

二叉树遍历代码实例

public static void main(String[] args){
     //  测试，先创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        heroNode root = new heroNode(1, "宋江");
        heroNode node1 = new heroNode(2, "吴用");
        heroNode node2 = new heroNode(3, "卢俊义");
        heroNode node3 = new heroNode(4, "林冲");
        heroNode node4 = new heroNode(5, "关胜");
        //设置头节点
        binaryTree.setHead(root);
        // 此处我们手动的填补二叉树，之后还会有递归的方式填充二叉树
        root.setLeftNode(node1);
        root.setRightNode(node2);
        node2.setRightNode(node3);
        node2.setLeftNode(node4);
        //测试
        ////    前序遍历
        //binaryTree.PreOrder();
        ////中序遍历
        //System.out.println();
        //binaryTree.InfixOrder();
        ////后序遍历
        //System.out.println();
        //binaryTree.PostOrder();
 }    
class BinaryTree {
    //确定根节点
    private heroNode head;
    public void setHead(heroNode head) {
        this.head = head;
    }
    //   前序遍历
    public void PreOrder() {
        if (this.head != null) {
            this.head.PreOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //中序遍历
    public void InfixOrder() {
        if (this.head != null) {
            this.head.infixOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //后续遍历
    public void PostOrder() {
        if (this.head != null) {
            this.head.postOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
}
class heroNode {
    private int id;
    private String name;
    private heroNode leftNode;
    private heroNode rightNode;
    public heroNode getLeftNode() {
        return leftNode;
    }
    public void setLeftNode(heroNode leftNode) {
        this.leftNode = leftNode;
    }
    public heroNode getRightNode() {
        return rightNode;
    }
    public void setRightNode(heroNode rightNode) {
        this.rightNode = rightNode;
    }
    public heroNode(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;
    }
    @Override
    public String toString() {
        return "heroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    public void setName(String name) {
        this.name = name;
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.getLeftNode() != null) {
            this.leftNode.PreOrder();
        }
        if (this.getRightNode() != null) {
            this.rightNode.PreOrder();
        }
    }
    //    中序遍历
    public void infixOrder() {
        if (this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }
    //   后序遍历
    public void postOrder() {
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }
}

二叉树查找思路

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

思路图解

二叉树查找代码示例

为了方便更好的阅读代码，就把节点和树类的查找代码专门的写出来，后面会有全代码的部分

class BinatyTree{
    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }
}
class heroNode{
    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }
}

二叉树-删除节点

如果删除的节点是叶子节点，则删除该节点
如果删除的节点是非叶子节点，则删除该子树.
测试，删除掉 5 号叶子节点和 3 号子树.

思路分析

有关二叉树的，遍历，查找，删除的全代码

package com.hyc.DataStructure.tree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree
 * @className: BinaryTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/3 16:47
 * @version: 1.0
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        //  测试，先创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        heroNode root = new heroNode(1, "宋江");
        heroNode node1 = new heroNode(2, "吴用");
        heroNode node2 = new heroNode(3, "卢俊义");
        heroNode node3 = new heroNode(4, "林冲");
        heroNode node4 = new heroNode(5, "关胜");
        //设置头节点
        binaryTree.setHead(root);
        // 此处我们手动的填补二叉树，之后还会有递归的方式填充二叉树
        root.setLeftNode(node1);
        root.setRightNode(node2);
        node2.setRightNode(node3);
        node2.setLeftNode(node4);
        //测试
        ////    前序遍历
        //binaryTree.PreOrder();
        ////中序遍历
        //System.out.println();
        //binaryTree.InfixOrder();
        ////后序遍历
        //System.out.println();
        //binaryTree.PostOrder();
        //System.out.println("前中后查找");
        //System.out.println("开始前序查找");
        //heroNode resNode = binaryTree.preOrderSearch(5);
        //if (resNode != null) {
        //    System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
        //} else {
        //    System.out.println("查找失败");
        //}
        //System.out.println("开始中序查找");
        //heroNode resNode = binaryTree.infixOrderSearch(5);
        //if (resNode != null) {
        //    System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
        //} else {
        //    System.out.println("查找失败");
        //}
        //System.out.println("开始后序查找");
        //heroNode resNode = binaryTree.postOrderSearch(5);
        //if (resNode != null) {
        //    System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
        //} else {
        //    System.out.println("查找失败");
        //}
        //    删除测试
        System.out.println("删除前");
        binaryTree.PreOrder();
        System.out.println("删除后");
        binaryTree.deleteNode(5);
        binaryTree.PreOrder();
    }
}
class BinaryTree {
    //确定根节点
    private heroNode head;
    public void setHead(heroNode head) {
        this.head = head;
    }
    //   前序遍历
    public void PreOrder() {
        if (this.head != null) {
            this.head.PreOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //中序遍历
    public void InfixOrder() {
        if (this.head != null) {
            this.head.infixOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //后续遍历
    public void PostOrder() {
        if (this.head != null) {
            this.head.postOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }
    //    删除节点
    public void deleteNode(int no) {
        if (head != null) {
            if (head.getId() == no) {
                head = null;
                return;
            } else {
                head.deleteNode(no);
            }
        } else {
            System.out.println("空树,无法删除");
        }
    }
}
class heroNode {
    private int id;
    private String name;
    private heroNode leftNode;
    private heroNode rightNode;
    public heroNode getLeftNode() {
        return leftNode;
    }
    public void setLeftNode(heroNode leftNode) {
        this.leftNode = leftNode;
    }
    public heroNode getRightNode() {
        return rightNode;
    }
    public void setRightNode(heroNode rightNode) {
        this.rightNode = rightNode;
    }
    public heroNode(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;
    }
    @Override
    public String toString() {
        return "heroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    public void setName(String name) {
        this.name = name;
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.getLeftNode() != null) {
            this.leftNode.PreOrder();
        }
        if (this.getRightNode() != null) {
            this.rightNode.PreOrder();
        }
    }
    //    中序遍历
    public void infixOrder() {
        if (this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }
    //   后序遍历
    public void postOrder() {
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }
    //   前序查找
    public heroNode PreOrderSearch(int no) {
        System.out.println("前序查找");
        //比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.PreOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.PreOrderSearch(no);
        }
        return resNode;
    }
    //   中序查找
    public heroNode infixOrderSearch(int no) {
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.infixOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //比较当前节点的no 是不是我们要搜索的
        System.out.println("中序查找");
        if (this.id == no) {
            return this;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.infixOrderSearch(no);
        }
        return resNode;
    }
    //   后序查找
    public heroNode postOrderSearch(int no) {
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.postOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.postOrderSearch(no);
        }
        //如果不为null 那么代表右边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        System.out.println("后序查找");
        //左右子树，都没有找到，那么就比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        return resNode;
    }
    //    删除 
    public void deleteNode(int no) {
        //    向左边遍历 如果左边子树有点话就将左边子树置空，如果不是就遍历右边
        if (this.leftNode != null && this.leftNode.id == no) {
            this.leftNode = null;
            return;
        }
        //    向右边遍历 如果右边子树有点话就将左边子树置空，如果左右都没有那么就绪要递归的删除
        if (this.rightNode != null && this.rightNode.id == no) {
            this.rightNode = null;
            return;
        }
        //    如果上面两步都不成功那么我们先向左边递归删除
        if (this.leftNode != null) {
            this.leftNode.deleteNode(no);
        }
        //    如果递归删除左子树也没有成功删除，那么就递归删除右边子树
        if (this.rightNode != null) {
            this.rightNode.deleteNode(no);
        }
    }
}

顺序存储二叉树

顺序存储二叉树的概念

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，

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

顺序存储二叉树的特点:

顺序二叉树通常只考虑完全二叉树

第 n 个元素的左子节点为 2 * n + 1（计算公式）
第 n 个元素的右子节点为 2 * n + 2 （计算公式）
第 n 个元素的父节点为 (n-1) / 2
n : 表示二叉树中的第几个元素

顺序存储二叉树遍历

需求

给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。

前序遍历的结果应当为 1,2,4,5,3,6,7

编码思路

这里判断的思路首先是有一个数组转变成树看待的思想，

数组： 1,2,3,4,5,6,7

树（如下图）

第 n 个元素的左子节点为 2 * n + 1（计算公式）
第 n 个元素的右子节点为 2 * n + 2 （计算公式）

我们可以用这个公式来证明一下，数组转树的正确性

比如我们要计算二的位置，2是1的左子节点，1是下标为0的元素 2*0+1 套用公式 = 1，之后的节点同理

代码实现

package com.hyc.DataStructure.tree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree
 * @className: ArrayTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/4 19:07
 * @version: 1.0
 */
public class ArrayTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrayTree arrayTree = new ArrayTree(arr);
        //452 6731
        arrayTree.postOrder(0);
    }
}
class ArrayTree {
    private int[] arr;
    public ArrayTree(int[] arr) {
        this.arr = arr;
    }
    //    顺序存储树的前序遍历
    // 遍历公式 找到n的第n个左结点 n*2+1 找到n的第n个右节点 n*2+2
    // 输入参数 int index 为开始遍历到根节点 即为 数组下标0
    public void preOrder(int index) {
        //非空判断 避免空指针
        if (arr == null || arr.length == 0) {
            System.out.println("该树 为空 不能遍历");
        }
        //    前序遍历先输出自己
        System.out.println(arr[index]);
        //    之后递归遍历左结点
        //判断index 是否越界
        if ((2 * index + 1) < arr.length) {
            preOrder(index * 2 + 1);
        }
        //    之后递归遍历右边结点
        //判断index 是否越界
        if ((2 * index + 2) < arr.length) {
            preOrder(index * 2 + 2);
        }
    }
    public void infixOrder(int index) {
        //非空判断 避免空指针
        if (arr == null || arr.length == 0) {
            System.out.println("该树 为空 不能遍历");
        }
        //    递归遍历左结点
        //判断index 是否越界
        if ((2 * index + 1) < arr.length) {
            infixOrder(index * 2 + 1);
        }
        //    中序遍历输出自己
        System.out.println(arr[index]);
        //    递归遍历右边结点
        //判断index 是否越界
        if ((2 * index + 2) < arr.length) {
            infixOrder(index * 2 + 2);
        }
    }
    public void postOrder(int index) {
        //非空判断 避免空指针
        if (arr == null || arr.length == 0) {
            System.out.println("该树 为空 不能遍历");
        }
        //    递归遍历左结点
        //判断index 是否越界
        if ((2 * index + 1) < arr.length) {
            postOrder(index * 2 + 1);
        }
        //    递归遍历右边结点
        //判断index 是否越界
        if ((2 * index + 2) < arr.length) {
            postOrder(index * 2 + 2);
        }
        //    后序遍历输出自己
        System.out.println(arr[index]);
    }
}

这里我们先了解顺序存储二叉树，并且掌握他的节点计算思路和遍历思路，小冷之后的文章堆排序的时候会进行知识点的使用，提前预热

线索化二叉树

通过一个问题来引入线索化二叉树

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

问题分析:

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

线索二叉树基本介绍

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

线索二叉树应用案例

将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}

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

left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的

就是前驱节点.

right 指向的是右子树，也可能是指向后继节点，比如 ① 节点 right 指向的是右子树，而⑩ 节点的 right 指向的是后继节点.

代码实现

package com.hyc.DataStructure.tree.ThreadedBinaryTree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree.ThreadedBinaryTree
 * @className: ThreadedBinaryTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/5 16:38
 * @version: 1.0
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        //测试一把中序线索二叉树的功能
        heroNode root = new heroNode(1, "tom");
        heroNode node2 = new heroNode(3, "jack");
        heroNode node3 = new heroNode(6, "smith");
        heroNode node4 = new heroNode(8, "mary");
        heroNode node5 = new heroNode(10, "king");
        heroNode node6 = new heroNode(14, "dim");
        //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeftNode(node2);
        root.setRightNode(node3);
        node2.setLeftNode(node4);
        node2.setRightNode(node5);
        node3.setLeftNode(node6);
        //测试中序线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setHead(root);
        threadedBinaryTree.postThreadedNodes(root);
        //测试: 以10号节点测试
        heroNode leftNode = node5.getLeftNode();
        heroNode rightNode = node5.getRightNode();
        System.out.println("10号结点的前驱结点是 =" + leftNode); //3
        System.out.println("10号结点的后继结点是=" + rightNode); //1
        //当线索化二叉树后，能在使用原来的遍历方法
        //threadedBinaryTree.infixOrder();
        System.out.println("使用线索化的方式遍历 线索化二叉树");
        threadedBinaryTree.preThreaddeList(); // 8, 3, 10, 1, 14, 6
    }
}
class ThreadedBinaryTree {
    //确定根节点
    private heroNode head;
    //递归的时候用来存放上一个节点的变量用于线索化树的遍历和线索化节点
    private heroNode pre;
    public void setHead(heroNode head) {
        this.head = head;
    }
    //线索化遍历
    public void ThreaddeList() {
        //    这里我们需要一个变量，存储当前的节点
        heroNode tempNode = head;
        while (tempNode != null) {
            /* 开始循环遍历
             * 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点
             * 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了
             * 之后只需要处理线索化之后的有效节点即可
             * */
            while (tempNode.getLefttype() == 0) {
                tempNode = tempNode.getLeftNode();
            }
            //    因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了
            System.out.println(tempNode);
            /* 如果当前节点的右指针指向的是后继节点那么就一直输出
             * */
            while (tempNode.getRighttype() == 1) {
                tempNode = tempNode.getRightNode();
                System.out.println(tempNode);
            }
            // 替换这个遍历的节点
            tempNode = tempNode.getRightNode();
        }
    }
    public void preThreaddeList() {
        //    这里我们需要一个变量，存储当前的节点
        heroNode tempNode = head;
        while (tempNode != null) {
            /* 开始循环遍历
             * 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点
             * 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了
             * 之后只需要处理线索化之后的有效节点即可
             * */
            while (tempNode.getLefttype() == 0) {
                System.out.println(tempNode);
                tempNode = tempNode.getLeftNode();
            }
            //    因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了
            System.out.println(tempNode);
            // 替换这个遍历的节点
            tempNode = tempNode.getRightNode();
        }
    }
    //线索化节点
    public void ThreadedNodes(heroNode node) {
        //       非空判断
        if (node == null) {
            return;
        }
        //    线索化左子树
        ThreadedNodes(node.getLeftNode());
        //    线索化节点
        //不太好理解这里以 8 举例子
        // 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点
        if (node.getLeftNode() == null) {
            //如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点
            //以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1
            node.setLeftNode(pre);
            //    指向之后 将type改变为1
            node.setLefttype(1);
        }
        //处理后继节点
        //这里判断的前置节点非空并且前置节点没有后继结点
        if (pre != null && pre.getRightNode() == null) {
            //这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre  = 8这里指向的意思是 8 的rightnode为3
            pre.setRightNode(node);
            //此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点
            pre.setRighttype(1);
        }
        //每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中
        //否则会造成死递归
        pre = node;
        //    线索化右子树
        ThreadedNodes(node.getRightNode());
    }
    //线索化节点
    public void preThreadedNodes(heroNode node) {
        //       非空判断
        if (node == null) {
            return;
        }
        //    线索化节点
        //不太好理解这里以 8 举例子
        // 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点
        if (node.getLeftNode() == null) {
            //如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点
            //以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1
            node.setLeftNode(pre);
            //    指向之后 将type改变为1
            node.setLefttype(1);
        }
        //处理后继节点
        //这里判断的前置节点非空并且前置节点没有后继结点
        if (pre != null && pre.getRightNode() == null) {
            //这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre  = 8这里指向的意思是 8 的rightnode为3
            pre.setRightNode(node);
            //此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点
            pre.setRighttype(1);
        }
        //每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中
        //否则会造成死递归
        pre = node;
        if (node.getLefttype() == 0) {
            //    线索化左子树
            preThreadedNodes(node.getLeftNode());
        }
        if (node.getRighttype() == 0) {
            //    线索化右子树
            preThreadedNodes(node.getRightNode());
        }
    }
    //线索化节点
    public void postThreadedNodes(heroNode node) {
        //       非空判断
        if (node == null) {
            return;
        }
        //    线索化左子树
        ThreadedNodes(node.getLeftNode());
        //    线索化右子树
        ThreadedNodes(node.getRightNode());
        //    线索化节点
        //不太好理解这里以 8 举例子
        // 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点
        if (node.getLeftNode() == null) {
            //如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点
            //以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1
            node.setLeftNode(pre);
            //    指向之后 将type改变为1
            node.setLefttype(1);
        }
        //处理后继节点
        //这里判断的前置节点非空并且前置节点没有后继结点
        if (pre != null && pre.getRightNode() == null) {
            //这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre  = 8这里指向的意思是 8 的rightnode为3
            pre.setRightNode(node);
            //此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点
            pre.setRighttype(1);
        }
        //每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中
        //否则会造成死递归
        pre = node;
    }
    //   前序遍历
    public void preOrder() {
        if (this.head != null) {
            this.head.PreOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //中序遍历
    public void InfixOrder() {
        if (this.head != null) {
            this.head.infixOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //后续遍历
    public void PostOrder() {
        if (this.head != null) {
            this.head.postOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }
    //    删除节点
    public void deleteNode(int no) {
        if (head != null) {
            if (head.getId() == no) {
                head = null;
                return;
            } else {
                head.deleteNode(no);
            }
        } else {
            System.out.println("空树,无法删除");
        }
    }
}
class heroNode {
    private int id;
    private String name;
    private heroNode leftNode;
    private heroNode rightNode;
    //如果type 为 0 那么代表还有子树，如果type为1代表是前驱节点/后置节点
    private int lefttype;
    private int righttype;
    public int getLefttype() {
        return lefttype;
    }
    public void setLefttype(int lefttype) {
        this.lefttype = lefttype;
    }
    public int getRighttype() {
        return righttype;
    }
    public void setRighttype(int righttype) {
        this.righttype = righttype;
    }
    public heroNode getLeftNode() {
        return leftNode;
    }
    public void setLeftNode(heroNode leftNode) {
        this.leftNode = leftNode;
    }
    public heroNode getRightNode() {
        return rightNode;
    }
    public void setRightNode(heroNode rightNode) {
        this.rightNode = rightNode;
    }
    public heroNode(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;
    }
    @Override
    public String toString() {
        return "heroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    public void setName(String name) {
        this.name = name;
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.getLeftNode() != null) {
            this.leftNode.PreOrder();
        }
        if (this.getRightNode() != null) {
            this.rightNode.PreOrder();
        }
    }
    //    中序遍历
    public void infixOrder() {
        if (this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }
    //   后序遍历
    public void postOrder() {
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }
    //   前序查找
    public heroNode PreOrderSearch(int no) {
        System.out.println("前序查找");
        //比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.PreOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.PreOrderSearch(no);
        }
        return resNode;
    }
    //   中序查找
    public heroNode infixOrderSearch(int no) {
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.infixOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //比较当前节点的no 是不是我们要搜索的
        System.out.println("中序查找");
        if (this.id == no) {
            return this;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.infixOrderSearch(no);
        }
        return resNode;
    }
    //   后序查找
    public heroNode postOrderSearch(int no) {
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.postOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.postOrderSearch(no);
        }
        //如果不为null 那么代表右边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        System.out.println("后序查找");
        //左右子树，都没有找到，那么就比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        return resNode;
    }
    //    删除
    public void deleteNode(int no) {
        //    向左边遍历 如果左边子树有点话就将左边子树置空，如果不是就遍历右边
        if (this.leftNode != null && this.leftNode.id == no) {
            this.leftNode = null;
            return;
        }
        //    向右边遍历 如果右边子树有点话就将左边子树置空，如果左右都没有那么就绪要递归的删除
        if (this.rightNode != null && this.rightNode.id == no) {
            this.rightNode = null;
            return;
        }
        //    如果上面两步都不成功那么我们先向左边递归删除
        if (this.leftNode != null) {
            this.leftNode.deleteNode(no);
        }
        //    如果递归删除左子树也没有成功删除，那么就递归删除右边子树
        if (this.rightNode != null) {
            this.rightNode.deleteNode(no);
        }
    }
}

遍历线索化二叉树

说明：对前面的中序线索化的二叉树，进行遍历
分析：因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历
线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致。

public void preThreaddeList() {
        //    这里我们需要一个变量，存储当前的节点
        heroNode tempNode = head;
        while (tempNode != null) {
            /* 开始循环遍历
             * 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点
             * 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了
             * 之后只需要处理线索化之后的有效节点即可
             * */
            while (tempNode.getLefttype() == 0) {
                System.out.println(tempNode);
                tempNode = tempNode.getLeftNode();
            }
            //    因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了
            System.out.println(tempNode);
            // 替换这个遍历的节点
            tempNode = tempNode.getRightNode();
        }
    }

红黑树

是一种特殊的平衡二叉树

满足如下几个条件：

1、结点是红色或黑色的
2、根结点始终是黑色的
3、叶子结点也都是黑色的（当红色结点无左右孩子时，补足空结点是黑色的）
4、红色结点的子结点都是黑色的
5、对任一结点，到叶子结点的所有路径，都包含相同数目的黑色结点

特征：从根结点到叶子结点的最长路径，不会超过最短路径的两倍

当插入新结点使红黑树失去平衡时，通过两种方式恢复平衡：

旋转和变色（红变黑黑变红）

可视化网站

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

插入结点到红黑树的逻辑

约定新插入的结点都设为红色的，可以简化树的平衡过程

假设要插入的结点是X 父结点是P 祖父结点是G 叔父结点是U

1）X是根结点
放入根结点中，将颜色变为黑色

2）X的父结点是黑色的

3）X的父结点是红色的

a) 如果叔父结点U也是红色的，可以推断出祖父结点G必是黑色的

当增加新结点时造成两个红色结点相邻此时使用变色处理
P和U由从红色变为黑色 G由黑色变为红色如果G是根结点再次恢复为黑色

b) 如果叔父结点U是黑色的，并且X在左侧

以P为中心，向右旋转，G和U下移，此时如果P有右孩子，右孩子R移动到G的左孩子处
将P变为黑色将G变为红色

此为举例插入16的场景

c) 如果叔父结点U是黑色的，并且X在右侧

先通过左旋恢复成第二种情况然后再右旋和变色

以插入19举例

线段树

序列【1,4,2,3】

给序列的第i个数,加上X A[i]=A[I]+X O(1)
取序列的最大的数,遍历最大值 O(N)
遍历的时候时间复杂度高,怎么处理呢?

线段树Segment Tree

"区间" 线段树是根据区间的性质来构造的

特点:

每次将区间的长度一分为二,区间存储的左右边界 [[start,end]/[left,right]]

如果假设数组的长度 = n 线段树的高度就是 log(n)

将区间中的最大值加入进来,线段树加入值之后就是如下状态

除此之外,可以存储的区间内的最小值,区间求和等等

线段树的节点个数为 n+n/2+n/4... = (1+1/2+1/4...)*n ≈ 2n

构造线段树的时间复杂度和空间复杂度均为 O(n)

线段树创建代码实现

package com.hyc.DataStructure.SegmentTree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.SegmentTree
 * @className: SegmentTree
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/26 10:15
 * @version: 1.0
 */
public class SegmentTree {
    @Override
    public String toString() {
        return "SegmentTree{" +
                "start=" + start +
                ", end=" + end +
                ", val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 3};
        SegmentTree root = SegmentTree.build(arr);
        System.out.println(root);
    }
    //节点区间范围
    public int start, end;
    //    存储节点值
    public int val;
    //    左右子树
    public SegmentTree left;
    public SegmentTree right;
    public SegmentTree(int start, int end, int val) {
        this.start = start;
        this.end = end;
        this.val = val;
    }
    public static SegmentTree build(int[] A) {
        return buildByRecu(0, A.length - 1, A);
    }
    public static SegmentTree buildByRecu(int start, int end, int[] A) {
        if (start > end) {
            return null;
        }
        SegmentTree root = new SegmentTree(start, end, A[start]);
        //    如果是叶子节点 直接返回
        if (start == end) {
            return root;
        }
        //    如果不是那么就以二分的形式来递归创建树
        int mid = (start + end) / 2;
        root.left = buildByRecu(start, mid, A);
        root.right = buildByRecu(mid + 1, end, A);
        //求出区间内最大值为父节点的val
        root.val = Math.max(root.left.val, root.right.val);
        return root;
    }
}

单点更新

public static void modify(SegmentTree root, int index, int value) {
        //    先找到叶子节点,然后逐渐上层
        if (root.start == root.end && root.start == index) {
            root.val = value;
            return;
        }
        int mid = (root.start + root.end) / 2;
        //    判断index 在左子树的区间,还是 右子树的区间,二分思路
        if (index <= mid) {
            modify(root.left, index, value);
            root.val = Math.max(root.left.val, root.right.val);
            return;
        }
        modify(root.right, index, value);
        root.val = Math.max(root.left.val, root.right.val);
    }

搜索线段树

搜索线段树返回索引值

public static int searchByIndex(SegmentTree root, int index) {
        //    先找到叶子节点,然后逐渐上层
        if (root.start == root.end && root.start == index) {
            return root.val;
        }
        int mid = (root.start + root.end) / 2;
        //    判断index 在左子树的区间,还是 右子树的区间,二分思路
        if (index <= mid) {
            searchByIndex(root.left, index);
            return root.val;
        }
        searchByIndex(root.right, index);
        return root.val;
    }

树结构实际应用

堆排序

堆排序基本介绍

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

大顶堆

小顶堆

堆排序基本思想

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

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

堆排序步骤图解说明

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

假设给定无序序列结构如下
此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点
arr.length/2-1=5/2-1=1，也就是下面的 6 结点），从左至右，从下至上进行调整。

找到第二个非叶节点 4，由于[4,9,8]中 9 元素最大，4 和 9 交换。
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中 6 最大，交换 4 和 6。

此时，我们就将一个无序序列构造成了一个大顶堆。

步骤二将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换.

得到第二大元素。如此反复进行交换、重建、交换。

.将堆顶元素 9 和末尾元素 4 进行交换
重新调整结构，使其继续满足堆定义

再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

总结下堆排序的基本思路：

将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序.

代码实现

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

堆排序不是很好理解，老师通过 Debug 帮助大家理解堆排序
堆排序的速度非常快，在我的机器上 8 百万数据 3 秒左右。O(nlogn)

package com.hyc.DataStructure.tree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree
 * @className: HeapSort
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/6 23:52
 * @version: 1.0
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] test = new int[8000000];
        //测试数据
        for (int i = 0; i < 8000000; i++) {
            test[i] = (int) (Math.random() * 800000);
        }
        long time = System.currentTimeMillis();
        heapsort(test);
        long end = System.currentTimeMillis();
        long t = ((end - time) / 1000);
        System.out.println("一共用时 " + t + "秒");
        int arr[] = {4, 6, 8, 5, 9};
    }
    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 j = arr.length - 1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        //System.out.println("排序后的数组是 = " + Arrays.toString(arr));
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 大顶堆交换思路， 判断左右节点大小，之后判断左右节点的比对结果，与父节点判断，将最大值交还给父节点
     * @date: 2022/2/6 23:54
     * @param arr 存放需要将交换节点的数组
     * @param i   需要做调整的父节点索引
     * @param length 有多少节点需要调整
     * @return: void
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        //   开始调整
        /* 说明
         * k =i*2+1按照之前线索查找树的公式，找出左子树的节点位置
         * */
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            //判断条件 k（节点索引）首先不能大于我们要遍历的结点索引总数，之后判断左右节点的大小，交换
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            //找出最大的子节点，与父节点的值比对，
            if (arr[k] > temp) {
                //将较大的值放入到父节点
                arr[i] = arr[k];
                i = k; //i指向k ， 继续循环比较
            } else {
                break;
            }
        }
        //    for 循环结束之后 我们i已经是父节点以及最大值的索引了
        // 将 temp 调整到最后免得位置
        arr[i] = temp;
    }
}

赫夫曼树

基本介绍

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

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

路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L-1
结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积
树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL(weighted path

length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。

WPL 最小的就是赫夫曼树

赫夫曼树创建思路图解

给你一个数列 {13, 7, 8, 3, 29, 6, 1}，要求转成一颗赫夫曼树.

构成赫夫曼树的步骤：

从小到大进行排序, 将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树
取出根节点权值最小的两颗二叉树
组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复 1-2-3-4 的步骤，直到数列中，所有的数

据都被处理，就得到一颗赫夫曼树

赫夫曼树的代码实现

package com.hyc.DataStructure.HuffmanTree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.HuffmanTreeDemo
 * @className: HuffmanTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/8 0:21
 * @version: 1.0
 */
public class HuffmanTreeDemo {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node manTree = createHuffManTree(arr);
        //    测试
        preOrder(manTree);
    }
    //编写一个前序遍历的方法
    public static void preOrder(Node root) {
        if (root != null) {
            root.PreOrder();
        } else {
            System.out.println("空树无法遍历");
        }
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * @date: 2022/2/8 0:42
     * @param arr 需要创建赫夫曼树的数组
     * @return: com.hyc.DataStructure.HuffmanTree.Node 返回已经创建好的赫夫曼树的根节点
     */
    public static Node createHuffManTree(int[] arr) {
        List<Node> nodes = new ArrayList<>();
        //（1）为了方便操作 我们先遍历数组生成对应节点 放入 arrayList
        for (int value : arr) {
            nodes.add(new Node(value));
        }
        //循环处理
        while (nodes.size() > 1) {
            //    先用接口的sort 排序
            Collections.sort(nodes);
            System.out.println("nodes = " + nodes);
            //   （2） 取出根节点权值最小的两颗二叉树
            //    取出权值最小的结点
            Node leftnode = nodes.get(0);
            //取出根节点第二最小的二叉树
            Node rightnode = nodes.get(1);
            // （3） 构建出一颗新的二叉树
            Node parent = new Node(leftnode.value + rightnode.value);
            parent.left = leftnode;
            parent.right = rightnode;
            //    (4)从 ArrayList删除处理过的二叉树
            nodes.remove(leftnode);
            nodes.remove(rightnode);
            //    (5)将parent加入到 nodes
            nodes.add(parent);
        }
        //    返回赫夫曼树的root节点
        return nodes.get(0);
    }
}
/* 为了Node对象排序，我们实现collections集合排序
 * 这里我们实现 compareble
 * */
class Node implements Comparable<Node> {
    //赫夫曼树 权重值
    int value;
    Node left;
    Node right;
    //    构造方法 创建节点的时候只需要有权重值就可以了
    public Node(int value) {
        this.value = value;
    }
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    @Override
    public int compareTo(Node o) {
        //这里我们按照权重从小到大排序
        //从大到小只需要置负 -(this.value - o.value)
        return this.value - o.value;
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.PreOrder();
        }
        if (this.right != null) {
            this.right.PreOrder();
        }
    }
}

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

algorithm--这个是算法的英文单词（三）

快速排序案例

快速排序测速

归并排序

基本思想:

合并相邻有序子序列

动态图

思路实现

速度测试

基数排序

基数排序(桶排序)介绍

基数排序基本思想

动图演示

代码思路实验

速度测试

基数排序的说明:

哈希表

哈希表的基本介绍

google 上机题

思路分析并画出示意图

思路实现

效果演示

新增与遍历

查找

树的结构学习

二叉树简介

数组

链表

二叉树

认识树结构

二叉树遍历的说明

二叉树遍历应用实例(前序,中序,后序)

二叉树遍历代码实例

二叉树查找思路

二叉树查找代码示例

二叉树-删除节点

有关二叉树的，遍历，查找，删除的全代码

顺序存储二叉树

顺序存储二叉树的概念

顺序存储二叉树的特点:

顺序存储二叉树遍历

代码实现

线索化二叉树

线索二叉树基本介绍

线索二叉树应用案例

代码实现

遍历线索化二叉树

红黑树

线段树

线段树创建代码实现

单点更新

搜索线段树

树结构实际应用

堆排序

堆排序基本介绍

大顶堆

小顶堆

堆排序基本思想

堆排序步骤图解说明

总结下堆排序的基本思路：

代码实现

赫夫曼树

基本介绍

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

赫夫曼树创建思路图解

赫夫曼树的代码实现