在树结构中find所有独特的path

假设我有一个文本文件中的目录结构

root1 child1 child2 grandchild1 grandchild2 child3 root2 child1 child2 grandchild1 greatgrandchild1 

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

 [ [ "root1", "child1" ], [ "root1", "child2", "grandchild1" ], [ "root1", "child2", "grandchild2" ], [ "root1", "child3" ], [ "root2", "child1" ], [ "root2", "child2", "grandchild1", "greatgrandchild1" ] ] 

编辑

进一步,但仍然有问题recursion地穿过树

 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数组:

在这里输入图像说明

我懒得看你的algorithm: – |

 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中使用这个string:

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

(回答我自己的问题)

那么实现实际上有三个部分:(1)将文本文件转换为树结构,然后(2)在树上使用dfs来查找唯一path,最后(3)将所有path合并成单个数组。

首先是文本到树型转换器。 您仍然需要find每个项目的深度(缩进级别),因为这决定了它是一个孩子还是兄弟姐妹:

 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。 这个algorithm一次只search一棵树,所以如果你的目录结构有多个根,你需要把它放在一个循环中。

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