数据结构 玩转数据结构 9-3 创建线段树

标签：index null nums int 线段 tree 玩转 数据结构 public

0　　　　课程地址

https://coding.imooc.com/lesson/207.html#mid=13845

 

1　　　　重点关注

1.1　　　　创建线段树

见3.1

 

1.2　　　　代码如何引入方法

见3.1

 

2　　　　课程内容

 

 

3　　　　Coding

3.1　　　　创建线段树代码实现

• 关键代码

 /**
     * 初始化数组元素和tree(4*元素个数上节有推导)
     * @author weidoudou
     * @date 2023/1/15 15:34
     * @param nums 请添加参数描述
     * @return null
     **/
    public SegmentTree(E [] nums,Merge<E> merger){
        data = (E[])new Object[nums.length];
        for(int i = 0; i < nums.length; i++){
            data[i] = nums[i];
        }

        this.merger = merger;

        tree = (E[])new Object[4*nums.length];
        buildSegmentTree(0,0,data.length-1);
    }

    //2     创建线段树
    private void buildSegmentTree(int index,int l,int r){
        //2.1   终止条件
        if(l==r){
            tree[index] = data[l];

        //2.2   循环条件
        }else{
            //定义mid 将线段树节点平均拆分
            int mid = l+(r-l)/2;
            int indexL = getLeftChild(index);
            int indexR = getRightChild(index);
            buildSegmentTree(indexL,l,mid);
            buildSegmentTree(indexR,mid+1,r);
            tree[index] = merger.merge(tree[indexL],tree[indexR]);
        }

    }

 

• 线段树类：

package com.company;

/**
 * 线段树
 * 根据入参数组的元素个数，制造出线段树节点元素个数
 * @author weidoudou
 * @date 2023/1/15 15:24
 **/
public class SegmentTree<E> {
    //1     初始化线段树元素和数组元素
    private E[] data;
    private E[] tree;
    private Merge<E> merger;

    /**
     * 初始化数组元素和tree(4*元素个数上节有推导)
     * @author weidoudou
     * @date 2023/1/15 15:34
     * @param nums 请添加参数描述
     * @return null
     **/
    public SegmentTree(E [] nums,Merge<E> merger){
        data = (E[])new Object[nums.length];
        for(int i = 0; i < nums.length; i++){
            data[i] = nums[i];
        }

        this.merger = merger;

        tree = (E[])new Object[4*nums.length];
        buildSegmentTree(0,0,data.length-1);
    }

    //2     创建线段树
    private void buildSegmentTree(int index,int l,int r){
        //2.1   终止条件
        if(l==r){
            tree[index] = data[l];

        //2.2   循环条件
        }else{
            //定义mid 将线段树节点平均拆分
            int mid = l+(r-l)/2;
            int indexL = getLeftChild(index);
            int indexR = getRightChild(index);
            buildSegmentTree(indexL,l,mid);
            buildSegmentTree(indexR,mid+1,r);
            tree[index] = merger.merge(tree[indexL],tree[indexR]);
        }

    }

    //3     基本方法
    public int getSize(){
        return data.length;
    }

    public E get(int index){
        if(index<0||index>=getSize()){
            throw new IllegalArgumentException("get失败");
        }
        return data[index];
    }

    public int getLeftChild(int index){
        return index*2+1;
    }

    public int getRightChild(int index){
        return index*2+2;
    }

    public String toString(){
        StringBuffer sbf = new StringBuffer();
        sbf.append("[");
        for(int i = 0;i< tree.length;i++){
            if(tree[i]!=null){
                sbf.append(tree[i]);
            }else{
                sbf.append("null");
            }
            if(i!=tree.length-1){
                sbf.append(",");
            }
        }


        sbf.append("]");
        return sbf.toString();
    }


}

 

• 自定义接口

package com.company;

/**
 * 融合函数
 * @author weidoudou
 * @date 2023/1/17 6:38
 **/
public interface Merge<E> {
    E merge(E left,E right);
}

 

• 测试类：

package com.company;

public class Main {

    public static void main(String[] args) {
        Integer[] nums = {-2,0,3,-5,2,1};
        SegmentTree<Integer> segmentTree = new SegmentTree<>(nums, new Merge<Integer>() {
            @Override
            public Integer merge(Integer left, Integer right) {
                return left*right;
            }
        });

        System.out.println(segmentTree);
    }
}

 

• 测试结果：

[0,0,-10,0,3,-10,1,-2,0,null,null,-5,2,null,null,null,null,null,null,null,null,null,null,null]

Process finished with exit code 0

 

标签：index,null,nums,int,线段,tree,玩转,数据结构,public
From： https://www.cnblogs.com/1446358788-qq/p/17056863.html