likes
comments
collection
share

万字长文设计模式：迭代器模式 - “__ __启动，带你逛遍每个角落！”

作者站长头像
站长
· 阅读数 47

前言

Hi, 我是Rike，欢迎来到我的频道～

本篇为大家带来的是设计模式-迭代器模式。可能会很奇怪，刚看完工厂三部曲，这就开始迭代器了？但我确实是这么学的。哈哈哈哈哈～

起因是在使用Guava的AbstractIterator时，我对这个工具类的实现有些好奇，研究之后，发现已经在学习完迭代器模式了，干脆一不做二不休学习完。

本文会实现经典的迭代器模式实现，示例中不会出现JDK相关已实现的迭代器，请放心食用～～

在结尾拓展延伸部分，会聊一聊JDK的Iterator接口如何活学活用。 同时分享下，在开发中使用Guava的AbstractIterator实践的代码。

有什么不足请指出，希望各位喜欢！～

一、介绍

迭代器模式，是一种行为型设计模式，它对外提供了一个可迭代对象的访问顺序，且不会暴露对象的内部实现细节。即，该模式将可迭代对象的遍历和实现分离，使得其遍历方式可自行决定。

迭代器模式关注的是如何简化迭代对象的访问。

迭代器模式可以用于各种数据结构，不仅限于集合类型。它适用于任何可遍历的数据结构，包括但不限于以下情况：

  1. 集合类： 最常见的使用场景是在集合类（如列表、队列、栈、集合等）上应用迭代器模式，以便遍历其中的元素。
  2. 树形结构： 适用于树形结构，例如文件系统、组织架构等。通过迭代器模式，可以按照深度优先或广度优先的方式遍历树节点。
  3. 图结构： 适用于图结构，通过迭代器模式可以遍历图中的节点和边。
  4. 线性结构： 适用于线性结构，例如链表。迭代器模式可用于遍历链表中的节点。
  5. 自定义数据结构： 适用于自定义的数据结构，只要这些结构支持遍历操作。例如，某个应用中可能定义了一种特殊的数据结构，通过迭代器模式可以方便地对其进行遍历。

其优缺点如下：

  • 优点：
    • 封装迭代对象细节： 客户端无需关心对象内部结构，只需通过迭代器遍历元素。
    • 支持多种遍历方式： 可以根据需要实现不同的迭代器，支持不同的遍历方式，而不影响客户端代码。
    • 符合单一职责原则：一个迭代器对应一种结构
  • 缺点：
    • 增加了类的数量： 引入了迭代器接口和具体迭代器类，增加了系统的复杂度。
    • 可能降低性能： 在某些情况下，直接使用官方迭代对象自带的迭代方法可能更为高效，迭代器模式并不适用于所有的情况。
    • 遍历过程不可中断：一旦开始遍历，无法暂停、跳过、回滚某个元素，且遍历中进行写入操作是线程不安全的。

总体而言，迭代器模式可以应用于几乎所有需要遍历的数据结构，它提供了一种通用的方式来访问数据结构中的元素，使得客户端代码不必关心数据结构的具体实现细节。这种解耦合的设计使得系统更加灵活、可维护和可扩展。

二、模式原理

（一）角色关系

对于当前模式，我们需要清楚的知道其有几个角色，角色之间的关联关系。角色如下：

  • 抽象迭代器 - Iterator：定义遍历元素的接口，含hasHext()和next()方法。

    • hasHext()：检查是否还有下一个元素
    • next()：获取下一个元素

  • 具体迭代器 - ConcreteIterator：实现抽象迭代器接口进行具体的遍历操作。

  • 抽象聚合（容器） - Aggregate 或 Container：定义创建迭代器对象的接口，通常包括一个返回迭代器的方法。

  • 具体聚合（容器）- ConcreteAggregate 或 ConcreteContainer：实现抽象聚合接口，创建具体的迭代器对象。负责存储元素，并能够通过迭代器遍历元素。

从关联关系上看，可分成两派，

  • 迭代器关注如何遍历迭代对象。
  • 容器只关注创建迭代器的方式。

对于容器，我理解有两种：

  1. 通过接口实现来获取迭代器：可迭代对象的数据需要先在容器实现类中复制存储，使用新对象来创建迭代器。
  2. 在数据结构中提供另外的方法，直接创建迭代器。

这两种方式，都属于容器的定义，能存储，能提供迭代接口，我更倾向于使用通过接口获取迭代器。理由也十分简单，能将存储与实现进行分离，各自只专注于自身的任务，互不干扰。但缺点也十分明显，类数量会增加，系统复杂度会进一步提升。

两种方式我都会在下文中给出示例。

我更倾向于使用通过接口获取迭代器。理由是获取迭代器的逻辑能够跟数据存储类进行分离，二者专注于自身的任务，互不干扰。但缺点也十分明显，类的数量会增加，系统复杂度会进一步提升。

第二种方式的缺点是要注意线程安全。

（二）UML类图

下列UML图通过“分-总”的模式进行展示。

1.迭代器UML图

万字长文设计模式：迭代器模式 - “__ __启动，带你逛遍每个角落！”

当前一共实现了两种迭代器，分别是List​集合和BinaryTree​二叉树。集合直接实现了接口，而二叉树因为其本身类型多样化，其遍历可分为前序、中序、后序、层序。因此设计了抽象类在中间进行隔离。

当前只实现了前序遍历的迭代器。

2.容器UML图

万字长文设计模式：迭代器模式 - “__ __启动，带你逛遍每个角落！”

万字长文设计模式：迭代器模式 - “__ __启动，带你逛遍每个角落！”

以上两张图分别代表了两种迭代器容器：接口实现、类方法实现。

3.整体类图

整体关系图如下：

万字长文设计模式：迭代器模式 - “__ __启动，带你逛遍每个角落！”

三、应用实现

（一）应用场景

  1. 客户端能够透明地遍历聚合对象中的元素；
  2. 迭代对象存在多种便利方式；
  3. 隔离（结偶）数据结构和遍历算法，更改内部结构后不同遍历方式之间互不影响。

在上述场景中，无论是哪个场景都需要满足一个必要条件：算法遍历对象必须是一个可迭代对象。

（二）实现步骤

步骤如下：

  1. 创建迭代器接口；
  2. 实现迭代器接口；
  3. 创建迭代器容器接口；
  4. 实现迭代器容器接口；
  5. 客户端调用容器接口，获取对应迭代器，再使用迭代器进行遍历操作。

步骤看起来十分简单，但设计时需要考虑以下几点：

  1. 迭代器接口有多种不同形式时，使用枚举区分实现类。
  2. 迭代对象内部元素存储泛型化，便于扩展用途：在实际业务中，实体是复杂的，需要将迭代器适用于各种实体。
  3. 若在迭代器运行时进行增删，有可能会引发索引错乱、元素遗落，并发修改异常的问题。

（三）示例代码

在本次的示例代码中，实现了集合、二叉树前序遍历两种迭代器，基本迭代功能已实现。但仍会出现索引错乱、元素遗落、并发修改的问题！

二叉树节点结构请看附录。

1、创建迭代器接口

