您的位置:澳门新葡萄京最大平台 > 最大平台 > 如何用函数式思想来解决树搜索

如何用函数式思想来解决树搜索

发布时间:2019-11-15 16:25编辑:最大平台浏览(126)

    搜寻树是一个周围的操作,可分为深度寻找和广度找出。前不久,本文将运用函数式开拓合计,不采用递归而仅用java8的stream类完成深度寻觅和广度找寻。(小编建议,阅读本文前,需对java第88中学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

    本文由澳门新葡萄京最大平台发布于最大平台,转载请注明出处:如何用函数式思想来解决树搜索

    关键词: