Qz学算法-数据结构篇(树结构实际应用)

　　堆排序1.基本介绍堆排序是一种利用堆数据结构设计的排序算法。堆排序是一种选择排序。它是最坏、最好的。平均时间复杂度为O(nlogn),也是排序不稳定。 堆是一种完全的二叉树，具有以下性质：每个结点的值大于或等于儿童结点的值，称为大顶堆。请注意，左儿童的值与右儿童的值之间没有关系。 每个结点的值小于或等于其左右子节点的值，称为小顶堆 大顶堆的例子说明

　　我们按层编号堆中的结点，映射到数组中就是这样:

　　大顶堆的特点：arr[i]>=arr[2*i+1]&&arr[i]>=arr[2*+2]

　　//i对应第几个节点，i从0开始编号

　　5.小顶堆的例子说明

　　小顶堆：arr[i]<=arr[2*i+1]&&arr[i]<=arr[2*i+2]

　　//i对应第几个节点，i从0开始编号

　　6.一般升序采用大顶堆，降序采用小顶堆2.基本思想

　　1)将待排序列构建成堆

　　2)此时，整个序列的最大值是堆顶的根节点。

　　3)与末尾元素交换，此时末尾为最大值。

　　4)然后将剩余-1个元素重建成一堆，从而获得n个元素的次小值。这样反复执行，就可以得到一个有序的序列。3.代码实现 package tree;import java.util.Arrays;/** * @author LeeZhi * @version 1.0 */public class HeapSort { public static void main(String[] args) { ///要求对数组进行升序排序 int arr[] = {4, 6, 8, 5, 9}; heapSort(arr); } ////编写堆排序方法 public static void heapSort(int arr[]) { int temp = 0; System.out.println(”堆排序!!"); ///////// adjustHeap(arr,1, arr.length);// System.out.println("第1次"+ 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));//9 6 8 5 4 } //数组(二叉树)，调整成大顶堆 /** * 功能: 完成将以 i 对应的非叶节点数量调整为大顶堆 * 举例 举例int arr[]{4，6，8，5，9};=>i=1=>adjustHeap=>得到{4，9，8，5，6} * * @param arr 带调整的数组 * @param i 数组中的索引表示非叶子结点 * @param length 这意味着调整了多少元素，length 正在逐渐减少 */ public static void adjustHeap(int arr[], int i, int length) { int temp = arr[i];///先取出当前元素的值，临时变量保存 //开始调整 //说明 //1.k=i*2+1k是i结点的左子结点 for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { if (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值放在调整后的位置 }} 哈夫曼树1.基本介绍 给定n个权值作为叶结点，构建二叉树，如果树的带权路径长度(wpl)达到最小，称这样的二叉树为最佳二叉树，也称哈夫曼树Huffman Tree,还有一些书被翻译成霍夫曼树。 赫夫曼树是带权路径长度最短的树，权值较大的结点靠近根部。 2.赫夫曼树的几个重要概念和例子 路径和路径长度：在一棵树上，儿童或孙子从一个结点向下可以到达的路径称为路径。路径中分支的数量称为路径长度。如果根点的层数为1，则从根点到第L层结点的路径长度为L-1 结点的权利和权利路径长度：如果将树中的结点赋予具有一定意义的值，则该值称为结点的权利。结点的权利路径长度为：从根点到结点之间的路径长度和结点的权利乘积

树的带权路径长度：树的带权路径长度规定为所有叶结点的带权路径长度之和，记为WPL(weighted path length),权值越大，离根点越近的二叉树是最好的二叉树。 最小的WPL是赫夫曼树

3.思路分析

　　构成赫夫曼树的步骤：

　　1)从小到大排序，每个数据，每个数据都是一个节点，每个节点都可以看作是最简单的二叉树

　　2)取出根节点权值最小的两棵二叉树

　　3)形成新的二叉树，新的二叉树根节点的权重是前两个二叉树根节点的权重和

　　4)然后将新的二叉树按根节点的权重排序，重复1-2-3-4的步骤，直到数列中处理所有数据，获得赫夫曼树4.代码实现 package huffmantree;import java.util.ArrayList;import java.util.Collections;import java.util.List;/** * @author LeeZhi * @version 1.0 */public class HuffmanTree { public static void main(String[] args) { int arr[] = {13,7,8,3,29,6,1}; Node node = createHuffmanTree(arr); ///测试一个 preOrder(node); } ////编写前序遍历的方法 public static void preOrder(Node root){ if (root!=null){ root.preOrder(); }else{ System.out.println()是空树，不能遍历~"); } } ////创建赫夫曼树的方法 /** * * @param arr 需要创建成哈夫曼树的数组 * @return 赫夫曼树的root节点创建后 */ public static Node createHuffmanTree(int []arr){ //第一步，操作方便 /1.遍历arrr数组 //2.将arr的每个元素构成Node //3.将Node放入ArrayList中 Listnodes = new ArrayList(); for(int value:arr){ nodes.add(new Node(value)); } ///我们处理的过程是一个循环过程 while(nodes.size()>1){ //从小到大排序 Collections.sort(nodes); System.out.println("nodes="+nodes); ///取出根节点权值最小的两棵二叉树 //(1)取出权值最小的节点(二叉树) Node leftNode = nodes.get(0); //(2)取出权值第二小的节点(二叉树) 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); }}//创建结点类// 对象继续排序Collection集合排序//让Node实现Comparable接口classs Node implements Comparable{ int value;///节点权值 Node left;//指向左节点 Node right;//指向右子节点 //写一个前序遍历 public void preOrder(){ System.out.println(this); if (this.left!=null){ this.left.preOrder(); } if (this.right!=null){ this.right.preOrder(); } } public Node(int value) { this.value = value; } @Override public String toString() { return "Node{" + "value=" + value + '}'; } @Override public int compareTo(Node o) { //表示从小到大排序 return this.value-o.value; }}