/**
 * @author linshangqing
 * 迭代器接口 - 只要元素可便利，即可使用该接口
 */
public interface ElementIterator<E> {
    /**
     * 是否有下一个元素
     *
     * @return 是否有下一个元素
     */
    boolean hasNext();

    /**
     * 获取下一个元素
     *
     * @return 下一个元素
     */
    E next();
}

2、实现迭代器接口

集合迭代器实现：

/**
 * @author linshangqing
 * List迭代器
 */
public class ListIterator<T> implements ElementIterator<List<T>> {
    private static final int DEFAULT_INDEX = 0;
    private static final int DEFAULT_SIZE = 5;

    /**
     * 迭代对象
     */
    private final List<T> iterList;

    /**
     * 迭代索引
     */
    private int index = DEFAULT_INDEX;

    /**
     * 迭代大小
     */
    private int size = DEFAULT_SIZE;

    public ListIterator(List<T> iterList) {
        this(iterList, DEFAULT_INDEX, DEFAULT_SIZE);
    }

    public ListIterator(List<T> iterList, int size) {
        this(iterList, DEFAULT_INDEX, size);
    }

    public ListIterator(List<T> iterList, int index, int size) {
        if (CollectionUtils.isEmpty(iterList)) {
            throw new NullPointerException("iterList is null");
        }
        if (index < 0 || index > iterList.size() || size < 0 || size > iterList.size()) {
            throw new IllegalArgumentException("index or size is illegal");
        }
        this.iterList = iterList;
        this.index = index;
        this.size = size;
    }

    @Override
    public boolean hasNext() {
        return index < iterList.size();
    }

    @Override
    public List<T> next() {
        // 如果有下一个元素, 则获取下一个元素。反之返回null。
        if (this.hasNext()) {
            int nextIndex = index + size;
            // 如果下一个元素索引大于迭代对象大小, 则将下一个元素索引设置为迭代对象大小。
            if (nextIndex > iterList.size()) {
                nextIndex = iterList.size();
            }
            // 获取下一个元素
            List<T> list = iterList.subList(index, nextIndex);
            // 设置迭代索引
            index = nextIndex;
            // 返回下一个元素
            return list;
        }
        return null;
    }
}

二叉树迭代器实现：

/**
 * @author linshangqing
 * 二叉树迭代器
 */
public abstract class BinaryTreeIterator<T> implements ElementIterator<BinaryTreeNode<T>> {

}

/**
 * @author linshangqing
 * 二叉树前序遍历迭代器
 */
public class PreOrderBinaryTreeIterator<T> extends BinaryTreeIterator<T> {
    private final BinaryTreeNode<T> node;
    private Deque<BinaryTreeNode<T>> deque;

    public PreOrderBinaryTreeIterator(BinaryTreeNode<T> node) {
        if (Objects.isNull(node)) {
            throw new IllegalArgumentException("treeNode can not be null");
        }
        this.node = node;
        this.initStack();
    }

    private void initStack() {
        // init
        if (Objects.isNull(this.node)) {
            throw new IllegalArgumentException("treeNode can not be null");
        }
        this.deque = new ArrayDeque<>();
        // 按照前序遍历，将二叉树节点压入栈中
        Deque<BinaryTreeNode<T>> tempStack = new ArrayDeque<>();
        tempStack.push(node);
        // 压栈
        while (!tempStack.isEmpty()) {
            BinaryTreeNode<T> pop = tempStack.pop();
            this.deque.offer(pop);
            if (Objects.nonNull(pop.getRight())) {
                tempStack.push(pop.getRight());
            }
            if (Objects.nonNull(pop.getLeft())) {
                tempStack.push(pop.getLeft());
            }
        }
    }

    @Override
    public boolean hasNext() {
        return !this.deque.isEmpty();
    }

    @Override
    public BinaryTreeNode<T> next() {
        if (this.hasNext()) {
            return this.deque.poll();
        }
        return null;
    }
}

3、创建迭代器容器接口

/**
 * @author linshangqing
 * 迭代器容器: 用于获取迭代器接口
 */
public interface ElementIteratorContainer<E> {
    /**
     * 获取迭代器接口
     *
     * @return 迭代器接口
     */
    ElementIterator<E> createIterator();
}

4、实现迭代器容器接口

集合迭代器容器实现：

/**
 * @author linshangqing
 */
public class ListIteratorContainer<T> implements ElementIteratorContainer<List<T>> {
    private final List<T> iterList;

    public ListIteratorContainer(List<T> iterList) {
        this.iterList = List.copyOf(iterList);
    }

    @Override
    public ElementIterator<List<T>> createIterator() {
        return new ListIterator<>(iterList);
    }
}

二叉树迭代器容器实现：

/**
 * @author linshangqing
 * 二叉树迭代器容器
 */
public class BinaryIteratorContainer<E> implements ElementIteratorContainer<BinaryTreeNode<E>> {
    private final BinaryTreeNode<E> root;

    public BinaryIteratorContainer(BinaryTreeNode<E> node) {
        this.root = BeanUtil.copy(node, BinaryTreeNode.class);
    }

    @Override
    public ElementIterator<BinaryTreeNode<E>> createIterator() {
        return new PreOrderBinaryTreeIterator<>(root);
    }
}

5、聚合实现

聚合实现是将多个迭代器容器放入当一个item类中，这样方便管理使用。

@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
public class AggregationItem<T> {
    /**
     * 聚合对象 - List
     */
    private List<T> list;

    /**
     * 迭代对象 - Map
     */
    private BinaryTreeNode<T> treeNode;

    /**
     * 获取迭代器接口
     *
     * @return 迭代器接口
     */
    public ElementIterator<List<T>> createListIterator() {
        ElementIterator<List<T>> iterator;
        // 方式1:通过容器接口创建
        ElementIteratorContainer<List<T>> iteratorContainer = new ListIteratorContainer<>(list);
        iterator = iteratorContainer.createIterator();
        // 方式2:直接创建
        iterator = new ListIterator<>(list);
        return iterator;
    }

    public ElementIterator<BinaryTreeNode<T>> createBinaryTreeIterator() {
        ElementIterator<BinaryTreeNode<T>> iterator;
        // 方式1:通过容器接口创建
        ElementIteratorContainer<BinaryTreeNode<T>> iteratorContainer = new BinaryIteratorContainer<>(treeNode);
        iterator = iteratorContainer.createIterator();
        // 方式2:直接创建
        iterator = new PreOrderBinaryTreeIterator<>(treeNode);
        return iterator;
    }

}

6、客户端使用

客户端调用容器接口，获取对应迭代器，再使用迭代器进行遍历操作。

/**
 * 迭代器 - 经典实现
 */
