JavaScript中的遞歸重搜索JSON

Question

我正面臨一個算法概念問題。使用JavaScript語言，我有大約11000行的繁重的JSON對象，這是HTML文件轉換的結果。 JSON的結構類似於DOM中的一個，這意味着一個Object可以擁有一個屬性的孩子，這是一個由其他類似對象組成的數據結構。目標是在JSON中搜索並提取具有該屬性的對象的屬性itemprop的信息。 itemprop屬性是在和Object裏面的屬性屬性，表示某些第一個提到的Object有。

對象結構

{ type: 'x', 
    tagName: 'y', 
    attributes: { "itemprop" : "valueWanted" }, 
    children: 
    [ Object, Object, Object] 
} 

我想到了一個遞歸算法解決方案。不幸的是，我不熟悉遞歸，下一個代碼無法正常工作。

遞歸算法

var searchAttributesRecursive = function(children) { 
    for (var i = 0; i < children.length; ++i) { 
     if (children[i].hasOwnProperty('children')) { 
     return searchAttributesRecursive(children[i].children); 
     } 
     else { 
     if (children[i].hasOwnProperty('attributes')) { 
      if (children[i].attributes.itemprop === "valueWanted") { 
       console.log('success') 
      } 

      } 
     } 
     return; // probably a problem that breaks the loop 
     } 
    }; 

searchAttributesRecursive(startingChildren); 

有可能是另一種更有效的通用算法，才能得到這個任務完成。我樂於接受建議。

更新

感謝您提供所有的解決方案和解釋。更特別的是，請看@ ChrisG的簡單解決方案。現在，我想在算法中添加一個特殊的條件。

如果我想從下一個對象中檢索數據，而這些數據超出了對象具有wantedValue2的子範圍，那麼您是否知道如何訪問這些數據？算法遇到wantedValue2時會有一個特殊情況，並且不想直接提取itemprop的數據。

對象結構特殊情況

