查找树结构中的所有唯一路径

Question

比方说，我有一个文本文件，制定了一个目录结构

root1 
    child1 
    child2 
     grandchild1 
     grandchild2 
    child3 
root2 
    child1 
    child2 
     grandchild1 
      greatgrandchild1 

我怎样才能把上面的树结构成一个嵌套的数组，看起来像这样：

​​

编辑

获取进一步的，但仍然有问题通过递归树走

var $text = '' 
+ 'root1\n' 
+ ' r1 child1\n' 
+ ' r1 child2\n' 
+ ' r1 grandchild1\n' 
+ ' r1 grandchild2\n' 
+ ' r1 child3\n' 
+ 'root2\n' 
+ ' r2 child1\n' 
+ ' r2 c1\n' 
+ '  r2 c1 g1\n' 
+ ' r2 child2\n' 
+ ' r2 grandchild1\n' 
+ '  r2 greatgrandchild1\n' 
+ 'test!\n' 
+ 'root3\n' 
+ ' r3 child1\n' 
+ ' r3 c1\n' 
+ '  r3 c1 g1\n' 
+ ' r3 child3\n' 
+ ' r3 grandchild1\n' 
+ '  r3 greatgrandchild1'; 

var dirGen = (function(trees) { 
    "use strict"; 

    var indent = /[\s\t]/g; 
    var lTrim = /[\s\t]*/; 
    var $trees = decompose(trees); 
    var $root = []; 

    function init() { 
    var paths = $trees.map(treeMap) 
    $test(paths); 
    } 

    function treeMap(tree, n, arr) { 
    var base = new LinkedList(); 
    return bfs(-1, tree, base); 
    } 

    function bfs(n, tree, base) { 
    var l, t; 
    n++; 
    //base case 
    if (n === tree.length) return trails(base); 
    l = tree.length; 
    t = tree[n]; 
    var cur = { label: t.replace(lTrim, ""), depth: depth(t), children: [] }; 
    //set root 
    if (n === 0) { 
     base.tree = cur; 
     return bfs(n, tree, base); 
    } 

    base.push(cur); 

    return bfs(n, tree, base); 

    } 

    function depth(str) { 
    var d = str.match(indent); 
    if (d === null) return 0; 
    return d.length; 
    } 

    function trails(arr) { 
    return arr; 
    } 

    function LinkedList() {} 

    LinkedList.prototype.push = function(node) { 
    var l = this.tree.children.length; 
    var j = l - 1; 
    if (l === 0) { 
     this.tree.children.push(node); 
     return; 
    } 
    //walk through children array in reverse to get parent 
    while (j > -1) { 
     var d = this.tree.children[j].depth; 
     //child 
     if (node.depth > d) { 
     console.log(this.tree.children[j], node) 
     return this.tree.children[j].children.push(node); 
     } 
     //sibling 
     if (node.depth === d) { 

     } 

     j--; 
    } 

    } 

    function decompose(arr) { 
    var treeBreak = /[\r\n](?=\w)/gm; 
    var lines = /[\r\n]+(?!\s)*/g; 
    return arr.split(treeBreak).map(function(str) { 
     return str.split(lines) 
    }); 
    } 

    function $test(str) { 
    var json = JSON.stringify(str, null, 2); 
    var wtf = "<pre>" + json + "</pre>"; 
    document.write(wtf); 
    } 

    return init; 

})($text); 

dirGen(); 

到目前为止的代码让我这个JSON数组：

Answer 1

（回答我的问题） （1）将文本文件转换为树形结构，然后（2）在树上使用dfs来查找唯一路径，最后（3）将所有路径合并到单个数组中。

一，文字转换树。你仍然需要找到每个项目的深度（缩进级别），因为这是确定它是否是一个孩子或兄弟姐妹：