@Test
public void iteratorTest() {
    // 创建迭代对象
    List<String> iterList = List.of("0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10");
    AggregationItem<String> aggregationItem = AggregationItem.<String>builder()
            .list(iterList)
            .build();

    // 方式1: 使用迭代器工具类
    // 1.1 创建迭代器容器
    ElementIteratorContainer<List<String>> container = new ListIteratorContainer<>(iterList);
    // 1.2 获取迭代器
    ElementIterator<List<String>> iterator1 = container.createIterator();
    // 1.3 迭代获取结果
    while (iterator1.hasNext()) {
        List<String> stringList = iterator1.next();
        // 对迭代获取结果进行业务处理
        System.out.println(stringList);
    }

    // 方式2: 通过迭代对象获取迭代器
    // 2.1 获取迭代器
    ElementIterator<List<String>> iterator2 = aggregationItem.createListIterator();
    // 2.2 迭代获取结果
    while (iterator2.hasNext()) {
        List<String> next = iterator2.next();
        // 对迭代获取结果进行业务处理
        System.out.println(next);
    }
}

/**
 * 迭代器 - 二叉树迭代器
 */
@Test
public void binaryTreeIteratorTest() {
    // 创建迭代对象
    List<BinaryTreeNode<Integer>> treeNodeList = List.of(
            BinaryTreeNode.<Integer>builder().data(8).build(),
            BinaryTreeNode.<Integer>builder().data(4).build(),
            BinaryTreeNode.<Integer>builder().data(2).build(),
            BinaryTreeNode.<Integer>builder().data(1).build(),
            BinaryTreeNode.<Integer>builder().data(3).build(),
            BinaryTreeNode.<Integer>builder().data(6).build(),
            BinaryTreeNode.<Integer>builder().data(5).build(),
            BinaryTreeNode.<Integer>builder().data(7).build(),
            BinaryTreeNode.<Integer>builder().data(12).build(),
            BinaryTreeNode.<Integer>builder().data(10).build(),
            BinaryTreeNode.<Integer>builder().data(9).build(),
            BinaryTreeNode.<Integer>builder().data(11).build(),
            BinaryTreeNode.<Integer>builder().data(14).build(),
            BinaryTreeNode.<Integer>builder().data(13).build(),
            BinaryTreeNode.<Integer>builder().data(15).build()
    );
    BinaryTreeNode<Integer> initTree = binarySearchTreeBiz.initTree(treeNodeList);
    AggregationItem<Integer> aggregationItem = AggregationItem.<Integer>builder()
            .treeNode(initTree)
            .build();

    // 方式1: 使用迭代器工具类
    // 创建迭代器容器
    ElementIteratorContainer<BinaryTreeNode<Integer>> binaryIteratorContainer = new BinaryIteratorContainer<>(initTree);
    // 获取迭代器
    ElementIterator<BinaryTreeNode<Integer>> iterator1 = binaryIteratorContainer.createIterator();
    // 迭代获取结果
    while (iterator1.hasNext()) {
        BinaryTreeNode<Integer> node = iterator1.next();
        // 对迭代获取结果进行业务处理
        System.out.println(node.getData());
    }

    // 方式2: 通过迭代对象获取迭代器
    // 2.1 获取迭代器
    ElementIterator<BinaryTreeNode<Integer>> iterator2 = aggregationItem.createBinaryTreeIterator();
    // 2.2 迭代获取结果
    while (iterator2.hasNext()) {
        BinaryTreeNode<Integer> next = iterator2.next();
        // 对迭代获取结果进行业务处理
        System.out.println(next);
    }
}

上述示例代码，实现了List和Tree两种数据结构的迭代方法，同时也实现了容器接口调用、聚合调用两种使用方式。不足的是，本次只实现经典基本实现，是为了学习而写出的代码。在生产活动中，对于迭代对象的遍历尽可能使用JDK或第三方工具类提供的迭代方法。

四、拓展延伸

（一）JDK Iterator - 实现业务迭代器

在实际业务开发中，我们自行创建迭代器遍历对象的情况是十分少见的，且大部分迭代对象JDK都自带了迭代方法。更多场景下，我们会迭代获取数据源的数据，例如：批量导出、大文件写入、限流接口批量获取······。

我们可以根据需要实现JDK的Iterator接口，设计业务迭代器。例如，实现一个分页查询迭代器：

1、存在什么？

首先，想考当前设计需要的主要属性、方法都有哪些？

  1. 控制分页查询的变量：pageNo（页码）、pageSize（页容量）、total（数据总量）、totalPage（总页数）
  2. 由1可推出，需要分页查询方法、数据总量查询方法。
  3. JDK官方提供的Iterator接口共提供了四个方法，只需实现核心方法hasNext()和next()即可。

JDK Iterator接口方法：

  • boolean hasNext()：是否存在下一个迭代元素。
  • E next()：返回迭代元素。
  • void remove()：删除迭代器返回的最后一个元素，默认报错
  • void forEachRemaining(Consumer\<? super E> action)：对每个剩余元素执行给定操作，直到处理完所有元素或该操作引发异常。

2、设计核心思路？

迭代器的运行过程，核心就是判断迭代进度与记录数据获取。在JDK的Iterator接口中，即实现hasNext()、next()方法。

  • hasNext()：分页查询的迭代进度是否结束，可判断pageNo的下个页码是否超过totalPage，即pageNo <= totalPage。
  • next()：本方法分为三步设计：1.是否有下一位元素；2.从数据源中获取数据；3.变更控制分页变量；4.返回元素。

除此之外，我们还需要解决两个问题：计算total和totalPage及计算时机，数据源数据获取方法实现。这两个问题都会牵扯到查询数据源数据，并且需要考虑通用扩展性，因此可以拟定规范，将接口暴露，由开发者实现。至于计算时机，我理解有两处适宜：1.迭代器初始化后立即执行，即放在构造方法内。2.每次获取完数据后，核对下数值是否正确。

清楚核心实现思路后，就可以开始实现代码了。

3、实现代码

/**
 * @author linshangqing
 * 分页查询迭代器：使用JDK原生迭代器接口
 */
@Slf4j
public abstract class JdkAbstractPageQueryIterator<R> implements Iterator<PageInfo<R>> {
    /**
     * 当前页码
     */
    int pageNo = 1;
    /**
     * 每页大小
     */
    int pageSize = 10;
    /**
     * 总数
     */
    @Getter
    private long total = 0;
    /**
     * 总页数
     */
    @Getter
    private long totalPage = 0;
    /**
     * 是否已经结束查询
     */
    private boolean hasEndQuery;

    public JdkAbstractPageQueryIterator() {
        this(1, 10);
    }

    public JdkAbstractPageQueryIterator(int pageNo, int pageSize) {
        this(pageNo, pageSize, null);
    }

    public JdkAbstractPageQueryIterator(int pageNo, int pageSize, Long total) {
        this.pageNo = pageNo;
        assert pageSize > 0;
        this.pageSize = pageSize;
        if (Objects.isNull(total)) {
            this.total = this.count();
        } else {
            this.total = total;
        }
        this.calculateTotalPage();

    }

    /**
     * 是否有下一页
     * @return 是否有下一页
     */
    @Override
    public boolean hasNext() {
        return pageNo <= totalPage;
    }

    /**
     * 查询总数-抽象方法
     * @return 总数
     */
    public abstract long count();

    /**
     * 分页查询-抽象方法
     * @param pageNo   页码
     * @param pageSize 每页大小
     * @return 分页数据
     */
    public abstract List<R> queryList(int pageNo, int pageSize);

