如何做這個Javascript/JSON樹的遞歸搜索？

我在寫一些Javascript代碼。我有一個JSON對象，看起來像這樣（間距修改可讀性）：如何做這個Javascript/JSON樹的遞歸搜索？

var myNodes = [ 
    { 
     id: 4, 
     children: [ 
      { 
       id: 1, 
       children: [ 
       ] 
      }, 
      { 
       id: 3, 
       children: [ 
       ] 
      } 
     ] 
    }, 
    { 
     id: 2, 
     children: [ 
     ] 
    }, 
    { 
     id: 6, 
     children: [ 
      { 
       id: 5, 
       children: [ 
       ] 
      } 
     ] 
    } 
]

每個節點在這個數據結構ID是唯一的。然而，除此之外，有ID號在所有之中沒有固定的或已知的關係。每個級別的兒童人數沒有限制。

如果我想搜索這棵樹，並用ID == 6.我該怎麼辦呢返回節點？我寫了下面的代碼，它遇到的第一個葉節點，整個算法返回false，這顯然是不對的。然而之後。我只是想做一個基本的深度優先搜索。但我不想爲這些數據添加額外的字段，並像我在Web上的一些DFS實現中看到的那樣「標記」這些節點。

myClass.prototype.nodeSearch = function nodeSearch(treeNodes, searchID){ 
    for (var nodeIdx = 0; nodeIdx <= treeNodes.length-1; nodeIdx++) 
    { 
     console.log("Comparing treeNodes element with ID==" + treeNodes[nodeIdx].id + " to SearchID==" + searchID); 
     if (treeNodes[nodeIdx].id == searchID) 
     {  
      console.log("Match!"); 
      return treeNodes[nodeIdx]; 
     } 
     else 
     { 
      console.log("No Match! Trying " + treeNodes[nodeIdx].children.length + " Children of Node ID#" + treeNodes[nodeIdx].id); 
      return this.nodeSearch(treeNodes[nodeIdx].children, searchID); 
     } 
    } 
    console.log("Done trying " + treeNodes.length + " children. Returning False"); 
    return false; 
};

來源

2014-05-05 Saqib Ali

您的算法存在問題。無論您if和你else回報無條件，這意味着return將不可避免地發生在通過每個循環的第一次迭代，算法將只檢查第一個它的每一個後代的（在這種情況下，只是節點4和1，沒有別的）。你需要檢查遞歸調用是否返回了一個找到的值，並且只有在遞歸樹上傳遞了這個值。我想這應該爲您提供一個固定的解決方案：

myClass.prototype.nodeSearch = function nodeSearch(treeNodes, searchID){ 
    for (var nodeIdx = 0; nodeIdx <= treeNodes.length-1; nodeIdx++) { 
     var currentNode = treeNodes[nodeIdx], 
      currentId = currentNode.id, 
      currentChildren = currentNode.children; 
     console.log("Comparing treeNodes element with ID==" + 
        currentId + " to SearchID==" + searchID); 
     if (currentId == searchID) {  
      console.log("Match!"); 
      return currentNode; 
     } 
     else { 
      console.log("No Match! Trying " + currentChildren.length + 
         " Children of Node ID#" + currentId); 
      var foundDescendant = this.nodeSearch(currentChildren, searchID); 
      if (foundDescendant) { 
       return foundDescendant; 
      } 
     } 
    } 
    console.log("Done trying " + treeNodes.length + " children. Returning False"); 
    return false; 
};

我還添加了一些變量來幫助使代碼有點DRY呃，並有助於防止前面提到的一些錯誤。

來源

2014-05-05 06:14:52 JLRishe

是的，我相信我發現後，我的戰後初期的根本原因。你能看到我的編輯嗎？ – JLRishe

工作！謝謝！！ –

您可以使用DefiantJS（https://github.com/hbi99/defiant.js）。使用這個js-lib，你可以用XPath查詢來搜索JSON結構。這一點和下面的代碼一樣簡單。這裏是在JSFiddle相同的代碼： http://jsfiddle.net/hbi99/a55au8h5/

PS：我添加了這個示例代碼的「名稱」屬性。

var myNodes = [ 
    { 
     "id": 4, 
     "name": 'name_of_4', 
     "children": [ 
      { 
       "id": 1, 
       "name": 'name_of_1', 
       "children": [] 
      }, 
      { 
       "id": 3, 
       "name": 'name_of_3', 
       "children": [] 
      } 
     ] 
    }, 
    { 
     "id": 2, 
     "name": 'name_of_2', 
     "children": [] 
    }, 
    { 
     "id": 6, 
     "name": 'name_of_6', 
     "children": [ 
      { 
       "id": 5, 
       "name": 'name_of_5', 
       "children": [] 
      } 
     ] 
    } 
], 
found = JSON.search(myNodes, '//*[id=6]');

的console.log（實測值[0]。名稱）; // name_of_6

來源

2014-12-18 22:06:27

我選擇使用json-easy-filter而不是爲類似任務編寫自定義解決方案。

來源

2016-09-16 20:18:13

如何做這個Javascript/JSON樹的遞歸搜索？

回答

相關問題