通過遞歸遍歷一個Javascript對象來累積路徑

Question

我有一個存儲在Javascript對象中的樹結構，我想從頭部（sms_in）節點提取所有可能的路徑到分支中的最後一個節點。以下是樹結構的示例表示。

注意：任何給定的節點可以具有n個輸出（'true'型）連接的，但只有一個輸入連接。我的意思是，當你想從sms_in節點到isEmpty1節點，只有一個路徑[{ 'sms_in' : 'true'} ]。但是，如果您想從isEmpty1到dbInsert1，則必須選擇'false'路徑，而不是'true'路徑。你也可以去isEmpty節點的其他節點（不是在給定的情況下）。但是，您只能從一個路徑（即通過「sms_in」節點）到達isEmpty節點。

var graph = 
{ 
    "metadata": {"id": "sms_in", "type": "api", "optionsDivId": "div_sms_in", "options": {}}, 
    "data": { 
     "true": { 
      "isEmpty1": { 
       "metadata": { 
        "id": "isEmpty1", 
        "type": "empty", 
        "optionsDivId": "div_isEmpty1", 
        "options": {} 
       }, 
       "data": { 
        "true": { 
         "sms1": { 
          "metadata": { 
           "id": "sms1", 
           "type": "api", 
           "optionsDivId": "div_sms1", 
           "options": {} 
          }, "data": {"true": {}, "false": false} 
         } 
        }, 
        "false": { 
         "dbInsert1": { 
          "metadata": { 
           "id": "dbInsert1", 
           "type": "dbInsert", 
           "optionsDivId": "div_dbInsert1", 
           "options": {} 
          }, 
          "data": { 
           "true": { 
            "sms2": { 
             "metadata": { 
              "id": "sms2", 
              "type": "api", 
              "optionsDivId": "div_sms2", 
              "options": {} 
             }, "data": {"true": {}, "false": false} 
            } 
           }, "false": false 
          } 
         } 
        } 
       } 
      } 
     }, "false": false 
    } 
}; 

在這裏，我有2種類型的節點，其中'if/empty'類型的節點有'true/false'類型的子節點，而所有其他節點只有'true'類型的節點。我想遍歷節點並按照以下方式獲取所有可能情況的完整路徑。

var output = [ 

[ {'sms_in':'true'}, {'isEmpty1':'true'}, {'sms1':''}], 
[{'sms_in':'true'}, {'isEmpty1':'false'}, {'dbInsert1':'true'}, {'sms2':''}] 

]; 

我可以遍歷樹，但我不知道如何積累得到output陣列形式的完整路徑。 有人可以幫我嗎？

Answer 1

這個解決方案有效，但我不會依賴它，因爲數據結構。

基本上你有這樣的

data.true[k].data.true --> { k: true } 
data.true[k].data.false --> { k: false } 
     ^ and ^

的結構，這是非常罕見的。

但是sms1和sms2的值在我的情況下是true而不是''。想要的值不在給定的對象中。

function traverse(o, p, last) { 
 
    var r = []; 
 
    Object.keys(o).forEach(function (k) { 
 
     var l = typeof o[k] === 'object' && Object.keys(o[k])[0], 
 
      temp = {}; 
 
     temp[last] = k; 
 
     if (l && o[k][l].data && typeof o[k][l].data === 'object') { 
 
      r = r.concat(traverse(o[k][l].data, p.concat(temp), l)); 
 
     } else { 
 
      o[k] && r.push(p.concat(temp)); 
 
     } 
 
    }); 
 
    return r; 
 
} 
 

 
var graph = { "metadata": { "id": "sms_in", "type": "api", "optionsDivId": "div_sms_in", "options": {} }, "data": { "true": { "isEmpty1": { "metadata": { "id": "isEmpty1", "type": "empty", "optionsDivId": "div_isEmpty1", "options": {} }, "data": { "true": { "sms1": { "metadata": { "id": "sms1", "type": "api", "optionsDivId": "div_sms1", "options": {} }, "data": { "true": {}, "false": false } } }, "false": { "dbInsert1": { "metadata": { "id": "dbInsert1", "type": "dbInsert", "optionsDivId": "div_dbInsert1", "options": {} }, "data": { "true": { "sms2": { "metadata": { "id": "sms2", "type": "api", "optionsDivId": "div_sms2", "options": {} }, "data": { "true": {}, "false": false } } }, "false": false } } } } } }, "false": false } }, 
 
    path = traverse(graph.data, [], 'sms_in'); 
 

 
document.write('<pre>' + JSON.stringify(path, 0, 4) + '</pre>');