    /**
     * 获取下一页数据
     * @return 下一页数据
     */
    @Override
    public PageInfo<R> next() {
        if (!this.hasNext() || hasEndQuery) {
            return null;
        }
        List<R> list;
        try {
            list = this.queryList(pageNo, pageSize);
        } catch (Exception e) {
            log.error("分页查询异常, 参数如下:{}", this, e);
            throw new ProjectServiceException("分页查询异常", e);
        }
        if (CollectionUtils.isEmpty(list)) {
            hasEndQuery = true;
            return null;
        }
        if (this.count() != this.total) {
            this.total = this.count();
            this.calculateTotalPage();
        }
        return PageInfo.<R>builder()
                .data(list)
                .pageNo(this.pageNo++)
                .pageSize(this.pageSize)
                .total(this.total)
                .hasNext(this.hasNext())
                .nextPage(this.pageNo)
                .build();
    }

    /**
     * 计算总页数
     */
    private void calculateTotalPage() {
        this.totalPage = this.total % this.pageSize == 0
                ? this.total / this.pageSize
                : this.total / this.pageSize + 1;
    }
}

在本次实现代码中，考虑到不同数据的获取方式可能不同，因此暴露了count()​、queryList()两个接口规范，内部细节由调用方自行实现。迭代器泛型返回定义的是PageInfo<R>，可根据需要自行调整。

在实现还有一个hasEndQuery属性，用于记录迭代器状态，防止已结束迭代器继续进行请求。

那么我们如何使用呢？客官请看以下代码～～

@Resource
private ModelService modelService;

/**
 * 迭代器 - JDK Iterator 业务迭代器 - 分页查询
 */
@Test
public void jdkPageQueryIteratorTest(){
    // 1.假设方法入参
    ModelReqDto reqDto = ModelReqDto.builder()
            .modelField("string")
            .pageNo(2)
            .pageSize(15)
            .build();
    // 2.创建迭代器
    JdkAbstractPageQueryIterator<ModelDto> iterator = new JdkAbstractPageQueryIterator<>(reqDto.getPageNo(), reqDto.getPageSize()) {
        // 将pageNo、pageSize，赋值给迭代器，reqDo传递给service层，自定义count()、queryList()方法
        @Override
        public long count() {
            ModelReqDo reqDo = ModelReqDo.builder()
                    .modelField("string")
                    .build();
            return modelService.countByReqDo(reqDo);
        }

        @Override
        public List<ModelDto> queryList(int pageNo, int pageSize) {
            ModelReqDo reqDo = ModelReqDo.builder()
                    .modelField(reqDto.getModelField())
                    .pageNo(pageNo)
                    .pageSize(pageSize)
                    .build();
            return modelService.listByReqDo(reqDo);
        }
    };
    // 3.迭代获取结果
    while (iterator.hasNext()) {
        PageInfo<ModelDto> next = iterator.next();
        // 对迭代获取结果进行业务处理
        System.out.println(next);
    }
}

其中modelService的countByReqDo()、listByReqDo()是自定义的数据查询方法，可根据需要进行调整。

（二）Guava 库 AbstractIterator 工具类

在Google Guava库中，存在com.google.common.collect.AbstractIterator的工具类，方便程序员自行实现业务迭代。其本身实现了JDK的Iterator迭代器。具体特点如下：

  • 简化JDK Iterator接口的实现过程，开发者只需关注迭代元素的获取逻辑，无需实现所有的Iterator接口方法。
  • 迭代器根据迭代状态进行管理：判断迭代过程是否结束，防止重复计算，异常处理。
  • 根据迭代状态来判断迭代器是否正常运行，判断是否存在下一元素。

Maven版本如下：

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>30.1.1-jre</version>
</dependency>

1、源码解析

/**
 * This class provides a skeletal implementation of the {@code Iterator} interface, to make this
 * interface easier to implement for certain types of data sources.
 *
 * <p>{@code Iterator} requires its implementations to support querying the end-of-data status
 * without changing the iterator's state, using the {@link #hasNext} method. But many data sources,
 * such as {@link java.io.Reader#read()}, do not expose this information; the only way to discover
 * whether there is any data left is by trying to retrieve it. These types of data sources are
 * ordinarily difficult to write iterators for. But using this class, one must implement only the
 * {@link #computeNext} method, and invoke the {@link #endOfData} method when appropriate.
 *
 * <p>Another example is an iterator that skips over null elements in a backing iterator. This could
 * be implemented as:
 *
 * <pre>{@code
 * public static Iterator<String> skipNulls(final Iterator<String> in) {
 *   return new AbstractIterator<String>() {
 *     protected String computeNext() {
 *       while (in.hasNext()) {
 *         String s = in.next();
 *         if (s != null) {
 *           return s;
 *         }
 *       }
 *       return endOfData();
 *     }
 *   };
 * }
 * }</pre>
 *
 * <p>This class supports iterators that include null elements.
 *
 * @author Kevin Bourrillion
 * @since 2.0
 */
// When making changes to this class, please also update the copy at
// com.google.common.base.AbstractIterator
@GwtCompatible
public abstract class AbstractIterator<T> extends UnmodifiableIterator<T> {
  private State state = State.NOT_READY;

  /** Constructor for use by subclasses. */
  protected AbstractIterator() {}

  private enum State {
    /** We have computed the next element and haven't returned it yet. */
    READY,

    /** We haven't yet computed or have already returned the element. */
    NOT_READY,

    /** We have reached the end of the data and are finished. */
    DONE,

    /** We've suffered an exception and are kaput. */
    FAILED,
  }

  private @Nullable T next;

  /**
   * Returns the next element. <b>Note:</b> the implementation must call {@link #endOfData()} when
   * there are no elements left in the iteration. Failure to do so could result in an infinite loop.
   *
   * <p>The initial invocation of {@link #hasNext()} or {@link #next()} calls this method, as does
   * the first invocation of {@code hasNext} or {@code next} following each successful call to
   * {@code next}. Once the implementation either invokes {@code endOfData} or throws an exception,
   * {@code computeNext} is guaranteed to never be called again.
   *
   * <p>If this method throws an exception, it will propagate outward to the {@code hasNext} or
   * {@code next} invocation that invoked this method. Any further attempts to use the iterator will
   * result in an {@link IllegalStateException}.
   *
   * <p>The implementation of this method may not invoke the {@code hasNext}, {@code next}, or
   * {@link #peek()} methods on this instance; if it does, an {@code IllegalStateException} will
   * result.
   *
   * @return the next element if there was one. If {@code endOfData} was called during execution,
   *     the return value will be ignored.
   * @throws RuntimeException if any unrecoverable error happens. This exception will propagate
   *     outward to the {@code hasNext()}, {@code next()}, or {@code peek()} invocation that invoked
   *     this method. Any further attempts to use the iterator will result in an {@link
   *     IllegalStateException}.
   */
  protected abstract T computeNext();

