美学原理[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类好太多。

卓殊感谢您的阅读!您的留言、打赏、点赞、关注、分享,对作者最大的鼓励:P