gpt4 book ai didi

java - 在树结构上创建深度流

转载 作者:行者123 更新时间:2023-11-30 08:38:18 26 4
gpt4 key购买 nike

因此,我有一个基本的树结构,由树节点组成,这些树节点通过父子引用链接到其他树节点。我想创建一个返回 Stream 的方法,该 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
  • 我创建自己的 Iterator 实现以传递给 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 应该实现或扩展一些接口(interface)/类吗?让我知道是否有任何不清楚的地方。

谢谢!

最佳答案

不要使用流。使用您的替代方案,它有一个名称:visitor pattern .

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

如果你绝对必须有一个流,让你的消费者要么收集列表中的节点然后流式传输,要么将消费者连接到迭代器的 next() 方法(使用一些代码使其正常运行)并使用 StreamSupport 将其转换为流。

关于java - 在树结构上创建深度流,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36643297/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com