  /**
   * Implementations of {@link #computeNext} <b>must</b> invoke this method when there are no
   * elements left in the iteration.
   *
   * @return {@code null}; a convenience so your {@code computeNext} implementation can use the
   *     simple statement {@code return endOfData();}
   */
  @CanIgnoreReturnValue
  protected final T endOfData() {
    state = State.DONE;
    return null;
  }

  @CanIgnoreReturnValue // TODO(kak): Should we remove this? Some people are using it to prefetch?
  @Override
  public final boolean hasNext() {
    checkState(state != State.FAILED);
    switch (state) {
      case DONE:
        return false;
      case READY:
        return true;
      default:
    }
    return tryToComputeNext();
  }

  private boolean tryToComputeNext() {
    state = State.FAILED; // temporary pessimism
    next = computeNext();
    if (state != State.DONE) {
      state = State.READY;
      return true;
    }
    return false;
  }

  @CanIgnoreReturnValue // TODO(kak): Should we remove this?
  @Override
  public final T next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    state = State.NOT_READY;
    T result = next;
    next = null;
    return result;
  }

  /**
   * Returns the next element in the iteration without advancing the iteration, according to the
   * contract of {@link PeekingIterator#peek()}.
   *
   * <p>Implementations of {@code AbstractIterator} that wish to expose this functionality should
   * implement {@code PeekingIterator}.
   */
  public final T peek() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    return next;
  }
}

AbstractIterator内含state、next两个私有成员变量，computeNext()、endOfData()、hasNext()、next()四个核心方法。

成员变量

next变量，存储了下一位迭代元素的数据，在hasNext()判断是否有下一位时获取，使用next()方法时返回元素。

state变量，用于记录迭代器的迭代状态，分为：

  • READY：已计算下一位元素，但仍未返回给调用者。
  • NOT_READY：默认状态，表示尚未计算元素或已返回该元素。即，处于未工作状态。
  • DONE：已到达迭代序列末尾，无法再进行迭代。
  • FAILED：异常状态，迭代器遇到意外且已无法继续。

迭代状态会在核心方法中收到控制，能够更加简洁的控制迭代器的运行，防止意外发生，例如：异常处理后继续运行迭代器、迭代序列结束但仍满足迭代条件继续迭代······。

核心方法

四个核心方法作用如下：

  • hasNext()、next()方法实现了JDK Iterator接口，使用者通过调用二者来判断是否可以获取数据、拿到迭代数据。
  • computeNext()是暴露在外的接口规范，由开发者自行实现
  • endOfData()主要用于设置迭代状态为DONE​，无法继续迭代获取元素。
​computeNext()​和endOfData()​

computeNext()需要开发者自行实现业务逻辑，在设计时需注意：

  • 判断业务流程中是否有下一位元素。
  • 当无法获取下一元素时，调用endOfData()方法更新迭代状态。

通过文档注释，可知这两个方法是强绑定的。当迭代中没有剩余元素时，实现必须调用endOfData() ，如果不这样做可能会导致无限循环。

​hasNext()​​和next()​​

在JDK官方Iterator中，会将“判断”和“获取”两个操作分开，分别放进hasNext()、next()中，分开思考设计即可。如上文中所实现的业务迭代器，hasNext()方法，放入纯粹的业务判断逻辑，不进行数据的存储。next()​方法，获取前先判断是否还有下一元素，再进行数据获取等一系列操作。

Guava库AbstractIterator类实现的方法却大不相同。

@CanIgnoreReturnValue
@Override
public final boolean hasNext() {
  checkState(state != State.FAILED);
  switch (state) {
    case DONE:
      return false;
    case READY:
      return true;
    default:
  }
  return tryToComputeNext();
}

private boolean tryToComputeNext() {
  state = State.FAILED;
  next = computeNext();
  if (state != State.DONE) {
    state = State.READY;
    return true;
  }
  return false;
}

AbstractIterator将“判断”和“获取”两操作合并到了hasNext()中，通过迭代状态判断是否可以正常取出下一位元素。调用后会先判断迭代器是否为FAIL​状态，若是则抛异常禁止继续运行。若为NO_READY，则会通过开发者实现的computeNext()方法获取下一元素，并存储到迭代器中，便于调用者随时取出。

@CanIgnoreReturnValue
@Override
public final T next() {
  if (!hasNext()) {
    throw new NoSuchElementException();
  }
  state = State.NOT_READY;
  T result = next;
  next = null;
  return result;
}

next()方法，会先进行hasNext()的判断，若true取则返回元素并重置迭代器状态。这是防御式编程，为了防止开发者直接调用next()，造成异常状态。

若直接调用两次next()，则会取迭代序列的两位元素，并非一个元素取两次。

因为数据是在hasNext()中获取的，next()只需要取出元素即可。

内存资源管理

在next()方法中有next = null;这句代码，很多文章解释为“帮助 JVM 回收对象”，但并没有进行解释。

对于本句代码，我理解是：为了保证每次迭代完成后，都不会将数据流入下一回合。

  1. 为了节约内存资源的创建。

至于是否帮助JVM回收内存，我认为并不在于这句代码，需要结合next属性、迭代器运行流程、运行时栈内存结构进行分析。代码结构请参考下文的实战代码，序列图如下所示。

万字长文设计模式：迭代器模式 - “__ __启动，带你逛遍每个角落！”

AbstractPageQueryIterator被实例化后，内存变化会分为两个：在堆内存为该对象分配空间，在pageMethod()的栈内存中创建变量对象（引用堆内存地址）。若成功从computeNext()获取迭代数据时，就会在堆内存中为其分配内存空间，并且将其引用地址赋值给AbstractPageQueryIterator的next属性。

实际上，在本次迭代结束前，迭代元素会一直存储在堆内存中，它会在当前迭代完成后，且无任何对象引用其时回收内存。

因此，next = null;并不会直接对JVM内存回收有影响。

2、实战应用

本次实现的是分页查询迭代器，抽象迭代器代码如下：

public abstract class AbstractPageQueryIterator<T> extends AbstractIterator<List<T>> {
    /**
     * 页码
     */
    int pageNo = 1;

    /**
     * 每页展示数量
     */
    int pageSize = 10;

    /**
     * 最大页数
     */
    long maxPageNo = 1000;

    public AbstractPageQueryIterator() {
        super();
    }

    public AbstractPageQueryIterator(int pageSize) {
        ProjectAssert.isLessThanNumber(pageSize, 0, CommonEnum.SYSTEM_ERROR);
        this.pageSize = pageSize;
    }

    /**
     * 迭代业务方法
     * @return 数据
     */
    @Override
    protected List<T> computeNext() {
        // 当页数>最大页数时，退出
        if (pageNo > maxPageNo) {
            return endOfData();
        }
        // 查询数据
        PageInfo<T> pageInfo = this.query(pageNo++, pageSize);
        if (Objects.isNull(pageInfo) || CollectionUtils.isEmpty(pageInfo.getData())) {
            return endOfData();
        }
        this.setMaxPageNo(pageInfo);
        return pageInfo.getData();
    }

    /**
     * 自定义分类查询方法
     * @param pageNo 页码
     * @param pageSize 每页展示数量
     * @return 数据
     */
    public abstract PageInfo<T> query(int pageNo, int pageSize);

    private void setMaxPageNo(PageInfo<T> pageInfo) {
        if (Objects.nonNull(pageInfo)) {
            long total = pageInfo.getTotal();
            if (total % pageSize == 0) {
                maxPageNo = total / pageSize;
            } else {
                maxPageNo = (total / pageSize) + 1;
            }
        }
    }
}

computeNext()方法的实现，我分为了三部分：

  1. 判断业务是否能取下一元素；
  2. 调用分页查询接口，取出下一位元素；
  3. 更改迭代器属性，并返回元素；

其中分页查询接口仍然采用抽象方法定义，将接口暴露，让开发者按需自行定义。而业务判断是通过计算是否超过总页数，来判断迭代是否结束。

应用上文业务迭代器代码相似：

@Test
public void pageQueryIteratorTest() {
    ModelReqDto reqDto = ModelReqDto.builder()
            .modelField("string")
            .pageNo(2)
            .pageSize(10)
            .build();
    AbstractPageQueryIterator<ModelDto> nativeIterator = new AbstractPageQueryIterator<>() {
        // count方式一：初始化时查询一次
        final long total = modelService.countByReqDo(BeanUtil.copy(reqDto, ModelReqDo.class));
        @Override
        public PageInfo<ModelDto> query(int pageNo, int pageSize) {
            ModelReqDo reqDo = BeanUtil.copy(reqDto, ModelReqDo.class);
            reqDo.setPageNo(pageNo);
            reqDo.setPageSize(pageSize);
            List<ModelDto> list = modelService.listByReqDo(reqDo);
            if (CollectionUtils.isEmpty(list)) {
                return PageInfoUtil.emptyPageInfo();
            }
            return PageInfo.<ModelDto>builder()
                    .pageNo(pageNo)
                    .pageSize(pageSize)
                    .total(modelService.countByReqDo(reqDo)) // count方式二：每次查询后都会再次查询个数
                    .data(list)
                    .hasNext(true)
                    .build();
        }
    };
    while (nativeIterator.hasNext()) {
        List<ModelDto> list = nativeIterator.next();
        // 对list进行业务处理
        System.out.println(list);
    }
}

total分页数据总数的计算，可以分为两种：初始化时查询一次，或每次分页查询时都进行查询。

（三）注意

以上两种方式实现的迭代器都是惰性迭代器。即，非一次性遍历全部数据，每次迭代只会存在对应数据。

需注意，若对接数据库为数据源（例MySQL），无法保证迭代时数据总量不变。

若数据需要强一致性，个人建议：

  • 将迭代逻辑放入到事务中；
  • count方法在初始化时查询一次，确定整个迭代逻辑的数据总量。

五、附录

树节点结构

/**
 * @author linshangqing
 * 数据结构-根基类
 */
@Data
@SuperBuilder
@NoArgsConstructor
@AllArgsConstructor
public class BaseDataStructure<T> {
    /**
     * 数据
     */
    T data;
}

/**
 * @author linshangqing
 * 树-根基类
 */
@Data
@SuperBuilder
@NoArgsConstructor
@AllArgsConstructor
public class BaseTreeNode<T> extends BaseDataStructure<T> {
    /**
     * 是否为root节点
     */
    @Builder.Default
    boolean isRoot = false;
}

@Data
@SuperBuilder
@NoArgsConstructor
@AllArgsConstructor
public class BinaryTreeNode<T> extends BaseTreeNode<T> {
    /**
     * 左节点
     */
    private BinaryTreeNode<T> left;

    /**
     * 右节点
     */
    private BinaryTreeNode<T> right;
}

树业务代码

接口：

/**
 * @param <E>        数据类型
 * @param <TreeNode> 树节点类型
 *                   树-业务接口
 * @author linshangqing
 */
public interface TreeBiz<E, TreeNode extends BaseTreeNode<E>, Req extends TreeReqDto<E>> {

    /**
     * 初始化树
     *
     * @param nodeList 节点列表
     */
    TreeNode initTree(List<TreeNode> nodeList);

    /**
     * 判断树是否为空
     *
     * @return 是否为空
     */
    boolean isEmpty(TreeNode node);

    /**
     * 获取根节点
     *
     * @param nodeList 节点列表
     * @return 根节点
     */
    TreeNode getRootNode(List<TreeNode> nodeList);

    /**
     * 获取最小节点
     *
     * @param node 节点
     * @return 最小节点
     */
    TreeNode getMinNode(BinaryTreeNode<E> node);

    /**
     * 获取最大节点
     *
     * @param node 节点
     * @return 最大节点
     */
    TreeNode getMaxNode(BinaryTreeNode<E> node);

    /**
     * 获取树的信息
     *
     * @param node 树节点
     * @return 树的信息
     */
    TreeInfo getTreeInfo(TreeNode node);

    /**
     * 添加节点
     *
     * @param rootNode   root节点
     * @param insertNode 需插入数据节点
     */
    void insert(TreeNode rootNode, TreeNode insertNode);

    /**
     * 删除节点
     *
     * @param rootNode 节点
     * @param data     删除数据
     */
    void delete(TreeNode rootNode, E data);

    /**
     * 查找节点
     *
     * @param rootNode 节点
     * @param req      查找条件
     * @return 查找到的节点
     */
    TreeNode search(TreeNode rootNode, Req req);

    /**
     * 遍历树
     *
     * @param node         树节点
     * @param traverseType 遍历类型
     * @param isRecursion  是否递归
     */
    void traverse(TreeNode node, TraverseTypeEnum traverseType, boolean isRecursion);
}

实现：

public abstract class AbstractTreeImpl<E, T extends BaseTreeNode<E>, Req extends TreeReqDto<E>> implements TreeBiz<E, T, Req> {
    @Resource
    protected DataStructureTraverse<E, T> dataStructureTraverse;

    /**
     * 去除空节点
     *
     * @param nodeList 节点列表
     */
    protected void nodeListRemoveEmpty(List<T> nodeList) {
        nodeList.removeIf(this::nodeIsEmpty);
    }

    /**
     * 判断节点是否为空
     *
     * @param node 节点
     * @return 是否为空
     */
    protected boolean nodeIsEmpty(T node) {
        return Objects.isNull(node) || Objects.isNull(node.getData());
    }

    /**
     * 递归插入节点
     *
     * @param currentNode 当前节点
     * @param insertNode  需插入节点
     */
    protected abstract T insertRec(T currentNode, T insertNode);

    /**
     * 递归删除节点
     *
     * @param currentNode 当前节点
     * @param data        删除数据
     * @return 删除后的节点
     */
    protected abstract T deleteRec(T currentNode, E data);

    /**
     * 节点数据比较
     *
     * @param data1 数据1
     * @param data2 数据2
     * @return 比较结果 -1：data1 < data2; 0: data1 = data2; 1: data1 > data2
     */
    protected abstract int compareNodeData(@NotNull E data1, @NotNull E data2);
}





