樹遍歷優化

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