java - 遍历引用 Java 中的父节点的分层列表/树

Question

我正在尝试使用 https://github.com/bmelnychuk/AndroidTreeView 创建一个分层菜单

我将从 REST 服务中检索我的数据，示例菜单如下所示

[
  {
    "name": "parent 1",
    "code": "p1",
    "parent_code": "null",
    "is_active": 1,
    "store_id": "57a6d06232a7d133002b838c"
  },
  {
    "name": "parent 2",
    "code": "p2",
    "parent_code": "null",
    "is_active": 1,
    "store_id": "57a6d06232a7d133002b838c"
  },
  {
    "name": "child 1",
    "code": "c1",
    "parent_code": "p1",
    "is_active": 1,
    "store_id": "57a6d06232a7d133002b838c"
  },
  {
    "name": "child 2",
    "code": "c2",
    "parent_code": "p1",
    "is_active": 1,
    "store_id": "57a6d06232a7d133002b838c"
  },
  {
    "name": "grand child 1",
    "code": "gc1",
    "parent_code": "c2",
    "is_active": 1,
    "store_id": "57a6d06232a7d133002b838c"
  },
  {
    "name": "grand child 2",
    "code": "gc2",
    "parent_code": "c2",
    "is_active": 0,
    "store_id": "57a6d06232a7d133002b838c"
  },
  {
    "name": "grand child 3",
    "code": "gc3",
    "parent_code": "c2",
    "is_active": 1,
    "store_id": "57a6d06232a7d133002b838c"
  }
]

我正在尝试遍历列表并创建一个分层菜单。我正在使用以下代码遍历

for (ProductCategory prodCat :
                productCategories)
{
    if (prodCat.getParentCode().equalsIgnoreCase("null"))
    {
        // I found a parent node
        for (ProductCategory prodCatChild :
                productCategories)
        {
            if (prodCatChild.getParentCode().equalsIgnoreCase(prodCat.getCategoryCode()))
            {
                //I found all child nodes of the current parent
            }
        }
    }
}

我的 ProductCategory 定义如下

public class ProductCategory
{
    private String categoryName;

    private String categoryCode;

    private String parentCode;

    private Boolean isActive;

    private String storeId;
}

这段代码有两个问题。

• 如果树中有第三层或更多层，我将根本无法遍历它们。
• 我正在遍历 n^2 次，只为两个级别。

我怎样才能以最有效的方式遍历仅引用父对象？

Answer 1

我建议您使用 Hash Map 数据结构来构建运行时复杂度为 O(N) 的树。

为简单起见，我们假设您的实体具有以下结构(为了简单起见，我在提供的代码 fragment 中也违反了封装原则):

class Item {

    // id of the item itself
    final String id;

    // id of the parent item
    final String parentId;

    // this list will contain the children of the given item
    // at the beginning this list is empty, and we are going to populate it
    final List<Item> children = new ArrayList<>();

    public Item(String id, String parentId) {
        this.parentId = parentId;
        this.id = id;
    }
}

为了构建树，您应该维护从项目 ID 到项目本身的映射(这可以使用 java.util.HashMap 数据结构来完成)。构建映射后，您可以将每个节点附加到其父节点:

List<Item> constructForest(Item... items) {
    Map<String, Item> itemIdToItem = indexItemsById(items);
    List<Item> roots = attachToParents(itemIdToItem, items);
    return roots;
}

/**
 * Index all items by item id.
 * Returns the mapping from the item id to item.
 */
Map<String, Item> indexItemsById(Item... items) {
    Map<String, Item> itemIdToItem = new HashMap<>();
    for (Item item : items) {
        itemIdToItem.put(item.id, item);
    }
    return itemIdToItem;
}

/**
 * Attaches the children nodes to the parent nodes
 * Returns the list of root nodes of the constructed forest
 */
List<Item> attachToParents(Map<String, Item> itemIdToItem, Item... items) {

    List<Item> roots = new ArrayList<>();

    for (Item item : items) {
        if (item.parentId == null) {
            roots.add(item);
        } else {
            Item parent = itemIdToItem.get(item.parentId);
            parent.children.add(item);
        }
    }

    return roots;
}

所提供代码的运行时复杂度为 O(N)。

现在，有了构建树的根列表，您可以使用任何树遍历算法遍历它们，例如广度优先搜索 ( https://en.wikipedia.org/wiki/Breadth-first_search )、深度优先搜索 ( https://en.wikipedia.org/wiki/Depth-first_search )，同样具有 O(N) 的运行时复杂度。