将树形结构上的每个节点遍历出来

73 ·
0 ·
9天前
最新一次编辑的原因:

给出一组数:

135
1
12
122
134
123
13,

要求遍历出以下结果:

1
1-12-122
1-12-123
1-13-135
1-13-134
1-12
1-13

package com.upupor.framework.utils;

import com.google.common.collect.Lists;
import lombok.Data;
import org.springframework.util.CollectionUtils;
import org.springframework.util.StringUtils;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Demo
 *
 * @author YangRunkang(cruise)
 * @date 2021/11/20 23:21
 */
public class Demo {

    @Data
    public static class Node {
        private String id;

        private List<Node> children;

        private Node parent;

        public String getId() {
            return id;
        }

        public boolean hasParent() {
            return parent != null;
        }

        public Node(String id) {
            this.id = id;
        }

        public String getUpPath() {
            if (hasParent()) {
                return this.parent.getUpPath() + "-" + id;
            }
            return id;
        }

        public boolean hasChildren() {
            return !CollectionUtils.isEmpty(children);
        }


        public Node searChildren(List<Node> nodeList) {
            int length = this.getId().length();
            int childLength = length + 1;
            List<Node> childList = getChildrenNodes(nodeList, childLength);

            if (CollectionUtils.isEmpty(childList)) {
                return this.getParent();
            }
            this.setChildren(childList);
            for (Node child : childList) {
                child.setParent(this);
                child.searChildren(nodeList);
            }

            if (this.getParent() == null) {
                return this;
            }

            return this.getParent();
        }

        private List<Node> getChildrenNodes(List<Node> nodeList, int childLength) {
            int finalChildLength = childLength;
            List<Node> children = nodeList.stream()
                    .filter(a -> a.getId().length() == finalChildLength && a.getId().startsWith(this.getId()))
                    .collect(Collectors.toList());
            if (CollectionUtils.isEmpty(children)) {
                childLength = childLength + 1;
                Integer maxLen = nodeList.stream().map(Node::getId).map(String::length).max(Comparator.comparingInt(a -> a)).orElse(Integer.MAX_VALUE);
                if (childLength > maxLen) {
                    return Lists.newArrayList();
                }
                return getChildrenNodes(nodeList, childLength);
            }
            return children;
        }
    }

    public static void main(String[] args) {
        List<Node> nodeList = Lists.newArrayList(
                new Node("135"),
                new Node("1"),
                new Node("12"),
                new Node("122"),
                new Node("134"),
                new Node("123")
                , new Node("2")
                , new Node("24")
                , new Node("246")
                , new Node("13")
        );

        ArrayList<Node> originList = Lists.newArrayList(nodeList);

        // 按照id字符长度长短排序
        nodeList.sort(Comparator.comparingInt(a -> a.getId().length()));

        nodeList.stream()
                .map(Node::getId)
                .filter(s -> !StringUtils.isEmpty(s) && s.length() >= 1)
                .map(s -> s.substring(0, 1))
                .distinct()
                .forEach(s -> {
                    Node node = nodeList.stream().filter(n -> n.getId().equals(s)).findFirst().orElse(null);
                    if (!Objects.isNull(node)) {
                        Node nodeResult = node.searChildren(originList);
                        if (Objects.nonNull(nodeResult)) {
                            List<List<String>> lists = printResult(nodeResult);
                            lists.forEach(list -> list.forEach(System.out::println));
                        }
                    }

                });
    }

    private static List<List<String>> printResult(Node nodeResult) {
        List<List<String>> resultList = new ArrayList<>();

        if (!nodeResult.hasParent()) {
            ArrayList<String> rootList = new ArrayList<>();
            rootList.add(nodeResult.getId());
            resultList.addAll(Collections.singleton(rootList));
        }

        if (nodeResult.hasChildren()) {
            ArrayList<String> rootList = new ArrayList<>();
            for (Node child : nodeResult.getChildren()) {
                rootList.add(child.getUpPath());
                resultList.addAll(printResult(child));
            }
            resultList.addAll(Collections.singleton(rootList));
        }
        return resultList;
    }

}

再加一个数 1227结果如下:

1
1-12-122-1227 ---测试通过
1-12-122
1-12-123
1-13-135
1-13-134
1-12
1-13


本作品系原创,采用《署名-非商业性使用-禁止演绎4.0 国际》许可协议.转载请说明出处
本文链接:https://www.upupor.com/u/21112109163830979584 复制

无评论内容,快来评论吧

推荐阅读