var treeGrapher = (function() { 
    "use strict"; 

    var find = require("lodash.find"); 

    var indent = /[\s\t]/g; 
    var lTrim = /[\s\t]*/; 
    var treeBreak = /[\r\n](?=\w)/gm; 
    var lines = /[^\r\n]+/g 

    function init(text) { 
    return decompose(text).map(function(tree) { 
     return populate(-1, tree, {}) 
    }); 
    } 

    function depth(str) { 
    var d = str.match(indent); 
    if (d === null) return 0; 
    return d.length; 
    } 

    function decompose(txt) { 
    return txt.split(treeBreak).map(function(str) { 
     return str.match(lines); 
    }); 
    } 

    function populate(n, tree, root, cache, breadCrumbs) { 
    var branch, leaf, crumb; 
    //set index 
    n++; 
    //root case 
    if (n === tree.length) return root.tree; 

    branch = tree[n]; 
    leaf = { label: branch.replace(lTrim, ""), index: n, depth: depth(branch), children: [] }; 
    breadCrumbs = breadCrumbs || []; 
    crumb = cache ? { label: cache.label, index: cache.index, depth: cache.depth, node: cache } : undefined; 

    //set root 
    if (n === 0) { 
     root.tree = leaf; 
     return populate(n, tree, root, leaf, breadCrumbs); 
    } 

    //push child to cached parent from previous iteration 
    if (leaf.depth > cache.depth) { 
     cache.children.push(leaf); 
     root.parent = cache; 
     breadCrumbs.push(crumb) 
     return populate(n, tree, root, leaf, breadCrumbs); 
    } 

    //push child to distant parent via breadcrumb search 
    if (leaf.depth <= cache.depth) { 
     var rev = breadCrumbs.slice(0).reverse(); 
     var parentNode = find(rev, function(obj){ return obj.depth < leaf.depth }).node; 
     parentNode.children.push(leaf); 
     return populate(n, tree, root, leaf, breadCrumbs); 
    } 

    } 

    return init; 

})(); 

module.exports = treeGrapher; 

然后，DFS。这个算法一次只搜索一棵树，所以如果你的目录结构有多个根，你需要把它放在一个循环中。

var uniquePaths = (function() { 
    "use strict"; 

    function init(tree) { 
    return walk(tree, [], []); 
    } 

    function walk(branch, path, basket) { 
    var fork = path.slice(0); 
    var i = 0; 
    var chld = branch.children; 
    var len = chld.length; 
    fork.push(branch.label); 
    if (len === 0) { 
     basket.push(fork); 
     return basket; 
    } 
    for (i; i < len; i++) walk(chld[i], fork, basket); 
    return basket; 
    } 

    return init; 

})(); 

module.exports = uniquePaths; 

把它们放在一起应该是这样的：

directory.tmpl.txt

root1 
    child1 
    child2 
     gc1 
root2 
root3 
    root3-child1  

main.js

var fs = require("fs"); 
var treeGrapher = require("./lib/treeGrapher.js"); 
var uniquePaths = require("./lib/uniquePaths.js"); 

var tmpl = fs.readFileSync("./director.tmpl.txt", "utf8"); 
var graphs = treeGrapher(tmpl); //returns an array of trees 
var paths = arrange(graphs); 

/**  
[ 
    [ "root1", "rootchild1" ], 
    [ "root1", "child2", "gc1" ], 
    [ "root2" ], 
    [ "root3", "root3-child1" ] 
] 
*/ 

function arrange(trees) { 
    var bucket = []; 
    trees.forEach(function(list) { 
     uniquePaths(list).forEach(function(arr) { 
      bucket.push(arr); 
     }); 
    }); 
    return bucket; 
} 

Answer 2

我懒得看你的算法： - |

function populateTree (tree, text) { 
    var rTab, rChunks, rChunk; 
    var chunks, chunk; 
    var i, l, node; 
    if (!text) return; 
    rTab = /^\s{4}/gm; 
    rChunks = /[\r\n]+(?!\s{4})/g; 
    rChunk = /^(.+)(?:[\r\n]+((?:\r|\n|.)+))?$/; 
    chunks = text.split(rChunks); 
    l  = chunks.length; 
    for (i = 0; i < l; i++) { 
     chunk = chunks[i].match(rChunk); 
     node = { label: chunk[1], children: [] }; 
     tree.children.push(node); 
     populateTree(node, chunk[2] && chunk[2].replace(rTab, '')); 
    } 
} 

function printTree(tree, prefix) { 
    var i, l = tree.children.length; 
    for (i = 0; i < l; i++) { 
     console.log(prefix + tree.children[i].label); 
     printTree(tree.children[i], prefix + ' '); 
    } 
} 

用法：

var tree = { children: [] }; 
populateTree(tree, text); 
printTree(tree, ''); 

我不熟悉的NodeJS，我只能告诉大家，它工作在Chrome与此字符串：

var text = '' 
+ 'root1\n' 
+ ' child1\n' 
+ ' child2\n' 
+ '  grandchild1\n' 
+ '  grandchild2\n' 
+ ' child3\n' 
+ 'root2\n' 
+ ' child1\n' 
+ ' child2\n' 
+ '  grandchild1\n' 
+ '   greatgrandchild1';