5 排序
排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程
基本介绍：
常见排序：
5.1 冒泡排序
思路：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部
// 将前面额冒泡排序算法，封装成一个方法 public static void bubbleSort(int[] arr) { // 冒泡排序 的时间复杂度 O(n^2), 自己写出 int temp = 0; // 临时变量 boolean flag = false; // 标识变量，表示是否进行过交换 for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { // 如果前面的数比后面的数大，则交换 if (arr[j] > arr[j + 1]) { flag = true; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } //System.out.println("第" + (i + 1) + "趟排序后的数组"); //System.out.println(Arrays.toString(arr)); if (!flag) { // 在一趟排序中，一次交换都没有发生过 break; } else { flag = false; // 重置flag!!!, 进行下次判断 } } }
5.2 选择排序
思路：
第一次从arr[0]~arr[n-1]中选取最小值，与 arr[0]交换，
第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换，
第三次从 arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…
第 i 次从 arr[i-1]~arr[n-1]中选取最小值，与 arr[i-1]交换，…,
第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值，与 arr[n-2]交换，总
共通过 n-1 次，得到一个按排序码从小到大排列的有序序列
//选择排序 public static void selectSort(int[] arr) { //在推导的过程，我们发现了规律，因此，可以使用for来解决 //选择排序时间复杂度是 O(n^2) for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; int min = arr[i]; for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) { // 说明假定的最小值，并不是最小 min = arr[j]; // 重置min minIndex = j; // 重置minIndex } } // 将最小值，放在arr[0], 即交换 if (minIndex != i) { arr[minIndex] = arr[i]; arr[i] = min; } //System.out.println("第"+(i+1)+"轮后~~"); //System.out.println(Arrays.toString(arr));// 1, 34, 119, 101 }
5.3 插入排序
思路：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表
//插入排序 public static void insertSort(int[] arr) { int insertVal = 0; int insertIndex = 0; //使用for循环来把代码简化 for(int i = 1; i < arr.length; i++) { //定义待插入的数 insertVal = arr[i]; insertIndex = i - 1; // 即arr[1]的前面这个数的下标 // 给insertVal 找到插入的位置 // 说明 // 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界 // 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置 // 3. 就需要将 arr[insertIndex] 后移 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex] insertIndex--; } // 当退出while循环时，说明插入的位置找到, insertIndex + 1 // 举例：理解不了，我们一会 debug //这里我们判断是否需要赋值 if(insertIndex + 1 != i) { arr[insertIndex + 1] = insertVal; } //System.out.println("第"+i+"轮插入"); //System.out.println(Arrays.toString(arr)); }
5.4 希尔排序
思路：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1
// 希尔排序时， 对有序序列在插入时采用交换法, // 思路(算法) ===> 代码 public static void shellSort(int[] arr) { int temp = 0; int count = 0; // 根据前面的逐步分析，使用循环处理 for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { // 遍历各组中所有的元素(共gap组，每组有个元素), 步长gap for (int j = i - gap; j >= 0; j -= gap) { // 如果当前元素大于加上步长后的那个元素，说明交换 if (arr[j] > arr[j + gap]) { temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } //System.out.println("希尔排序第" + (++count) + "轮 =" + Arrays.toString(arr)); } } //对交换式的希尔排序进行优化->移位法 public static void shellSort2(int[] arr) { // 增量gap, 并逐步的缩小增量 for (int gap = arr.length / 2; gap > 0; gap /= 2) { // 从第gap个元素，逐个对其所在的组进行直接插入排序 for (int i = gap; i < arr.length; i++) { int j = i; int temp = arr[j]; if (arr[j] < arr[j - gap]) { while (j - gap >= 0 && temp < arr[j - gap]) { //移动 arr[j] = arr[j-gap]; j -= gap; } //当退出while后，就给temp找到插入的位置 arr[j] = temp; } } } }
5.5 快速排序
思路：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
public static void quickSort(int[] arr,int left, int right) { 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); } }
5.6 归并排序
//分+合方法 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; } }
5.7 基数排序
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)); }
5.8 堆排序
public class HeapSort { public static void main(String[] args) { //要求将数组进行升序排序 //int arr[] = {4, 6, 8, 5, 9}; // 创建要给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); heapSort(arr); Date data2 = new Date(); String date2Str = simpleDateFormat.format(data2); System.out.println("排序前的时间是=" + date2Str); //System.out.println("排序后=" + Arrays.toString(arr)); } //编写一个堆排序的方法 public static void heapSort(int arr[]) { int temp = 0; System.out.println("堆排序!!"); // //分步完成 // adjustHeap(arr, 1, arr.length); // System.out.println("第一次" + Arrays.toString(arr)); // 4, 9, 8, 5, 6 // // adjustHeap(arr, 0, arr.length); // System.out.println("第2次" + Arrays.toString(arr)); // 9,6,8,5,4 //完成我们最终代码 //将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆 for(int i = arr.length / 2 -1; i >=0; i--) { adjustHeap(arr, i, arr.length); } /* * 2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端; 3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。 */ 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)); } //将一个数组(二叉树), 调整成一个大顶堆 /** * 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆 * 举例 int arr[] = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => 得到 {4, 9, 8, 5, 6} * 如果我们再次调用 adjustHeap 传入的是 i = 0 => 得到 {4, 9, 8, 5, 6} => {9,6,8,5, 4} * @param arr 待调整的数组 * @param i 表示非叶子结点在数组中索引 * @param lenght 表示对多少个元素继续调整， length 是在逐渐的减少 */ public static void adjustHeap(int arr[], int i, int lenght) { int temp = arr[i];//先取出当前元素的值，保存在临时变量 //开始调整 //说明 //1. k = i * 2 + 1 k 是 i结点的左子结点 for(int k = i * 2 + 1; k < lenght; k = k * 2 + 1) { if(k+1 < lenght && arr[k] < arr[k+1]) { //说明左子结点的值小于右子结点的值 k++; // k 指向右子结点 } if(arr[k] > temp) { //如果子结点大于父结点 arr[i] = arr[k]; //把较大的值赋给当前结点 i = k; //!!! i 指向 k,继续循环比较 } else { break;//! } } //当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部) arr[i] = temp;//将temp值放到调整后的位置 } }
6 查找
6.1 二分查找
public static int binarySearch(int[] arr, int left, int right, int findVal) { // 当 left > right 时，说明递归整个数组，但是没有找到 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; } } //完成一个课后思考题: /* * 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中， * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000 * * 思路分析 * 1. 在找到mid 索引值，不要马上返回 * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList * 4. 将Arraylist返回 */ public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) { System.out.println("hello~"); // 当 left > right 时，说明递归整个数组，但是没有找到 if (left > right) { return new ArrayList<Integer>(); } int mid = (left + right) / 2; int midVal = arr[mid]; if (findVal > midVal) { // 向 右递归 return binarySearch2(arr, mid + 1, right, findVal); } else if (findVal < midVal) { // 向左递归 return binarySearch2(arr, left, mid - 1, findVal); } else { // * 思路分析 // * 1. 在找到mid 索引值，不要马上返回 // * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList // * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList // * 4. 将Arraylist返回 List<Integer> resIndexlist = new ArrayList<Integer>(); //向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList int temp = mid - 1; while(true) { if (temp < 0 || arr[temp] != findVal) {//退出 break; } //否则，就temp 放入到 resIndexlist resIndexlist.add(temp); temp -= 1; //temp左移 } resIndexlist.add(mid); // //向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList temp = mid + 1; while(true) { if (temp > arr.length - 1 || arr[temp] != findVal) {//退出 break; } //否则，就temp 放入到 resIndexlist resIndexlist.add(temp); temp += 1; //temp右移 } return resIndexlist; } }
6.2 插值查找
public static int insertValueSearch(int[] arr, int left, int right, int findVal) { System.out.println("插值查找次数~~"); //注意：findVal < arr[0] 和 findVal > arr[arr.length - 1] 必须需要 //否则我们得到的 mid 可能越界 if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) { return -1; } // 求出mid, 自适应 int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]); int midVal = arr[mid]; if (findVal > midVal) { // 说明应该向右边递归 return insertValueSearch(arr, mid + 1, right, findVal); } else if (findVal < midVal) { // 说明向左递归查找 return insertValueSearch(arr, left, mid - 1, findVal); } else { return mid; } }
6.3 斐波那契查找
//因为后面我们mid=low+F(k-1)-1，需要使用到斐波那契数列，因此我们需要先获取到一个斐波那契数列 //非递归方法得到一个斐波那契数列 public static int[] fib() { int[] f = new int[maxSize]; f[0] = 1; f[1] = 1; for (int i = 2; i < maxSize; i++) { f[i] = f[i - 1] + f[i - 2]; } return f; } //编写斐波那契查找算法 //使用非递归的方式编写算法 /** * * @param a 数组 * @param key 我们需要查找的关键码(值) * @return 返回对应的下标，如果没有-1 */ public static int fibSearch(int[] a, int key) { 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] 值 可能大于 a 的 长度，因此我们需要使用Arrays类，构造一个新的数组，并指向temp[] //不足的部分会使用0填充 int[] temp = Arrays.copyOf(a, f[k]); //实际上需求使用a数组最后的数填充 temp //举例: //temp = {1,8, 10, 89, 1000, 1234, 0, 0} => {1,8, 10, 89, 1000, 1234, 1234, 1234,} for(int i = high + 1; i < temp.length; i++) { temp[i] = a[high]; } // 使用while来循环处理，找到我们的数 key while (low <= high) { // 只要这个条件满足，就可以找 mid = low + f[k - 1] - 1; if(key < temp[mid]) { //我们应该继续向数组的前面查找(左边) high = mid - 1; //为甚是 k-- //说明 //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-- //即下次循环 mid = f[k-1-1]-1 k--; } else if ( key > temp[mid]) { // 我们应该继续向数组的后面查找(右边) low = mid + 1; //为什么是k -=2 //说明 //1. 全部元素 = 前面的元素 + 后边元素 //2. f[k] = f[k-1] + f[k-2] //3. 因为后面我们有f[k-2] 所以可以继续拆分 f[k-1] = f[k-3] + f[k-4] //4. 即在f[k-2] 的前面进行查找 k -=2 //5. 即下次循环 mid = f[k - 1 - 2] - 1 k -= 2; } else { //找到 //需要确定，返回的是哪个下标 if(mid <= high) { return mid; } else { return high; } } } return -1; }
7 哈希表
- 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表
基本介绍：
google上机题：
public class HashTabDemo { public static void main(String[] args) { //创建哈希表 HashTab hashTab = new HashTab(7); //写一个简单的菜单 String key = ""; Scanner scanner = new Scanner(System.in); while (true) { System.out.println("add: 添加雇员"); System.out.println("list: 显示雇员"); System.out.println("find: 查找雇员"); System.out.println("exit: 退出系统"); key = scanner.next(); switch (key) { case "add": System.out.println("输入id"); int id = scanner.nextInt(); System.out.println("输入名字"); String name = scanner.next(); //创建 雇员 Emp emp = new Emp(id, name); hashTab.add(emp); break; case "list": hashTab.list(); break; case "find": System.out.println("请输入要查找的id"); id = scanner.nextInt(); hashTab.findEmpById(id); break; case "exit": scanner.close(); System.exit(0); default: break; } } } } //创建HashTab 管理多条链表 class HashTab { private EmpLinkedList[] empLinkedListArray; private int size; //表示有多少条链表 //构造器 public HashTab(int size) { this.size = size; //初始化empLinkedListArray empLinkedListArray = new EmpLinkedList[size]; //？留一个坑, 这时不要分别初始化每个链表 for (int i = 0; i < size; i++) { empLinkedListArray[i] = new EmpLinkedList(); } } //添加雇员 public void add(Emp emp) { //根据员工的id ,得到该员工应当添加到哪条链表 int empLinkedListNO = hashFun(emp.id); //将emp 添加到对应的链表中 empLinkedListArray[empLinkedListNO].add(emp); } //遍历所有的链表,遍历hashtab public void list() { for (int i = 0; i < size; i++) { empLinkedListArray[i].list(i); } } //根据输入的id,查找雇员 public void findEmpById(int id) { //使用散列函数确定到哪条链表查找 int empLinkedListNO = hashFun(id); Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id); if (emp != null) {//找到 System.out.printf("在第%d条链表中找到 雇员 id = %d\n", (empLinkedListNO + 1), id); } else { System.out.println("在哈希表中，没有找到该雇员~"); } } //编写散列函数, 使用一个简单取模法 public int hashFun(int id) { return id % size; } } //表示一个雇员 class Emp { public int id; public String name; public Emp next; //next 默认为 null public Emp(int id, String name) { super(); this.id = id; this.name = name; } } //创建EmpLinkedList ,表示链表 class EmpLinkedList { //头指针，执行第一个Emp,因此我们这个链表的head 是直接指向第一个Emp private Emp head; //默认null //添加雇员到链表 //说明 //1. 假定，当添加雇员时，id 是自增长，即id的分配总是从小到大 // 因此我们将该雇员直接加入到本链表的最后即可 public void add(Emp emp) { //如果是添加第一个雇员 if (head == null) { head = emp; return; } //如果不是第一个雇员，则使用一个辅助的指针，帮助定位到最后 Emp curEmp = head; while (true) { if (curEmp.next == null) {//说明到链表最后 break; } curEmp = curEmp.next; //后移 } //退出时直接将emp 加入链表 curEmp.next = emp; } //遍历链表的雇员信息 public void list(int no) { if (head == null) { //说明链表为空 System.out.println("第 " + (no + 1) + " 链表为空"); return; } System.out.print("第 " + (no + 1) + " 链表的信息为"); Emp curEmp = head; //辅助指针 while (true) { System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name); if (curEmp.next == null) {//说明curEmp已经是最后结点 break; } curEmp = curEmp.next; //后移，遍历 } System.out.println(); } //根据id查找雇员 //如果查找到，就返回Emp, 如果没有找到，就返回null public Emp findEmpById(int id) { //判断链表是否为空 if (head == null) { System.out.println("链表为空"); return null; } //辅助指针 Emp curEmp = head; while (true) { if (curEmp.id == id) {//找到 break;//这时curEmp就指向要查找的雇员 } //退出 if (curEmp.next == null) {//说明遍历当前链表没有找到该雇员 curEmp = null; break; } curEmp = curEmp.next;//以后 } return curEmp; } }
8 树(基础)
基本介绍：
8.1 二叉树
基础介绍：
- 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
- 二叉树的子节点分为左节点和右节点
- 如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树
- 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树
遍历：
- 前序遍历: 先输出父节点，再遍历左子树和右子树
- 中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
- 后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
public class BinaryTreeDemo { public static void main(String[] args) { //先需要创建一颗二叉树 BinaryTree binaryTree = new BinaryTree(); //创建需要的结点 HeroNode root = new HeroNode(1, "宋江"); HeroNode node2 = new HeroNode(2, "吴用"); HeroNode node3 = new HeroNode(3, "卢俊义"); HeroNode node4 = new HeroNode(4, "林冲"); HeroNode node5 = new HeroNode(5, "关胜"); //说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树 root.setLeft(node2); root.setRight(node3); node3.setRight(node4); node3.setLeft(node5); binaryTree.setRoot(root); //测试 // System.out.println("前序遍历"); // 1,2,3,5,4 // binaryTree.preOrder(); //测试 // System.out.println("中序遍历"); // binaryTree.infixOrder(); // 2,1,5,3,4 // // System.out.println("后序遍历"); // binaryTree.postOrder(); // 2,5,4,3,1 //前序遍历 //前序遍历的次数 ：4 // System.out.println("前序遍历方式~~~"); // HeroNode resNode = binaryTree.preOrderSearch(5); // if (resNode != null) { // System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName()); // } else { // System.out.printf("没有找到 no = %d 的英雄", 5); // } //中序遍历查找 //中序遍历3次 // System.out.println("中序遍历方式~~~"); // HeroNode resNode = binaryTree.infixOrderSearch(5); // if (resNode != null) { // System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName()); // } else { // System.out.printf("没有找到 no = %d 的英雄", 5); // } //后序遍历查找 //后序遍历查找的次数 2次 // System.out.println("后序遍历方式~~~"); // HeroNode resNode = binaryTree.postOrderSearch(5); // if (resNode != null) { // System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName()); // } else { // System.out.printf("没有找到 no = %d 的英雄", 5); // } //测试一把删除结点 System.out.println("删除前,前序遍历"); binaryTree.preOrder(); // 1,2,3,5,4 binaryTree.delNode(5); //binaryTree.delNode(3); System.out.println("删除后，前序遍历"); binaryTree.preOrder(); // 1,2,3,4 } } //定义BinaryTree 二叉树 class BinaryTree { private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } //删除结点 public void delNode(int no) { if (root != null) { //如果只有一个root结点, 这里立即判断root是不是就是要删除结点 if (root.getNo() == no) { root = null; } else { //递归删除 root.delNode(no); } } else { System.out.println("空树，不能删除~"); } } //前序遍历 public void preOrder() { if (this.root != null) { this.root.preOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } //中序遍历 public void infixOrder() { if (this.root != null) { this.root.infixOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } //后序遍历 public void postOrder() { if (this.root != null) { this.root.postOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } //前序遍历 public HeroNode preOrderSearch(int no) { if (root != null) { return root.preOrderSearch(no); } else { return null; } } //中序遍历 public HeroNode infixOrderSearch(int no) { if (root != null) { return root.infixOrderSearch(no); } else { return null; } } //后序遍历 public HeroNode postOrderSearch(int no) { if (root != null) { return this.root.postOrderSearch(no); } else { return null; } } } //先创建HeroNode 结点 class HeroNode { private int no; private String name; private HeroNode left; //默认null private HeroNode right; //默认null public HeroNode(int no, String name) { this.no = no; this.name = name; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } public HeroNode getLeft() { return left; } public void setLeft(HeroNode left) { this.left = left; } public HeroNode getRight() { return right; } public void setRight(HeroNode right) { this.right = right; } @Override public String toString() { return "HeroNode [no=" + no + ", name=" + name + "]"; } //递归删除结点 //1.如果删除的节点是叶子节点，则删除该节点 //2.如果删除的节点是非叶子节点，则删除该子树 public void delNode(int no) { //思路 /* * 1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点. 2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除) 3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除) 4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除 5. 如果第4步也没有删除结点，则应当向右子树进行递归删除. */ //2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除) if (this.left != null && this.left.no == no) { this.left = null; return; } //3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除) if (this.right != null && this.right.no == no) { this.right = null; return; } //4.我们就需要向左子树进行递归删除 if (this.left != null) { this.left.delNode(no); } //5.则应当向右子树进行递归删除 if (this.right != null) { this.right.delNode(no); } } //编写前序遍历的方法 public void preOrder() { System.out.println(this); //先输出父结点 //递归向左子树前序遍历 if (this.left != null) { this.left.preOrder(); } //递归向右子树前序遍历 if (this.right != null) { this.right.preOrder(); } } //中序遍历 public void infixOrder() { //递归向左子树中序遍历 if (this.left != null) { this.left.infixOrder(); } //输出父结点 System.out.println(this); //递归向右子树中序遍历 if (this.right != null) { this.right.infixOrder(); } } //后序遍历 public void postOrder() { if (this.left != null) { this.left.postOrder(); } if (this.right != null) { this.right.postOrder(); } System.out.println(this); } //前序遍历查找 /** * @param no 查找no * @return 如果找到就返回该Node ,如果没有找到返回 null */ public HeroNode preOrderSearch(int no) { System.out.println("进入前序遍历"); //比较当前结点是不是 if (this.no == no) { return this; } //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找 //2.如果左递归前序查找，找到结点，则返回 HeroNode resNode = null; if (this.left != null) { resNode = this.left.preOrderSearch(no); } if (resNode != null) {//说明我们左子树找到 return resNode; } //1.左递归前序查找，找到结点，则返回，否继续判断， //2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找 if (this.right != null) { resNode = this.right.preOrderSearch(no); } return resNode; } //中序遍历查找 public HeroNode infixOrderSearch(int no) { //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找 HeroNode resNode = null; if (this.left != null) { resNode = this.left.infixOrderSearch(no); } if (resNode != null) { return resNode; } System.out.println("进入中序查找"); //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点 if (this.no == no) { return this; } //否则继续进行右递归的中序查找 if (this.right != null) { resNode = this.right.infixOrderSearch(no); } return resNode; } //后序遍历查找 public HeroNode postOrderSearch(int no) { //判断当前结点的左子节点是否为空，如果不为空，则递归后序查找 HeroNode resNode = null; if (this.left != null) { resNode = this.left.postOrderSearch(no); } if (resNode != null) {//说明在左子树找到 return resNode; } //如果左子树没有找到，则向右子树递归进行后序遍历查找 if (this.right != null) { resNode = this.right.postOrderSearch(no); } if (resNode != null) { return resNode; } System.out.println("进入后序查找"); //如果左右子树都没有找到，就比较当前结点是不是 if (this.no == no) { return this; } return resNode; } }
8.2 顺序存储二叉树：
- 顺序二叉树通常只考虑完全二叉树
- 第 n 个元素的左子节点为 2 * n + 1
- 第 n 个元素的右子节点为 2 * n + 2
- 第 n 个元素的父节点为 (n-1) / 2
- n : 表示二叉树中的第几个元素(按
public class ArrBinaryTreeDemo { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5, 6, 7}; //创建一个 ArrBinaryTree ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr); arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7 } } //编写一个ArrayBinaryTree, 实现顺序存储二叉树遍历 class ArrBinaryTree { private int[] arr;//存储数据结点的数组 public ArrBinaryTree(int[] arr) { this.arr = arr; } //重载preOrder public void preOrder() { this.preOrder(0); } //编写一个方法，完成顺序存储二叉树的前序遍历 /** * @param index 数组的下标 */ public void preOrder(int index) { //如果数组为空，或者 arr.length = 0 if (arr == null || arr.length == 0) { System.out.println("数组为空，不能按照二叉树的前序遍历"); } //输出当前这个元素 System.out.println(arr[index]); //向左递归遍历 if ((index * 2 + 1) < arr.length) { preOrder(2 * index + 1); } //向右递归遍历 if ((index * 2 + 2) < arr.length) { preOrder(2 * index + 2); } } }
8.3 线索化二叉树：
- n 个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
- 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
- 一个结点的前一个结点，称为前驱结点
- 一个结点的后一个结点，称为后继结点
package com.atguigu.tree.threadedbinarytree; import java.util.concurrent.SynchronousQueue; 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.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); //测试中序线索化 ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree(); threadedBinaryTree.setRoot(root); threadedBinaryTree.threadedNodes(); //测试: 以10号节点测试 HeroNode leftNode = node5.getLeft(); HeroNode rightNode = node5.getRight(); System.out.println("10号结点的前驱结点是 =" + leftNode); //3 System.out.println("10号结点的后继结点是=" + rightNode); //1 //当线索化二叉树后，能在使用原来的遍历方法 //threadedBinaryTree.infixOrder(); System.out.println("使用线索化的方式遍历 线索化二叉树"); threadedBinaryTree.threadedList(); // 8, 3, 10, 1, 14, 6 } } //定义ThreadedBinaryTree 实现了线索化功能的二叉树 class ThreadedBinaryTree { private HeroNode root; //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针 //在递归进行线索化时，pre 总是保留前一个结点 private HeroNode pre = null; public void setRoot(HeroNode root) { this.root = root; } //重载一把threadedNodes方法 public void threadedNodes() { this.threadedNodes(root); } //遍历线索化二叉树的方法 public void threadedList() { //定义一个变量，存储当前遍历的结点，从root开始 HeroNode node = root; while (node != null) { //循环的找到leftType == 1的结点，第一个找到就是8结点 //后面随着遍历而变化,因为当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(); } } //编写对二叉树进行中序线索化的方法 /** * @param node 就是当前需要线索化的结点 */ public void threadedNodes(HeroNode node) { //如果node==null, 不能线索化 if (node == null) { return; } //(一)先线索化左子树 threadedNodes(node.getLeft()); //(二)线索化当前结点[有难度] //处理当前结点的前驱结点 //以8结点来理解 //8结点的.left = null , 8结点的.leftType = 1 if (node.getLeft() == null) { //让当前结点的左指针指向前驱结点 node.setLeft(pre); //修改当前结点的左指针的类型,指向前驱结点 node.setLeftType(1); } //处理后继结点 if (pre != null && pre.getRight() == null) { //让前驱结点的右指针指向当前结点 pre.setRight(node); //修改前驱结点的右指针类型 pre.setRightType(1); } //!!! 每处理一个结点后，让当前结点是下一个结点的前驱结点 pre = node; //(三)在线索化右子树 threadedNodes(node.getRight()); } //删除结点 public void delNode(int no) { if (root != null) { //如果只有一个root结点, 这里立即判断root是不是就是要删除结点 if (root.getNo() == no) { root = null; } else { //递归删除 root.delNode(no); } } else { System.out.println("空树，不能删除~"); } } //前序遍历 public void preOrder() { if (this.root != null) { this.root.preOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } //中序遍历 public void infixOrder() { if (this.root != null) { this.root.infixOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } //后序遍历 public void postOrder() { if (this.root != null) { this.root.postOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } //前序遍历 public HeroNode preOrderSearch(int no) { if (root != null) { return root.preOrderSearch(no); } else { return null; } } //中序遍历 public HeroNode infixOrderSearch(int no) { if (root != null) { return root.infixOrderSearch(no); } else { return null; } } //后序遍历 public HeroNode postOrderSearch(int no) { if (root != null) { return this.root.postOrderSearch(no); } else { return null; } } } //先创建HeroNode 结点 class HeroNode { private int no; private String name; private HeroNode left; //默认null private HeroNode right; //默认null //说明 //1. 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点 //2. 如果rightType == 0 表示指向是右子树, 如果 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(int no, String name) { this.no = no; this.name = name; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } public HeroNode getLeft() { return left; } public void setLeft(HeroNode left) { this.left = left; } public HeroNode getRight() { return right; } public void setRight(HeroNode right) { this.right = right; } @Override public String toString() { return "HeroNode [no=" + no + ", name=" + name + "]"; } //递归删除结点 //1.如果删除的节点是叶子节点，则删除该节点 //2.如果删除的节点是非叶子节点，则删除该子树 public void delNode(int no) { //思路 /* * 1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点. 2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除) 3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除) 4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除 5. 如果第4步也没有删除结点，则应当向右子树进行递归删除. */ //2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除) if (this.left != null && this.left.no == no) { this.left = null; return; } //3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除) if (this.right != null && this.right.no == no) { this.right = null; return; } //4.我们就需要向左子树进行递归删除 if (this.left != null) { this.left.delNode(no); } //5.则应当向右子树进行递归删除 if (this.right != null) { this.right.delNode(no); } } //编写前序遍历的方法 public void preOrder() { System.out.println(this); //先输出父结点 //递归向左子树前序遍历 if (this.left != null) { this.left.preOrder(); } //递归向右子树前序遍历 if (this.right != null) { this.right.preOrder(); } } //中序遍历 public void infixOrder() { //递归向左子树中序遍历 if (this.left != null) { this.left.infixOrder(); } //输出父结点 System.out.println(this); //递归向右子树中序遍历 if (this.right != null) { this.right.infixOrder(); } } //后序遍历 public void postOrder() { if (this.left != null) { this.left.postOrder(); } if (this.right != null) { this.right.postOrder(); } System.out.println(this); } //前序遍历查找 /** * @param no 查找no * @return 如果找到就返回该Node ,如果没有找到返回 null */ public HeroNode preOrderSearch(int no) { System.out.println("进入前序遍历"); //比较当前结点是不是 if (this.no == no) { return this; } //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找 //2.如果左递归前序查找，找到结点，则返回 HeroNode resNode = null; if (this.left != null) { resNode = this.left.preOrderSearch(no); } if (resNode != null) {//说明我们左子树找到 return resNode; } //1.左递归前序查找，找到结点，则返回，否继续判断， //2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找 if (this.right != null) { resNode = this.right.preOrderSearch(no); } return resNode; } //中序遍历查找 public HeroNode infixOrderSearch(int no) { //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找 HeroNode resNode = null; if (this.left != null) { resNode = this.left.infixOrderSearch(no); } if (resNode != null) { return resNode; } System.out.println("进入中序查找"); //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点 if (this.no == no) { return this; } //否则继续进行右递归的中序查找 if (this.right != null) { resNode = this.right.infixOrderSearch(no); } return resNode; } //后序遍历查找 public HeroNode postOrderSearch(int no) { //判断当前结点的左子节点是否为空，如果不为空，则递归后序查找 HeroNode resNode = null; if (this.left != null) { resNode = this.left.postOrderSearch(no); } if (resNode != null) {//说明在左子树找到 return resNode; } //如果左子树没有找到，则向右子树递归进行后序遍历查找 if (this.right != null) { resNode = this.right.postOrderSearch(no); } if (resNode != null) { return resNode; } System.out.println("进入后序查找"); //如果左右子树都没有找到，就比较当前结点是不是 if (this.no == no) { return this; } return resNode; } }