{ 
"type": "", 
    "tagName": "", 
    "attributes": { 
    "itemprop": "wantedValue" 
    }, 
    "children": [{ 
     "type": "", 
     "content": "" 
     } 
    ] 
    }, 
{ 
    "type": "", 
    "content": "" 
    }] 
    },   
    { 
    "type": "", 
    "tagName": "", 
    "attributes": {}, 
    "children": [ 
    { 
    "type": "", 
    "content": "here" 
    } 
    ] 

Answer 1

這裏有一個較短的版本：

注意，函數需要一個數組，所以如果你的對象不是一個數組，你必須使用findItemprop([dom], "wanted")

function findItemprop(data, value, found) { 
 
    if (!found) found = []; 
 
    data.forEach((node) => { 
 
    if (node.attributes && node.attributes.itemprop == value) 
 
     found.push(node); 
 
    if (node.children) findItemprop(node.children, value, found); 
 
    }); 
 
    return found; 
 
} 
 

 
var dom = [{ 
 
    tag: "root", 
 
    children: [{ 
 
    tag: "header", 
 
    children: [{ 
 
     tag: "div" 
 
    }] 
 
    }, { 
 
    tag: "div", 
 
    id: "main", 
 
    children: [{ 
 
     tag: "p", 
 
     attributes: { 
 
     itemprop: "wanted" 
 
     } 
 
    }] 
 
    }, { 
 
    tag: "footer", 
 
    children: [{ 
 
     tag: "span", 
 
     content: "copyright 2017", 
 
     attributes: { 
 
     itemprop: "wanted" 
 
     } 
 
    }] 
 
    }] 
 
}]; 
 

 
console.log(findItemprop(dom, "wanted"));

Answer 2

你的回報將打破循環。你只是想，如果它不會返回返回：

var searchAttributesRecursive = function(children) { 
    for (var i = 0; i < children.length; ++i) { 
     if (children[i].hasOwnProperty('children')) { 
      var result=searchAttributesRecursive(children[i].children); 
      if(result) return result;//if weve found sth, return 
     } 

     if (children[i].hasOwnProperty('attributes')) { 
      if (children[i].attributes.itemprop === "valueWanted1") { 
       console.log('success') 
       return children[i];//return sth useful 
      } 

     } 
    } 
return false;//nothing found in this and in all childs 
}; 

var elem=searchAttributesRecursive(startingChildren); 

這將返回第一找到孩子。您可能要返回數組來代替：

var searchAttributesRecursive = function(children,result=[]) { 
    for (var i = 0; i < children.length; ++i) { 
     if (children[i].hasOwnProperty('children')) { 
      searchAttributesRecursive(children[i].children,result); 
     } 
     if (children[i].hasOwnProperty('attributes')) { 
      if (children[i].attributes.itemprop === "valueWanted1") { 
       console.log('success') 
       result.push(children[i]);//return sth useful 
      } 

     } 
    } 
return result;//return all results found 
}; 

var arr=searchAttributesRecursive(allElems); 
arr.forEach(console.log); 

通過傳遞一個數組作爲可選參數，它是快速和容易的多個樹的遍歷儲存在同一個結果：

var arr=[]; 
searchAttributesRecursive(allElems,arr); 
searchAttributesRecursive(allElemsTwo,arr); 

Answer 3

您可以通過使用.some()功能做到這一點。這樣做會在任何迭代返回true時返回true，否則返回false。因此，對於當前對象中的每個鍵，您將檢查該屬性是否爲=== 'attributes'，如果是，則將檢查itemprop屬性以獲取所需的值。如果當前鍵不是「屬性」，並且是=== 'children'，它將以相同的方式遞歸併檢查每個子對象。

var searchAttributesRecursive = function(obj, valueWanted) { 
 
    if (obj instanceof Object) { 
 
    if (obj.attributes && obj.attributes.itemprop === valueWanted) { 
 
     return true; 
 
    } 
 
    if (obj.children) { 
 
     return obj.children.some(function(_obj) { 
 
     return searchAttributesRecursive(_obj, valueWanted); 
 
     }); 
 
    } else { 
 
     return false; 
 
    } 
 
    } else { 
 
    return false; 
 
    } 
 
}; 
 
var obj = { 
 
    type: 'x', 
 
    tagName: 'y', 
 
    attributes: { 
 
    "itemprop": "wantedValue0" 
 
    }, 
 
    children: [{ 
 
     type: 'x', 
 
     tagName: 'y', 
 
     attributes: { 
 
     "itemprop": "wantedValue1" 
 
     }, 
 
     children: [] 
 
    }, 
 
    { 
 
     type: 'x', 
 
     tagName: 'y', 
 
     attributes: { 
 
     "itemprop": "wantedValue2" 
 
     }, 
 
     children: [{ 
 
     type: 'x', 
 
     tagName: 'y', 
 
     attributes: { 
 
      "itemprop": "wantedValue3" 
 
     }, 
 
     children: [] 
 
     }] 
 
    } 
 
    ] 
 
}; 
 

 
console.log("Found 'wantedValue0': " + searchAttributesRecursive(obj, "wantedValue0")); 
 
console.log("Found 'wantedValue1': " + searchAttributesRecursive(obj, "wantedValue1")); 
 
console.log("Found 'wantedValue2': " + searchAttributesRecursive(obj, "wantedValue2")); 
 
console.log("Found 'wantedValue3': " + searchAttributesRecursive(obj, "wantedValue3")); 
 
console.log("Found 'wantedValue4': " + searchAttributesRecursive(obj, "wantedValue4"));

編輯 - 爲了使這項工作動態，並且在任何嵌套屬性或嵌套子屬性搜索itemprop === wantedValue，您可以執行以下操作：

var searchAttributesRecursive2 = function(data, valueWanted) { 
 
    if (Array.isArray(data)) { 
 
    return data.some(function(elem) { 
 
     return searchAttributesRecursive2(elem, valueWanted); 
 
    }); 
 
    } else if (data instanceof Object) { 
 
    return Object.keys(data).some(function(key) { 
 
     var prop = data[key]; 
 
     return prop.itemprop === valueWanted || searchAttributesRecursive2(prop, valueWanted); 
 
    }); 
 
    } else { 
 
    return false; 
 
    } 
 
}; 
 

 
var obj = { 
 
    type: 'x', 
 
    tagName: 'y', 
 
    attributes: { 
 
    "itemprop": "wantedValue0" 
 
    }, 
 
    children: [{ 
 
     type: 'x', 
 
     tagName: 'y', 
 
     attributes: { 
 
     "itemprop": "wantedValue1" 
 
     }, 
 
     children: [] 
 
    }, 
 
    { 
 
     type: 'x', 
 
     tagName: 'y', 
 
     attributes: { 
 
     "itemprop": "wantedValue2" 
 
     }, 
 
     children: [{ 
 
     type: 'x', 
 
     tagName: 'y', 
 
     attributes: { 
 
      "itemprop": "wantedValue3" 
 
     }, 
 
     children: [] 
 
     }] 
 
    } 
 
    ] 
 
}; 
 

 
console.log("Found 'wantedValue0': " + searchAttributesRecursive2(obj, "wantedValue0")); 
 
console.log("Found 'wantedValue1': " + searchAttributesRecursive2(obj, "wantedValue1")); 
 
console.log("Found 'wantedValue2': " + searchAttributesRecursive2(obj, "wantedValue2")); 
 
console.log("Found 'wantedValue3': " + searchAttributesRecursive2(obj, "wantedValue3")); 
 
console.log("Found 'wantedValue4': " + searchAttributesRecursive2(obj, "wantedValue4"));

Answer 4

給喬納斯w他們的答案的功勞，我只是標記幫助糾正一些關於遞歸的困惑，並希望使它更容易理解和使用。

首先，你傳遞的是孩子的數組。這很好，但是當你檢查它們時，你必須從它的數組索引中訪問每一個。我的建議是讓你的功能一次只處理一個項目。 （我將使用Jonas w的收集節點的方法，因爲可能有多個節點具有此屬性，我還將添加屬性名稱作爲參數以使其更具動態性。）

function searchAttributesRecursive(currentNode, parameterName, results=[]){ 
} 

現在你可以一次只集中在一個節點上。一旦它通過了支票，你就可以轉到孩子身上。

function searchAttributesRecursive(currentNode, parameterName, results=[]){ 
    if(currentNode.attributes && currentNode.attributes[parameterName]){ 
     results.push(currentNode); 
    } 
    if(currentNode.children){ 
     for(var i = 0, len = currentNode.children.length; i < len; ++i){ 
      searchAttributesRecursive(currentNode.children[i], parameterName, results); 
     } 
    } 
} 

調用它像這樣：

var results = []; 
searchAttributesRecursive(yourJsObject, "itemprop", results); 

...填充results與包含 「itemprop」 屬性節點。您現在可以使用簡單循環打印屬性值：

for(var i = 0, len = results.length; i < len; ++i){ 
    console.log(i, results[i].attributes.itemprop); 
}