在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(); 
}