在Tree结构上创建深度流

Question

所以，我有一个基本的树结构，它由树节点和父节点和子节点的引用链接到其他树节点组成。我想创建一个方法，它返回一个从叶节点到根节点或从根到叶的流。我已经实现了这一点，但我正在寻找一个解决方案，创建最少量的对象。优选没有。这里是我的代码：

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

流是会被大量使用，所以我想尽可能避免创建对象。迭代没有流的树结构是一件简单的事情。现在我只使用流的映射方法。我只需要一个方法，它需要一个Consumer，迭代深度并为每个节点调用消费者，并且不会创建对象，但是我会丢失所有流功能。这看起来像这样：

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

请勿使用流。使用你的替代品，其名称为：visitor pattern。

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

如果你绝对必须有一个流，让你的消费者或者收集列表中的节点然后流式处理，或者将消费者连接到迭代器的next()方法（使用一些代码使其行为正确）并使用StreamSupport将其转变为流。

Answer 2

我不同意你的性能问题，但是，有简化代码的空间，这可能会解决你的一些问题作为副作用。

你犯了一个开始于Iterator实现的常见错误，很可能是因为Iterator接口的老化和众所周知。但是做起来很麻烦，事实上，你并不需要在Spliterator包裹的Iterator，如果你只是实现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(); 
}