当我构建嵌套集时，如何获取非叶节点的右侧值

Question

我正在尝试使用非递归深度优先搜索方法来读取目录并构建嵌套集。我需要为给定目录的路径分配左、右和深度值（同一目录级别的文件不分先后）。 现在我已经完成了叶子节点的深度、左侧和右侧的分配。但我对如何获取非叶节点的右侧值感到困惑。

这是我希望实现的目标，也是我已经完成的：

A：给定一个目录，其中 |== 代表文件夹； |-- 代表文件。 （可以替换成自己的目录）

 |==resources
            |==data
                  |==table_design
            |==mapper
                  |==server
                        |--ServerMapper.xml
                  |==source
                  |--AMapper.xml
            |--bootstrap.properties
            |--logback-spring.xml

B: 预期结果

0   1|||\resources|||20
1   2|||\resources\data||5
2   3|||\resources\data\table_design|||4
1   6|||\resources\mapper|||15
2   7|||\resources\mapper\server|||10
3   8|||\resources\mapper\server\ServerMapper.xml|||9
2   11|||\resources\mapper\source|||12
2   13|||\resources\mapper\AMapper.xml|||14
1   16|||\resources\bootstrap.properties|||17
1   18|||\resources\logback-spring.xml|||19

C： 我的实现

1. 实体

  static class MyObject {

        private int left;
        private int right;
        private int depth;
        private String path;
    }

2. 我的深度优先搜索逻辑

  private static void dfs(File root) {
        if (root == null) {
            return;
        }
        int depth = 0;
        int index = 1;
        Stack<File> stack = new Stack<>();
        //Indicates whether the node has been pushed onto the stack
        Map<File, MyObject> map = new LinkedHashMap<>();
        stack.add(root);
        MyObject rootObj = new MyObject();
        rootObj.setPath(root.getAbsolutePath());
        rootObj.setDepth(depth);
        rootObj.setLeft(index++);
        map.put(root, rootObj);
        while (!stack.isEmpty()) {
            File cur = stack.pop();
            depth--;
            File[] files = cur.listFiles();
            if (files != null) {
                //Execute as soon as the next node is found
                for (File next : files) {
                    //The next node is pushed if it has not been accessed
                    if (!map.containsKey(next)) {
                        depth++;
                        stack.push(cur);
                        depth++;
                        stack.push(next);
                        MyObject obj = new MyObject();
                        obj.setLeft(index++);
                        obj.setPath(next.getAbsolutePath());
                        obj.setDepth(depth);
                        if (!next.isDirectory()) {
                            obj.setRight(index++);
                        }
                        map.put(next, obj);
                        break;
                    }
                }
            }
        }

        System.out.println("depth" + "\t left|||path|||right");
        for (MyObject value : map.values()) {
            System.out.println(value.getDepth() + "\t" + value.getLeft() + "|||" + value.getPath() + "|||" + value.getRight());
        }
    }
    

3. 我的输出

0   1|||\resources|||0
1   2|||\resources\bootstrap.properties|||3
1   4|||\resources\data|||0
2   5|||\resources\data\table_design|||6
1   7|||\resources\logback-spring.xml|||8
1   9|||\resources\mapper|||0
2   10|||\resources\mapper\server|||0
3   11|||\resources\mapper\server\UserMapper.xml|||12
2   13|||\resources\mapper\source|||0
2   14|||\resources\mapper\SourceJobMapper.xml|||15

Answer 1

我完成了数据的构建。

 public static Map<File, NestedSetObj> dfs2NestedSets(File root) {
        if (root == null) {
            return new HashMap<>(0);
        }

        //Record depth pop -1, push +1
        long depth = 0L;
        //Left and right values
        long index = 1L;
        Deque<File> stack = new ArrayDeque<>();
        stack.push(root);

        //The global collection of objects, which also indicates whether the object has been pushed.
        Map<File, NestedSetObj> map = new LinkedHashMap<>();
        //Root directory, directly give the value
        NestedSetObj rootObj = NestedSetObj.builder().path(root.getAbsolutePath()).depth(depth).left(index++).build();
        map.put(root, rootObj);

        while (!stack.isEmpty()) {
            File cur = stack.pop();
            depth--;
            File[] files = cur.listFiles();
            if (files != null) {
                //Execute as soon as the next node is found
                for (File next : files) {
                    //The next node is executed if it has not been accessed
                    if (!map.containsKey(next)) {
                        //The current node and the next node are pushed
                        depth++;
                        stack.push(cur);
                        depth++;
                        stack.push(next);
                        //On each first access, the node is assigned the value left
                        NestedSetObj obj = NestedSetObj.builder().left(index++).path(next.getAbsolutePath()).depth(depth).build();
                        boolean leaf = !next.isDirectory();
                        boolean emptyDirLeaf = next.listFiles() != null && next.listFiles().length == 0;
                        //Assign right directly to leaf nodes or empty directories
                        if (leaf || emptyDirLeaf) {
                            obj.setRight(index++);
                        }
                        map.put(next, obj);
                        break;
                    }
                }

                //Determine whether the right side of the leaf node needs to be assigned
                //We believe that the current directory can be assigned only if all sub-levels of data in the current directory have a value of RIGHT 
                long min = Long.MAX_VALUE;

                for (File file : files) {
                    NestedSetObj childObject = map.get(file);
                    if (childObject == null) {
                        min = 0L;
                        break;
                    }
                    min = Math.min(min, childObject.getRight());
                }

                //Assign a value to the right of a non-leaf node；
                //If all level 1 child nodes have the right node value, index plus 1 is the right node value of the current node.  
                if (min > 0L && Long.MAX_VALUE != min) {
                    NestedSetObj curObj = map.get(cur);
                    if (curObj.right == 0L) {
                        curObj.setRight(index++);
                    }
                }
            }
        }
        //Rvalue of the root directory = Number of nodes x 2
        rootObj.setRight(map.size() * 2L);
        return map;
    }