樹結構：找到父元素的元素並保存鏈的最佳方法

Question

我有一個JSONObject，它可能具有相同類型的子JSONArray。我想遍歷它，找到我需要的元素並保存父元素的鏈（例如，找到的元素是此元素的子元素，此元素是下一個元素的子元素，下一個元素是根元素的子元素）。

目前這裏是我的幼稚的做法：

private boolean found; 

private void searchNode(List<JSONObject> chain, 
         JSONObject rootNode, JSONObject desiredFrame) { 

    if (found) 
     return; 

    JSONArray children = rootNode.getJSONArray("frames"); 

    chain.add(rootNode); 

    for (int i = 0; i < children.length(); i++) { 
     JSONObject currentNode = children.getJSONObject(i); 

     if (currentNode.equals(desiredNode)) { 
      found = true; 
      chain.add(currentNode); 
      return; 
     } 

     searchNode(chain, currentNode, desiredNode); 

     if (!found) 
      chain.remove(currentNode); 
    } 

我可以看到什麼樣的問題：

1. 我不知道它會工作得很好:)
2. 此實現不明顯，這不是乾淨的代碼。
3. 我使用類領域，大概我能避免使用

可將這種結構稱爲樹，但是這個人是不是二進制文件。

Answer 1

一些潛在的問題與代碼：

• 您可以用searchNode結果代替共享標誌found。
• 您正在比較JSONObject等於。我建議使用Predicate來檢查它是否合適。
• rootNode.getJSONArray("frames")可以返回null或空數組，但你從不檢查它。
• 此外，您可以使用Stack<>而不是List<>來跟蹤路徑。它可以簡化你的算法。

例子：

private static boolean searchNode(Stack<JSONObject> chain, 
            JSONObject currentNode, Predicate<JSONObject> condition) throws Exception { 

    if (condition.test(currentNode)) { 
     chain.push(currentNode); 
     return true; 
    } 

    JSONArray children = currentNode.getJSONArray("frames"); 
    if (children == null) { 
     return false; 
    } 

    for (int i = 0; i < children.length(); i++) { 
     if (searchNode(chain, children.getJSONObject(i), condition)) { 
      chain.push(currentNode); 
      return true; 
     } 
    } 

    return false; 
} 

Answer 2

這裏是一個更好的算法來搜索您的對象。

您不必維護找到的字段或將您的鏈作爲參數傳遞。

相反，你用你的遞歸調用的返回值來構建鏈一旦你找到對象

List<JSONObject> search(JSONObject node, JSONObject searchTerm) { 
    if (node.equals(searchTerm)) { 
     List<JSONObject> chain = new List<>(); 
     chain.add(node); 
     return chain; 
    } else { 
     List chain = new Collections.emptyList(); 
     for (JSONObject child: node.getJSONArray("frames")) { 
      chain = search(child, searchTerm); 
      if (chain.length > 0) { 
       chain.add(0, node); 
       break; 
      } 
     } 
     return chain; 
    } 
}