如何编写递归方法来查找父节点和子节点

Question

这是为了使用递归保存详细信息。

在此，我想从数据库获取详细信息并使用递归方法设置到我的bean中。因此，我可以以angularUi树形格式显示。我该如何编写递归方法以将其设置到我的bean中。

我的DB结构：

我使用rowId区分父项和子项。您可以访问我的示例屏幕。

例如：Rowid是1的父项 该1的子项为1.1， 1.1的子项为1.1.1，以此类推。

我将所有父项和子项保存在单个表中，即上图。

每个对象（行）都会有items[]。如果父项有任何子项，则该子项将添加到该items[]数组中。如果该子项有任何子项，则该子项将添加到该行的父项的items[]中……以此类推。

例如：JSON对象如下：

{
    "id": 1,
    "rowId": "1",
    "items": [
      {
        "id": 10,
        "rowId": "1.1",
        "items": [
          {
            "id": 100,
            "rowId": "1.1.1",
            "items": [
              {
                "id": 1000,
                "rowId": "1.1.1.1",
                "items": []
              }
            ]
          }
        ]
      },
      {
        "id": 11,
        "rowId": "1.2",
        "items": []
      }
    ]
  }

我使用这个答案来保存这些数据。

但是在检索时，我遇到了问题。问题是，在检索时，不会有任何父级和子级，因为数据将保存在同一个表中。关系只有rowid。因此，我需要编写递归方法来添加子项到父项的items[]数组中，就像保存一样。

public class AdminComponentBean{

    List<MultiAdminComponent> componentListbean;
}

MultiAdminComponent.java:-

public class MultiAdminComponent {

    private String componentName;
    private String componentIdentification;
    private String componentType;
    private String componentState;
    private String componentUrl;
    private String rowId;
    private List<MultiAdminComponent> items;
}

在这里，我尝试检索所有细节并尝试将子项添加到父项。但它应该使用递归方法。

List<MultiAdminComponent> componentList=BaseDAO.getAdminComponentDAOObject().getComponentDetails();
   if(null != componentList) {
       for(MultiAdminComponent itemsList : componentList){
           if(itemsList.getRowId().length().equals() "1"){//here parent row will come
               //by considering rowid I need to find the child of the rowId
               //child of 1 is 1.1
               //if 1.1 is child of 1 then I need to add that 1.1 object to `items[]` array of 1
               //like this it should work recursve
            }
        }
    }

- Murali

---

如果您有一个父ID（假设这就是“rowId”的含义），那么应该相当简单（更高的性能可能会使它更复杂，所以现在我们将坚持简单）：1）获取所有没有父级的元素2）直到您不再获取任何数据为止，请执行以下操作：a）获取所有行ID与最后加载的元素之一匹配的元素，并b）使用行ID将加载的元素附加到其父级。当您不再获取任何元素时，您就完成了。 - Thomas

每一行的rowid都是唯一的。 - Murali

@Thomas，你能否请再提供一些更明确的信息？ - Murali

实际上，看一下Absurd-Mind的答案，他似乎利用了“rowId”基本上包含其各自级别上所有父项的索引（因此rowId = parent.rowId + indexInParent）。 因此，您可以在一个查询中加载部分树（例如，... where rowId in ('1'，'1.1') or rowId like '1.1.%'以获取元素1、1.1和所有1.1的子项），并且正如Absurd-Mind建议的那样，使用映射将加载的元素连接起来。 - Thomas

Answer 1

我建议不要使用递归，而是多花一点功夫将所有元素存储在HashMap中。

// a map containing all elements searchable by the rowId
HashMap<String, MultiAdminComponent> idToItem = new HashMap<>();
// a set containing all elements that don't have a parent (id: 1, 2, 3, etc.)
Set<MultiAdminComponent> rootItems = new HashSet<>();

for (MultiAdminComponent item : componentList) {
    // build the id->item map
    idToItem.put(item.getRowId(), item);
}

for (MultiAdminComponent item : componentList) {
    String parentId = getParentId(item.getRowId());
    if (parentId == null) {
        // this item has no parent -> it is a root item
        rootItems.add(item);
    } else {
        // This item has a parent -> look the parent up
        MultiAdminComponent parent = idToItem.get(parentId);
        parent.getItems().add(item);
    }
}

// rootItems now contains all MultiAdminComponents which do not have a parent, with the correct hierarchy for all items

getParentId 可能长这样：

private String getParentId(String id) {
    int lastDot = id.lastIndexOf(".");
    if (lastDot == -1) {
        return null;
    }
    return id.substring(0, lastDot);
}

如果你能保证componentList从父元素到子元素的顺序遍历，那么可以合并两个for循环。

- Absurd-Mind