在树结构上创建深度流

Question

因此，我有一个基本的树结构，该结构由树节点组成，该树节点链接到具有父级和子级引用的其他树节点。我想创建一个方法，该方法返回一个 Stream，该流从叶节点流式传输到根节点或从根到叶。我已经实现了这个，但我正在寻找一种创建最少对象的解决方案。最好没有。这是我的代码：

  public class TreeNode<TNode> {

      private TNode iValue;

      private TreeNode<TNode> iParentNode = null;

      private List<TreeNode<TNode>> iChildren = new ArrayList<>();

      public TreeNode(TNode value) {
          this(value, null);
      }

      private TreeNode(TNode value, TreeNode<TNode> parentNode) {
          iValue = value;
          iParentNode = parentNode;
      }

      public Stream<TreeNode<TNode>> streamFromLeaf() {
          return StreamSupport.stream(Spliterators.spliteratorUnknownSize(new LeafFirstIterator(this), Spliterator.SIZED),
            false);
      }

      public Stream<TreeNode<TNode>> streamFromRoot() {
          return StreamSupport.stream(Spliterators.spliteratorUnknownSize(new RootFirstIterator(this), Spliterator.SIZED),
            false);
      }

      public TNode getValue() {
          return iValue;
      }

      public TreeNode<TNode> getParent() {
          return iParentNode;
      }

      public TreeNode<TNode> addChild(TNode childValue) {
          TreeNode<TNode> childNode = new TreeNode<TNode>(childValue, iNodeNameFunction, this);
          iChildren.add(childNode);
          return childNode;
      }

      public boolean isLeaf() {
          return iChildren.size() == 0;
      }

      public boolean isRoot() {
          return iParentNode == null;
      }

      public List<TreeNode<TNode>> getChildren() {
          return iChildren;
      }

      class LeafFirstIterator implements Iterator<TreeNode<TNode>> {

          private TreeNode<TNode> iNextNode;

          LeafFirstIterator(TreeNode<TNode> leafNode) {
              iNextNode = leafNode;
          }

          @Override
          public boolean hasNext() {
              return iNextNode != null;
          }

          @Override
          public TreeNode<TNode> next() {
              TreeNode<TNode> current = iNextNode;
              iNextNode = current.getParent();
              return current;
          }

      }

      class RootFirstIterator implements Iterator<TreeNode<TNode>> {

          private List<TreeNode<TNode>> iNodes = new ArrayList<>();

          private int iNextIndex;

          RootFirstIterator(TreeNode<TNode> leafNode) {
              TreeNode<TNode> currentNode = leafNode;
              while (currentNode != null) {
                  iNodes.add(currentNode);
                  currentNode = currentNode.getParent();
              }
              iNextIndex = iNodes.size() - 1;
           }

           @Override
           public boolean hasNext() {
               return iNextIndex >= 0;
           }

           @Override
           public TreeNode<TNode> next() {
               return iNodes.get(iNextIndex--);
           }

       }
   }

这很好，但我的“问题”是，为每个流调用创建了很多对象。

• StreamSupport.stream 创建新的 ReferencePipeline
• Spliterators.spliteratorUnknownSize 创建新的 IteratorSpliterator
• 我创建自己的迭代器实现以传递给Spliterator
• RootFirstIterator 创建新的 ArrayList

流将被大量使用，所以我想尽可能避免创建对象。在没有流的情况下迭代树结构是一件简单的事情。现在我只使用流的映射方法。我可以只拥有一个接受消费者的方法，迭代深度并为每个节点调用消费者，不会创建任何对象，但我会失去所有流功能。看起来大概是这样的:

public void iterateUp(Consumer<TreeNode<TNode>> consumer) {
    doIterateUp(this, consumer);
}

public static <T> void doIterateUp(TreeNode<T> node, Consumer<TreeNode<T>> consumer) {
    if (node == null)
        return;
    consumer.accept(node);
    doIterateUp(node.getParent(), consumer);
}

从根开始向下迭代也一样简单。

对此有什么想法吗？我是不是走错路了？TreeNode应该实现或扩展一些接口/类吗？如果有什么不清楚的，请告诉我。

谢谢！

Answer 1

我不同意您对性能的担忧，但是，您的代码还有简化的空间，这可能会解决您的一些担忧作为副作用。

您犯了一个常见的错误，即从< code>Iterator实现开始，很可能是因为< code>Iterator接口很老而且广为人知。但是实现它很麻烦，而且如果您只是直接实现< code>Spliterator,则不需要将< code >迭代器包装在< code>Spliterator中，这只是一个很好的副作用:

public Stream<TreeNode<TNode>> streamFromLeaf() {
    return StreamSupport.stream(new LeafFirstSpliterator<>(this), false);
}
static class LeafFirstSpliterator<TNode>
extends Spliterators.AbstractSpliterator<TreeNode<TNode>> {
    private TreeNode<TNode> iNextNode;
    LeafFirstSpliterator(TreeNode<TNode> leafNode) {
        super(100, ORDERED|NONNULL);
        iNextNode = leafNode;
    }
    public boolean tryAdvance(Consumer<? super TreeNode<TNode>> action) {
        if(iNextNode==null) return false;
        action.accept(iNextNode);
        iNextNode=iNextNode.getParent();
        return true;
    }
}

对我来说，Spliterator 实现看起来更干净，至少它没什么好怕的，它可能允许更快的流遍历。您可以考虑重写 forEachRemaining 方法，因为它可以直接实现。

对于从根到叶的流，临时存储似乎是不可避免的，但如果是这样，请不要浪费时间进行低级编码，只需使用存储的内置流式处理功能：

public Stream<TreeNode<TNode>> streamFromRoot() {
    ArrayDeque<TreeNode<TNode>> deque = new ArrayDeque<>();
    for(TreeNode<TNode> n = this; n != null; n = n.getParent())
        deque.addFirst(n);
    return deque.stream();
}

Answer 2

不要使用流。使用您的替代方案，它有一个名称：访客模式。

流并不总是正确的方法，这是使用访问者模式的经典案例。

如果您一定要有一个流，让您的使用者收集列表中的节点，然后对其进行流处理，或者将使用者连接到迭代器的< code>next()方法(使用一些代码使其行为正常)，并使用StreamSupport将其转换为流。