[tree structure]: the directory structure for querying the complete path through multiple vertices

Demand background:

Recently, in the data R & D platform, there is a search related demand: users can do fuzzy search through the Job name, return the relevant result set, and carry out the complete directory structure. The directory structure of the R & D platform is divided into four types: the root node is the workspace, the sub node has multi-layer nested folders, the folder contains DAG workflow, and the workflow contains Job tasks; The requirement is to return the complete directory structure to the front end.


This problem is very interesting. The first point is the tree structure. Because it is a fuzzy search, there may be multiple returned jobs. If you traverse, there may be multiple complete directory structures. At this time, path merging is required, which is very difficult; I modified the tree structure, and the following code is directly:


The key of the current node and the key of the parent node must be unique;

The text field represents other fields of the current Node, which are put into the Map collection

children refers to the child nodes of the current Node, and the structure is the array collection of SearchNode;

When making toString, it is directly converted to JSON format, and the data in the Map set is also solved. Here is a problem:

Because the value of Map is of Object type, I directly use regular matching to match the number type here, without double quotation marks, and if it is of Boolean type, without double quotation marks;

public class SearchNode {
    private String  key;
    private String  parentKey;
    private Map<String,Object> text;

    private List<SearchNode> children;

    private String regex = "([1-9]\\d*\\.?\\d*)|(0\\.\\d*[1-9])";

    public SearchNode(String key, String parentKey, Map<String,Object> text) {
        this.key = key;
        this.parentKey = parentKey;
        this.text = text;

    public String toString() {
        final StringBuilder sb = new StringBuilder("{");
        text.forEach((k,v) -> {
            Pattern compile = Pattern.compile(regex);
            Matcher matcher = compile.matcher(v.toString());
            if (matcher.matches()) {
            } else {
                if (v.equals(true) || v.equals(false)) {
                } else {
        return sb.toString();


Here we use the idea of recursion to obtain the tree structure, but our requirement background is to splice it into a completed directory structure rather than multiple structures, so we choose Set to duplicate the idea and kill the repeated searchnodes

public class SearchTree {

    private HashSet<SearchNode> searchNodeList = new HashSet<>();
    public SearchTree(HashSet<SearchNode> searchNodeList) {
        this.searchNodeList = searchNodeList;

    //Establish tree structure
    public HashSet<SearchNode> builTree(){
        HashSet<SearchNode> treeSearchNodes =new  HashSet<SearchNode>();
        for(SearchNode searchNodeNode : getRootNode()) {
            searchNodeNode =buildChilTree(searchNodeNode);
        return treeSearchNodes;

    //Recursion, establish subtree structure
    private SearchNode buildChilTree(SearchNode pNode){
        List<SearchNode> chilSearchNodes =new  ArrayList<SearchNode>();
        for(SearchNode searchNodeNode : searchNodeList) {
            if(searchNodeNode.getParentKey().equals(pNode.getKey())) {
        return pNode;

    //Get root node
    private List<SearchNode> getRootNode() {
        List<SearchNode> rootSearchNodeLists =new  ArrayList<SearchNode>();
        for(SearchNode searchNodeNode : searchNodeList) {
            if(searchNodeNode.getParentKey().equals("head")) {
        return rootSearchNodeLists;


Test results:

public class SearchNodeTests {

    public void contextLoads() {
        HashSet<SearchNode> menuList= new HashSet<>();
        HashMap<String, Object> map1 = new HashMap<>();
        map1.put("local","Hubei province");

        HashMap<String, Object> map2 = new HashMap<>();
        map2.put("local","Shandong Province");
        HashMap<String, Object> map3 = new HashMap<>();
        HashMap<String, Object> map4 = new HashMap<>();
        map4.put("local","Xiantao City");
        HashMap<String, Object> map5 = new HashMap<>();
        HashMap<String, Object> map6 = new HashMap<>();
        map6.put("local","Wuchang District");
        HashMap<String, Object> map7 = new HashMap<>();
        map7.put("local","Hongshan District");
        HashMap<String, Object> map8 = new HashMap<>();
        map8.put("local","Hongshan Street");
        /*Insert some data*/
        menuList.add(new SearchNode("1","head",map1));
        menuList.add(new SearchNode("7","head",map2));
        menuList.add(new SearchNode("2","1",map3));
        menuList.add(new SearchNode("3","1",map4));

        menuList.add(new SearchNode("8","7",map5));
        menuList.add(new SearchNode("4","2",map6));
        menuList.add(new SearchNode("5","2",map7));
        menuList.add(new SearchNode("6","4",map8));

        /*Let's create a tree*/
        SearchTree menuTree =new SearchTree(menuList);
        /*Turn to json to see the effect*/
        String jsonOutput= JSON.toJSONString(menuList);
        System.out.println("Tree data:"+menuList.toString());

        System.out.println("Everything in the tree id"+ this.list);//Get all nodes in the tree

    List<Menu> children=null;
    //Parameter 1: tree structure parameter 2: node id
    public List<Menu> recursion (Menu tree, int node){
        if(tree.getId()==node){     //Node id = ID to query
            children = tree.getChildren();  //Get the data return from children
        }else {
            for(Menu bean:tree.getChildren()){     //On the contrary, recursive data in children
        return children;

    List<Long> list = new ArrayList<Long>();//Initialize id set
    //Get all nodes in the tree and remember to clear the list before calling the method
    public void getAllNode(Menu tree) {
        list.add((long) tree.getId());//Add node
        if (tree.getChildren() != null) {//Determine whether there are child nodes
            for (Menu bean : tree.getChildren()) {//Cyclic recursive child node


Tags: Java Spring Boot data structure Back-end

Posted by TipPro on Fri, 20 May 2022 07:42:29 +0300