如何使用 JavaScript 在树中查找节点

Question

我有一个对象文字，它本质上是一棵没有固定数量级别的树。如何在树中搜索特定节点，然后在 javascript 中以有效方式找到该节点时返回该节点？

本质上我有一棵这样的树，想找到标题为“randomNode_1”的节点

var data = [
{
title: 'topNode',
 children: [
   {
       title: 'node1',
       children: [
       {
           title: 'randomNode_1'
       },
       {
           title: 'node2',
           children: [
           {
               title: 'randomNode_2',
               children:[
               {
                   title: 'node2',
                   children: [
                   {
                       title: 'randomNode_3',
                   }]
               }
               ]
           }]
       }]
   }
  ]
 }];

原文由 Dave 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这个答案基于@Ravindra 的答案，但具有真正的递归。

 function searchTree(element, matchingTitle){
     if(element.title == matchingTitle){
          return element;
     }else if (element.children != null){
          var i;
          var result = null;
          for(i=0; result == null && i < element.children.length; i++){
               result = searchTree(element.children[i], matchingTitle);
          }
          return result;
     }
     return null;
}

然后你可以称它为：

 var element = data[0];
var result = searchTree(element, 'randomNode_1');

原文由 driangle 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这是一个迭代解决方案：

 var stack = [], node, ii;
stack.push(root);

while (stack.length > 0) {
    node = stack.pop();
    if (node.title == 'randomNode_1') {
        // Found it!
        return node;
    } else if (node.children && node.children.length) {
        for (ii = 0; ii < node.children.length; ii += 1) {
            stack.push(node.children[ii]);
        }
    }
}

// Didn't find it. Return null.
return null;

原文由 FishBasketGordo 发布，翻译遵循 CC BY-SA 4.0 许可协议