@Slf4j
@Component
public class BinarySearchTreeImpl<E> extends AbstractTreeImpl<E, BinaryTreeNode<E>, TreeReqDto<E>> {
    @Override
    public BinaryTreeNode<E> initTree(List<BinaryTreeNode<E>> binaryTreeNodes) {
        List<BinaryTreeNode<E>> copyList = new ArrayList<>(binaryTreeNodes); // 防止传入list为不可变的
        // 去除空节点
        this.nodeListRemoveEmpty(copyList);
        // 判断节点list是否为空
        if (CollectionUtils.isEmpty(copyList)) {
            log.info("BinarySearchTreeImpl#initTree, 节点list为空, 无法初始化树");
            return null;
        }
        // 按照规则寻找最小值, 作为root节点
        BinaryTreeNode<E> rootNode = this.getRootNode(copyList);
        if (Objects.isNull(rootNode)) {
            log.info("BinarySearchTreeImpl#initTree, 未找到root节点, binaryTreeNodes:{}", JSONObject.toJSONString(copyList));
            return null;
        }
        // 使用insert方法插入节点
        copyList.forEach(insertNode -> {
            // root节点不需要插入
            if (insertNode.isRoot()) {
                return;
            }
            // 插入节点
            this.insert(rootNode, insertNode);
        });
        log.info("BinarySearchTreeImpl#initTree, 已初始化树, 数据如下, root:{}", JSONObject.toJSONString(rootNode));
        return rootNode;
    }

    @Override
    public boolean isEmpty(BinaryTreeNode<E> node) {
        // root节点不存在, 说明树为空
        return Objects.isNull(node);
    }

    @Override
    public BinaryTreeNode<E> getRootNode(List<BinaryTreeNode<E>> binaryTreeNodes) {
        if (CollectionUtils.isEmpty(binaryTreeNodes)) {
            log.info("BinarySearchTreeImpl#getRootNode, 节点list为空, 无法找到root节点");
            return null;
        }
        // 当前使用list首个元素作为root节点, 实际业务中会更加复杂。思路：此处可使用RuleHandler来定制规则获取root。
        BinaryTreeNode<E> root = binaryTreeNodes.get(0);
        if (root.getData() instanceof Integer) {
            root = this.getMiddleIntegerNodeRoot(binaryTreeNodes);
        }
        root.setRoot(true);
        log.info("BinarySearchTreeImpl#getRootNode, root:{}", JSONObject.toJSONString(root));
        return root;
    }

    @Override
    public BinaryTreeNode<E> getMinNode(BinaryTreeNode<E> node) {
        if (this.nodeIsEmpty(node) || Objects.isNull(node.getLeft())) {
            log.info("BinarySearchTreeImpl#getMinNode, 最小节点, node:{}", JSONObject.toJSONString(node));
            return node;
        }
        return this.getMinNode(node.getLeft());
    }

    @Override
    public BinaryTreeNode<E> getMaxNode(BinaryTreeNode<E> node) {
        if (this.nodeIsEmpty(node) || Objects.isNull(node.getRight())) {
            log.info("BinarySearchTreeImpl#getMaxNode, 最大节点, node:{}", JSONObject.toJSONString(node));
            return node;
        }
        return this.getMaxNode(node.getRight());
    }

    /**
     * 寻找中位数(仅支持Integer)
     *
     * @param list 节点列表
     * @return 中位数节点
     */
    private BinaryTreeNode<E> getMiddleIntegerNodeRoot(List<BinaryTreeNode<E>> list) {
        List<BinaryTreeNode<E>> copyList = new ArrayList<>(list).stream()
                .sorted((o1, o2) -> this.compareNodeData(o1.getData(), o2.getData()))
                .collect(Collectors.toList());
        return copyList.get(copyList.size() / 2);
    }

    @Override
    public TreeInfo getTreeInfo(BinaryTreeNode<E> node) {
        return null;
    }

    @Override
    public void insert(BinaryTreeNode<E> rootNode, BinaryTreeNode<E> insertNode) {
        // 1.判断节点及数据是否为空
        if (this.nodeIsEmpty(rootNode) || this.nodeIsEmpty(insertNode)) {
            log.info("BinarySearchTreeImpl#insert, 当前root节点或插入节点不存在, rootNode:{}, insertNode:{}",
                    JSONObject.toJSONString(rootNode), JSONObject.toJSONString(insertNode));
            return;
        }
        log.info("BinarySearchTreeImpl#insert, 当前root节点或插入节点不存在, 入参如下, rootNode:{}, insertNode:{}",
                JSONObject.toJSONString(rootNode), JSONObject.toJSONString(insertNode));
        // 2.判断data数据是否存在, 存在则直接返回。
        BinaryTreeNode<E> search = this.search(rootNode, TreeReqDto.<E>builder().data(insertNode.getData()).build());
        if (Objects.nonNull(search)) {
            log.info("BinarySearchTreeImpl#insert, 当前节点数据已存在于树中, 无法添加！rootNode:{}, insertNode:{}",
                    JSONObject.toJSONString(rootNode), JSONObject.toJSONString(insertNode));
            return;
        }
        // 3.判断insertNode是否小于rootNode, 小于则进入左子树, 大于插入右子树
        this.insertRec(rootNode, insertNode);
    }

    @Override
    protected BinaryTreeNode<E> insertRec(BinaryTreeNode<E> currentNode, BinaryTreeNode<E> insertNode) {
        // 1.判断节点是否为空
        if (this.nodeIsEmpty(insertNode)) {
            return null;
        }
        // 2.当前节点若为null, 则返回insertNode
        if (this.nodeIsEmpty(currentNode)) {
            return insertNode;
        }
        // 3.判断当前节点是否小于插入节点, 小于进入左子树递归, 大于进入右子树递归
        int compareFlag = this.compareNodeData(insertNode.getData(), currentNode.getData());
        if (compareFlag < 0) {
            currentNode.setLeft(this.insertRec(currentNode.getLeft(), insertNode));
        } else if (compareFlag > 0) {
            currentNode.setRight(this.insertRec(currentNode.getRight(), insertNode));
        }
        // 4.返回当前节点
        return currentNode;
    }

    @Override
    protected int compareNodeData(@NotNull E data1, @NotNull E data2) {
        // 这里简单地比较 toString 的结果, 实际中可能需要更复杂的逻辑。此时可以使用RuleHandler来定制规则。
        if (data1 instanceof Integer && data2 instanceof Integer) {
            return Integer.compare((Integer) data1, (Integer) data2);
        }
        return data1.toString().compareTo(data2.toString());
    }

    @Override
    public void delete(BinaryTreeNode<E> rootNode, E delData) {
        // 当前删除是直接比对数据, 数据符合则删除。实际业务中可能需要更复杂的逻辑。此时可以使用RuleHandler来定制规则。
        // 1.判断root及数据是否为空
        if (this.nodeIsEmpty(rootNode) || Objects.isNull(delData)) {
            return;
        }
        // 2.递归删除
        this.deleteRec(rootNode, delData);
    }

