搜索樹(shù)是一個(gè)常見(jiàn)的操作，可分成深度搜索和廣度搜索。今天，本文將利用函數(shù)式開(kāi)發(fā)思想，不使用遞歸而僅用java8的stream類實(shí)現(xiàn)深度搜索和廣度搜索。（筆者建議，閱讀本文前，需對(duì)java8中stream操作有基礎(chǔ)性的了解。）
開(kāi)始之前，先創(chuàng)建一個(gè)樹(shù)節(jié)點(diǎn)。
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());
}
}
這是樹(shù)節(jié)點(diǎn)的類。每個(gè)節(jié)點(diǎn)可以有0，1，2個(gè)孩子。如果孩子不存在，則為null。
getChildren() 是用來(lái)返回節(jié)點(diǎn)的孩子集合。大致的實(shí)現(xiàn)原理是，先用左孩子和右孩子創(chuàng)建List，并stream這個(gè)List，然后用filter過(guò)濾掉null，然后收集（collect）剩下的數(shù)據(jù)到一個(gè)新的list并返回。
深度搜索
我們需要一個(gè)方法，返回一個(gè)含有所有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個(gè)list，分別存放已訪問(wèn)節(jié)點(diǎn)的list（visitedNodes）和待訪問(wèn)節(jié)點(diǎn)的list（unvisitedNodes）。開(kāi)始搜索前，先添加根節(jié)點(diǎn)到unvisitedNodes。
開(kāi)始循環(huán)訪問(wèn)unvisitedNodes中的節(jié)點(diǎn)。我們先取第一節(jié)點(diǎn)，作為當(dāng)前節(jié)點(diǎn)，然后把他的孩子節(jié)點(diǎn)進(jìn)行stream，過(guò)濾掉已訪問(wèn)過(guò)的，并收集回List。把這個(gè)List加到unvisitedNodes的開(kāi)頭。這樣做，就是為了深度搜索。最后將當(dāng)前節(jié)點(diǎn)加到visitedNodes中。
反復(fù)循環(huán)，直到unvisitedNodes中沒(méi)有節(jié)點(diǎn)，即表示搜索完成，返回visitedNodes作為結(jié)果。
廣度搜索
另寫(xiě)一個(gè)方法，返回一個(gè)含有所有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;
}
}
廣度搜索的開(kāi)始和深度搜索一樣，準(zhǔn)備了2個(gè)List。廣度搜索是按樹(shù)的層次來(lái)搜索新節(jié)點(diǎn)。所以的做法是找到當(dāng)前層次所對(duì)應(yīng)的下一個(gè)層次的所有節(jié)點(diǎn)，并把這些節(jié)點(diǎn)全部加到unvisitedNodes中。
我們使用map來(lái)得到下一層次的節(jié)點(diǎn)：
.map(Node::getChildren)
但是這里得到是類型是List<Node>的stream，故需使用flatMap，將其變成類型是Node的stream。在過(guò)濾掉已經(jīng)訪問(wèn)的節(jié)點(diǎn)之后，收集到的節(jié)點(diǎn)List作為unvistedNodes。而原來(lái)的unvistedNodes中的節(jié)點(diǎn)全部放置到visitedNodes中。
同樣，當(dāng)unvisitedNodes中沒(méi)有節(jié)點(diǎn)，即表示搜索完成，返回visitedNodes作為結(jié)果。
總結(jié)
使用了函數(shù)式思想的stream類之后，不論是代碼的可讀性還是簡(jiǎn)潔性上，都比不使用stream類好太多。
