原创

树结构的实际应用

温馨提示:
本文最后更新于 2022年06月18日,已超过 8 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

树结构的实际应用

堆排序

  • 大顶堆:堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆,
  • 小顶对:每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
  • 大顶堆特点:arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] // i 对应第几个节点,i从0开始编号
  • 小顶堆:arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2] // i 对应第几个节点,i从0开始编号
    一般升序采用大顶堆,降序采用小顶堆

堆排序的基本思想

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

代码实现

package cn.rlfit.heapSort;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author Mr.sun
 */
public class HeapSot {
    public static void main(String[] args) {
        int[] array = {4,6,8,5,2};
        HeapSortTest.heatSort(array);
        System.out.println(Arrays.toString(array));
    }
}
class HeapSortTest{
    public static void adjust(int[] array,int i,int length){
        //首先将数组构建成为一个大顶堆,从i开始比较,比较i的叶子节点是否比i本身大
        //首先将i节点存储起来,因为i每一次都会被赋给k,然而我们可能会比较两次以上
        int temp = array[i];
        //得到叶子节点,循环比较和i节点的大小
        for(int k =i*2+1 ;k<length;k=k*2+1){
            //比较叶子节点的大小,将k指向最大的那一个叶子节点
            if(k+1<length && array[k+1]>array[k]){
                k++;
            }
            //和顶上的那一个节点进项比较,如果发现叶子节点大于顶上的那一个节点,就将叶子节点和顶上的那一个节点进行交换
            if(array[k]>temp){
                array[i] = array[k];
                i = k;
            }else{
                //为什么能够直接break呢,因为我们是从最底端进行比较的,再比较上一层的时候,最下面的已经符合大顶堆的要求,所以就可以直接break
                break;
            }
        }
        //循环结束之后意味着已近将最大值放在最顶端,k已经指向了最小值应该在在的地方,就可以直接将temp赋值给k(i在的地方)
        array[i] = temp;
    }
    //进行完交换之后我们就可以得到一个大顶堆,然后再将大顶堆进行交换,重复此操作,最后就可以得到一个有序的数组

    public static void heatSort(int[] array){
        //进行几次交换呢,就要看我们创建的二叉树有几层,二叉树的层数为array.length>>1+1层,这又取决于array.length的大小
        for(int i = (array.length>>1)-1;i>=0;i--){
            adjust(array,i, array.length);
        }
        for(int j = array.length-1;j>0;j--){
            int temp = array[j];
            array[j] = array[0];
            array[0] = temp;
            adjust(array,0,j);
        }
    }
}

image-20220508151810915

赫夫曼树

概念

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

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

image-20220508130422628

赫夫曼树的创建步骤

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

package cn.rlfit.hefumanTree;

import java.util.*;

/**
 * @author Mr.sun
 */
public class HefumanTree {
    public static void main(String[] args) {
        int[] array = {0,-1,10,100,9,6};
        Node node = structHefumanTree(array);
        Node.preOder(node);
    }
    /**
     * 1.从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树
     * 2.取出根节点权值最小的两颗二叉树
     * 3.组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
     * 4.再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复  1-2-3-4 的步骤,直到数列中,所有的数据都被处理,就得到一颗赫夫曼树
     */
    public static Node structHefumanTree(int[] array){
        //首先将节点存放在一个集合里面待会我们就可以利用集合来进行操作数据
        List list = new ArrayList();
        for (int  value : array) {
            list.add(new Node(value));
        }
        //现在已经将数据损放在在集合里面
        //将集合进行排序
        while(list.size()>1){
            Collections.sort(list);
            //取出根节点权值最小的值,就是排序之后,集合前面的两棵树
            Node left = (Node) list.get(0);
            Node right = (Node) list.get(1);
            //取出来的树组合成为一颗新的树
            Node newTree = new Node(left.value + right.value);
            newTree.left = left;
            newTree.right = right;
            //然后将已近处理好的树移除集合
            list.remove(left);
            list.remove(right);
            //然后将新的树存放到集合里面
            list.add(newTree);
            //然后重复次操作,直到集合里面只有一个数为止
        }
        return (Node) list.get(0);
    }

}
//创建节点将数组里面的数据存放在节点里面
//实现集合的排序首先要实现

class Node implements Comparable<Node>{
    int value;
    Node left = null;
    Node right = null;

    public Node(int value) {
        this.value = value;
    }
    //创建该节点应该有的方法,遍历方法

    //前序遍历

    public static void preOder(Node root){
        if(root !=null){
            System.out.println(root.value);
        }
        if(root.left !=null){
            preOder(root.left);
        }
        if(root.right !=null){
            preOder(root.right);
        }
    }

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

    //实现比较规则

    @Override
    public int compareTo(Node o) {
        return value - o.value;
    }
}

image-20220508152002401

大顶堆:堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆,
小顶对:每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
大顶堆特点:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点,i从0开始编号
小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 对应第几个节点,i从0开始编号
:堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆,
小顶对:每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
大顶堆特点:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点,i从0开始编号
小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 对应第几个节点,i从0开始编号
:堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆,
小顶对:每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
大顶堆特点:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点,i从0开始编号
小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 对应第几个节点,i从0开始编号
一般升序采用大顶堆,降序采用小顶堆

:堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆,
小顶对:每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
大顶堆特点:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点,i从0开始编号
小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 对应第几个节点,i从0开始编号
一般升序采用大顶堆,降序采用小顶堆

树结构的实际应用
堆排序
大顶堆:堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆,
小顶对:每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
大顶堆特点:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点,i从0开始编号
小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 对应第几个节点,i从0开始编号
一般升序采用大顶堆,降序采用小顶堆
堆排序的基本思想

正文到此结束