树遍历优化

Question

我在JavaScript中使用嵌套的对象是一个简单的树数据结构，

class Node { 
    name: "", 
    children: [ 
     ...Node 
    ] 
} 

rootNode=[Node, Node, Node...] 

现在，

我遍历树，并找到匹配的谓词像所有的节点，

let result =[]; 
let allNodes =[]; 
if isArray(rootNode) { 
    rootNode.each(x=>{ 
     allNodes.push(x) 
    }); 
} else { 
    allNodes.push(rootNode); 
} 

while (allNodes.length) { 
    let currentNode = allNodes.shift(); 
    if (predicate(currentNode) { 
      result.push(currentNode); 
    } 
    if (currentNode.children.length) { 

     allNodes.push(addAllChild(currentNode.children)) 
    } 

} 

有没有有效的方法做到以上？

Answer 1

您可以尝试递归执行此操作，因为您无需按特定顺序执行操作。在这里，您没有在allNodes中存储所有节点引用的开销，并且由于尾部调用优化，此代码可能会比迭代代码运行得更快：

var result = []; 
function traverse(curr) { 
    if(predicate(curr)) { 
     result.push(curr); 
    } 
    for(var i=0; i < curr.children.length; i++) { 
     traverse(curr.children[i]); 
    } 
} 
//Iterate through the array of root nodes 
for(var j=0;j < allNodes.length; j++) { 
    traverse(allNodes[j]); 
}