[java8]如何用函数式思想来解决树搜索
搜索树是一个常见的操作，可分成深度搜索和广度搜索。今天，本文将利用函数式开发思想，不使用递归而仅用java8的stream类实现深度搜索和广度搜索。（笔者建议，阅读本文前，需对java8中stream操作有基础性的了解。）
java8函数式开发
开始之前，先创建一个树节点。
public class Node {
private Node left;
private Node right;
private String label;
public Node(String label, Node left, Node right) {
this.left = left;
this.right = right;
this.label = label;
}
public List<Node> getChildren() {
return Stream.of(left, right)
.filter(Objects::nonNull)
.collect(Collectors.toList());
}
}
这是树节点的类。每个节点可以有0，1，2个孩子。如果孩子不存在，则为null。
getChildren() 是用来返回节点的孩子集合。大致的实现原理是，先用左孩子和右孩子创建List，并stream这个List，然后用filter过滤掉null，然后收集（collect）剩下的数据到一个新的list并返回。
深度搜索
我们需要一个方法，返回一个含有所有node的List，顺序是深度搜索的顺序：
public class Node {
//...
public List<Node> searchByDepth() {
List<Node> visitedNodes = new LinkedList<>();
List<Node> unvisitedNodes = Arrays.asList(this);
while(!unvisitedNodes.isEmpty()) {
Node currNode = unvisitedNodes.remove(0);
List<Node> newNodes = currNode.getChildren()
.stream()
.filter(node -> !visitedNodes.contains(node))
.collect(Collectors.toList());
unvisitedNodes.addAll(0, newNodes);
visitedNodes.add(currNode);
}
return visitedNodes;
}
}
我们有2个list，分别存放已访问节点的list（visitedNodes）和待访问节点的list（unvisitedNodes）。开始搜索前，先添加根节点到unvisitedNodes。
开始循环访问unvisitedNodes中的节点。我们先取第一节点，作为当前节点，然后把他的孩子节点进行stream，过滤掉已访问过的，并收集回List。把这个List加到unvisitedNodes的开头。这样做，就是为了深度搜索。最后将当前节点加到visitedNodes中。
反复循环，直到unvisitedNodes中没有节点，即表示搜索完成，返回visitedNodes作为结果。
广度搜索
另写一个方法，返回一个含有所有node的List，顺序是广度搜索的顺序：
public class Node {
//...
public List<Node> searchByBreadth() {
List<Node> visitedNodes = new LinkedList<>();
List<Node> unvisitedNodes = Arrays.asList(this);
while(!unvisitedNodes.isEmpty()) {
List<Node> newNodes = unvisitedNodes
.stream()
.map(Node::getChildren)
.flatMap(List::stream)
.filter(node -> !visitedNodes.contains(node))
.collect(Collectors.toList());
visitedNodes.addAll(unvisitedNodes);
unvisitedNodes = newNodes;
}
return visitedNodes;
}
}
广度搜索的开始和深度搜索一样，准备了2个List。广度搜索是按树的层次来搜索新节点。所以的做法是找到当前层次所对应的下一个层次的所有节点，并把这些节点全部加到unvisitedNodes中。
我们使用map来得到下一层次的节点：
.map(Node::getChildren)
但是这里得到是类型是List<Node>的stream，故需使用flatMap，将其变成类型是Node的stream。在过滤掉已经访问的节点之后，收集到的节点List作为unvistedNodes。而原来的unvistedNodes中的节点全部放置到visitedNodes中。
同样，当unvisitedNodes中没有节点，即表示搜索完成，返回visitedNodes作为结果。
总结
使用了函数式思想的stream类之后，不论是代码的可读性还是简洁性上，都比不使用stream类好太多。
