查找樹結構中的所有唯一路徑

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';