用javascript打印层次树结构

Question

我正在处理一个问题，在给定一组文件路径的情况下，我想打印文件结构。例如，对于给定的数组["/a/b/c", "a/a/a", "/a/b/d"]，理想的结构看起来像：

a
b
c
d
a
a

但我的结构最终看起来更像这样：

a
b
c
a
a
a
b

据我所知，这是由于我的树没有识别树中何时已经存在节点造成的。因此，它添加了节点"；a"；三次，而不是认识到；a"；已经存在并正在遍历。

let paths = ["/a/b/c", "a/a/a", "/a/b/d"]
class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}

addChild(element) {
this.children.push(element)
}
}
const head = new TreeNode('Head');
let cur = head;
paths.forEach(element => {
cur = head;
let filePath = element.split('/');
filePath.shift();

filePath.forEach(element => {
let newNode = new TreeNode(element);
if(!cur.children.includes(newNode)) {
cur.addChild(newNode);
cur = cur.children[cur.children.length - 1];
} else {
cur = cur.children.indexOf(newNode);
}
})
})
var spaceAppend = function(num) {
let i = 0;
let space = "";
while(i < num) {
space += " ";
i++;
}
return space;
}
var traverse = function(node, level = 0){
if(node === null)
return;
console.log(spaceAppend(level), node.value)
if(node.children) {
for(const n of node.children) {
traverse(n, level + 1);
}
}
}
traverse(head)

我的树实现有问题吗？

Answer 1

一些问题：

• .includes()不是找到匹配值的正确方法。请改用.find()
• .indexOf()将返回一个索引，因此这不是您想要在else块中分配给cur的正确值
• 当CCD_ 7不以CCD_ 8开始时。您可以使用.match()而不是.split()来简化处理，这样您就可以准确地获得路径的非空部分

问题不大：

• 没有必要在外循环之外定义cur
• JavaScript有一个类似spaceAppend的原生函数。您可以使用.repeat()
• 当您实际上不需要new TreeNode(element)时，也会调用它。只有当您知道没有匹配的节点时，才能创建一个新节点
• 您可以用.reduce()替换内部的.forEach()循环，这为cur变量提供了更好的范围处理

这是您的代码，其中考虑了这些备注：

class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}

addChild(element) {
this.children.push(element);
}
}
let paths = ["/a/b/c", "a/a/a", "/a/b/d"];
const head = new TreeNode('Head');
paths.forEach(element => {
// Use .match() to only get non-empty elements
let filePath = element.match(/[^/]+/g);

filePath.reduce((cur, element) => {
// Use .find() instead of .includes()
let node = cur.children.find(child => child.value === element);
// Only create the node when needed:
if (!node) {
node = new TreeNode(element);
cur.addChild(node);
}
// Walk down one step in the tree
return node; // ...becomes the value of `cur`
}, head); // Initial value of reduction
});
const traverse = function(node, level=0) {
if (node === null) return;
// Use .repeat():
console.log(" ".repeat(level), node.value);
if (node.children) {
for (const n of node.children) {
traverse(n, level + 1);
}
}
}
traverse(head);

Answer 2

启动器阵列是["/a/b/c", "/a/a/a", "/a/b/d"]("/a/a/a"而不是("a/a/a")？

我认为你遇到的问题的关键是线路

if(!cur.children.includes(newNode)) { ... }

创建新节点时，即使它具有与上一个相同的value，在比较两个TreeNode对象时也不会导致公平。您需要比较节点的value，而不是节点本身。

因此，有一个简化版本的节点对象示例：

class TreeNode {
constructor(value) {
this.value = value;
}
}
a1 = new TreeNode('a');
a2 = new TreeNode('a');
console.log("a1 == a2");
console.log(a1 == a2); // false
console.log("a1.value == a2.value");
console.log(a1.value == a2.value); // true

我用一个比较values而不是TreeNode对象的循环调整了内部forEach循环

filePath.forEach(element => {
let newNode = new TreeNode(element);
let tempNode = null;
for (var i = 0; i < cur.children.length; i++) {
if (cur.children[i].value == newNode.value) {
tempNode = cur.children[i];
}
}
if (tempNode == null) {
cur.addChild(newNode);
cur = newNode;
} else {
cur = tempNode;
}
});

代码笔上的完整代码片段

javascript中的对象平等处理起来不是特别好。有关更多信息，请参阅其他答案

Answer 3

这里有一个使用lodash和对象树化的解决方案。虽然它是更简单的代码，但引入额外的依赖关系显然是有代价的。

该解决方案首先将路径转换为树结构，然后使用对象树化进行可视化

// const lodash = require('lodash');
// const objectTreeify = require('object-treeify');
const myPaths = ['/a/b/c', 'a/a/a', '/a/b/d'];
const treeify = (paths) => objectTreeify(paths.reduce((p, c) => {
lodash.set(p, c.match(/[^/]+/g));
return p;
}, {}), {
spacerNoNeighbour: ' ',
spacerNeighbour: ' ',
keyNoNeighbour: '',
keyNeighbour: ''
});
console.log(treeify(myPaths));
/* =>
a
b
c
d
a
a
*/

.as-console-wrapper {max-height: 100% !important; top: 0}

<script src="https://bundle.run/lodash@4.17.20"></script>
<script src="https://bundle.run/object-treeify@1.1.31"></script>

免责声明：我是object treeify 的作者