    /**
     * 递归逻辑：<br>
     * 1.判断当前节点是否为null, true则为叶子节点。即未找到删除节点, 返回null。<br>
     * 2.判断当前节点是否为删除节点：<br>
     * 2.1 delData < currentNode：递归进入currentNode左子树。<br>
     * 2.2 delData > currentNode：递归进入currentNode右子树。<br>
     * 2.3 delData = currentNode：currentNode为删除节点。<br>
     * 2.3.1 currentNode是否为叶子or单子树节点：若是, 左子树存在返回左子树, 左子树不存在返回右子树。<br>
     * 2.3.2 currentNode为全子树节点：<br>
     * 2.3.2.1 寻找替代节点(左子树最大值 or 右子树最小值)<br>
     * 2.3.2.2 currentNode的数据位替换为替代节点数据。<br>
     * 2.3.2.3 从currentNode中删除替代节点。<br>
     * 2.3.2.4 返回currentNode。<br>
     * <p>
     * <p>
     * 注意：<br>
     * 找到目标节点后, 我的第一反应是向单链表一样删除, 但实现其实非常繁琐：（假设目标节点为t, 目标节点的父节点为tp, 替代节点为r, 替代节点的父节点为rp）<br>
     * 1.寻找tp、r、rp三个节点。<br>
     * 2.判断r节点在rp节点的哪个分支子树上。<br>
     * 3.滞空rp节点的r节点位置。<br>
     * 4.r节点的两个子树, 改赋值为t节点的左右子树。<br>
     * 5.判断t节点在tp节点的哪个分支子树上。<br>
     * 6.r节点替换tp节点上t节点的位置。（用C语言的角度来说就是, tp节点指向t的指针改指向r）<br>
     * 7.滞空t节点的左右分支。<br>
     * <p>
     * 这样做会引发以下思考：<br>
     * * 思考1：我如何找到tp节点, 因二叉树节点特性, 无法反推父节点。唯一方法是通过root节点向下推理得出。<br>
     * * 思考2：需要查询三次节点, 无论哪种查找方式, 逻辑太繁琐。不适合<br>
     * * 思考3：不能使用局部变量来作为temp, 可能会出现赋空的情况, 或未继承子树分支的情况。<br>
     * 相当于, 在递归方法内使用了非递归的方式进行删除。<br>
     * <p>
     * 递归算法本质上是将“一个问题可以分解成具有相同解决思路的子问题”的算法, 因此在设计时就需要考虑, 函数要干什么、怎么干、结果怎么用。<br>
     * 对于本题而言, 就是找到当前节点对应的子节点, 且进行赋值操作。因此需要考虑, 当前递归层中, currentNode在不同情况下方法的返回值。<br>
     * * null：返回null, 相当于未找到目标节点。<br>
     * * 非目标节点：根据比对结果大小, 递归进入对应子树。<br>
     * * 目标删除节点：仍返回currentNode当前节点, 但需要将目标节点的数据位改为为替换对象节点的数据, 且删除树中的替换对象。PS: 删除可以使用当前迭代方法。<br>
     */
    @Override
    protected BinaryTreeNode<E> deleteRec(BinaryTreeNode<E> currentNode, E delData) {
        // 1.判断节点及数据是否为空
        if (this.nodeIsEmpty(currentNode)) {
            log.info("BinarySearchTreeImpl#deleteRec, 当前currentNode或节点内data属性为null, 未找到目标删除节点, currentNode:{}, delData:{}",
                    JSONObject.toJSONString(currentNode), JSONObject.toJSONString(delData));
            return null;
        }
        // 2.判断当前节点是否为删除节点
        int compareFlag = this.compareNodeData(delData, currentNode.getData());
        if (compareFlag < 0) {
            // 2.1 delData < currentNode：递归进入currentNode左子树。
            currentNode.setLeft(this.deleteRec(currentNode.getLeft(), delData));
        } else if (compareFlag > 0) {
            // 2.2 delData > currentNode：递归进入currentNode右子树。
            currentNode.setRight(this.deleteRec(currentNode.getRight(), delData));
        } else {
            // 2.3 delData = currentNode：currentNode为删除节点。
            // 2.3.1 currentNode为叶子节点or单子树节点
            if (this.nodeIsEmpty(currentNode.getLeft())) {
                return currentNode.getRight();
            } else if (this.nodeIsEmpty(currentNode.getRight())) {
                return currentNode.getLeft();
            }
            // 2.3.2 currentNode为全子树节点
            BinaryTreeNode<E> minNode = this.getMinNode(currentNode.getRight()); // 当前采用右子树最小值当作替代节点
            E replaceData = minNode.getData();
            // 替换数据，并且删除替代节点
            currentNode.setData(replaceData);
            minNode = this.deleteRec(currentNode.getRight(), replaceData);
            currentNode.setRight(minNode);
        }
        return currentNode;
    }

    @Override
    public BinaryTreeNode<E> search(BinaryTreeNode<E> currentNode, TreeReqDto<E> treeReqDto) {
        // 1.判断root及数据是否为空
        if (this.nodeIsEmpty(currentNode)) {
            log.info("BinarySearchTreeImpl#search, 当前currentNode或节点内data属性为null, 未找到目标节点, currentNode:{}, treeReqDto:{}",
                    JSONObject.toJSONString(currentNode), JSONObject.toJSONString(treeReqDto));
            return null;
        }
        // 2.判断当前节点是否为目标节点
        int compareFlag = this.compareNodeData(currentNode, treeReqDto);
        // 3.判断当前节点是否小于目标节点, 小于进入左子树递归, 大于进入右子树递归
        if (compareFlag < 0) {
            return this.search(currentNode.getLeft(), treeReqDto);
        } else if (compareFlag > 0) {
            return this.search(currentNode.getRight(), treeReqDto);
        } else {
            log.info("BinarySearchTreeImpl#search, 已找到目标节点, currentNode:{}, treeReqDto:{}",
                    JSONObject.toJSONString(currentNode), JSONObject.toJSONString(treeReqDto));
            return currentNode;
        }
    }

    @Override
    public void traverse(BinaryTreeNode<E> node, TraverseTypeEnum traverseType, boolean isRecursion) {
        Deque<BinaryTreeNode<E>> traverse = dataStructureTraverse.traverse(traverseType, node, isRecursion);
        traverse.forEach(System.out::println);
    }

    private int compareNodeData(BinaryTreeNode<E> currentNode, TreeReqDto<E> treeReqDto) {
        // 根据具体业务，来确定比对策略，判断当前节点是否为目标节点。当前默认比大小
        return this.compareNodeData(currentNode.getData(), treeReqDto.getData());
    }
}

​万字长文设计模式：迭代器模式 - “__ __启动，带你逛遍每个角落！”​

感谢各位观看，下期见～

参考资料

版权声明：个人学习记录，本博客所有文章均采用 CC-BY-NC-SA 许可协议。转载请注明出处。

若有侵权，请留言联系～

  1. Java全栈知识体系 -《行为型 - 迭代器(Iterator)》
  2. 程序员进阶 -《设计模式——迭代器模式》
  3. Hello算法 -《二叉搜索树》

如果您觉得文章对您有帮助，请点击文章正下方的小红心一下。您的鼓励是博主的最大动力！

转载自:https://juejin.cn/post/7355826327356342298
评论
请登录