如何将树结构转换为java中的节点流

Question

我想在Java8节点流中转换树

这是存储可以选择的数据的节点树

public class SelectTree<D> {

  private D data;

  private boolean selected = false;

  private SelectTree<D> parent;

  private final List<SelectTree<D>> children = new ArrayList<>();

  public SelectTree(D data, SelectTree<D> parent) {
    this.data = data;
    if (parent != null) {
      this.parent = parent;
      this.parent.getChildren().add(this);
    }
  }

  public D getData() {
    return data;
  }

  public void setData(D data) {
    this.data = data;
  }

  public boolean isSelected() {
    return selected;
  }

  public void setSelected(boolean selected) {
    this.selected = selected;
  }

  public SelectTree<D> getParent() {
    return parent;
  }

  public void setParent(SelectTree<D> parent) {
    this.parent = parent;
  }

  public List<SelectTree<D>> getChildren() {
    return children;
  }

  public boolean isRoot() {
    return this.getParent() == null;
  }

  public boolean isLeaf() {
    return this.getChildren() == null || this.getChildren().isEmpty();
  }
}

我想获得所选数据的集合

我想做那样的事情：

  public static void main(String[] args) {
    SelectTree<Integer> root = generateTree();

    List<Integer> selectedData = root.stream()
            .peek(node -> System.out.println(node.getData()+": "+node.isSelected()))
            .filter(node-> node.isSelected())
            .map(node-> node.getData())
            .collect(Collectors.toList()) ;

    System.out.println("\nselectedData="+selectedData);
  }

  private static SelectTree<Integer> generateTree() {
    SelectTree<Integer> n1 = new SelectTree(1, null);
    SelectTree<Integer> n11 = new SelectTree(11, n1);
    SelectTree<Integer> n12 = new SelectTree(12, n1);
    n12.setSelected(true);
    SelectTree<Integer> n111 = new SelectTree(111, n11);
    n111.setSelected(true);
    SelectTree<Integer> n112 = new SelectTree(112, n11);
    SelectTree<Integer> n121 = new SelectTree(121, n12);
    SelectTree<Integer> n122 = new SelectTree(122, n12);
    return n1;
  }

问题是找到stream()的实现，我想我可以帮助一些人分享我的解决方案，我会知道是否存在一些问题或更好的方法。

起初它是针对TreeNode的素​​面，但我将问题概括为各种树木

Answer 1

kwisatz答案的一小部分补充。

这个实现：

this.getChildren().stream()
        .map(SelectTree::stream)
        .reduce(Stream.of(this), Stream::concat);

会更加渴望，我。即在流创建期间将遍历整个层次结构。如果你的hirarchy很大，让我们说，你正在寻找一个匹配某个谓词的单个节点，你可能想要一个更懒惰的行为：

Stream.concat(Stream.of(this),
              this.getChildren().stream().flatMap(SelectTree::stream));

在这种情况下，在流创建期间仅检索根节点的子节点，并且搜索节点不一定会导致遍历整个层次结构。

两种方法都将展示DFS迭代次序。

Answer 2

我发现这个stream()的实现是一个DFS树遍历：

public class SelectTree<D> {

  //...

  public Stream<SelectTree<D>> stream() {
    if (this.isLeaf()) {
      return Stream.of(this);
    } else {
      return this.getChildren().stream()
                .map(child -> child.stream())
                .reduce(Stream.of(this), (s1, s2) -> Stream.concat(s1, s2));
    }
  }
}

如果你不能改变像primefaces TreeNode（org.primefaces.model.TreeNode）那样的树实现，你可以在另一个类中定义一个方法：

  public Stream<TreeNode> stream(TreeNode parentNode) {
    if(parentNode.isLeaf()) {
      return Stream.of(parentNode) ;
    } else {
      return parentNode.getChildren().stream()
                .map(childNode -> stream(childNode))
                .reduce(Stream.of(parentNode), (s1, s2) -> Stream.concat(s1, s2)) ;
    }
  }

Answer 3

使用任何节点类的更通用的方法是为方法添加一个参数，该参数返回子节点：

public class TreeNodeStream {
  public static <T> Stream<T> of(T node, Function<T, Collection<? extends T>> childrenFunction) {
  return Stream.concat( //
    Stream.of(node), //
    childrenFunction.apply(node).stream().flatMap(n -> of(n, childrenFunction)));
  }
}

使用File的示例：

TreeNodeStream.of(
  new File("."), f -> f.isDirectory() ? Arrays.asList(f.listFiles()) :
                                        Collections.emptySet())
  .filter(f -> f.getName().endsWith(".java"))
  .collect(Collectors::toList);