Java - 多节点树数据结构 - 如何高效搜索

Question

我正在寻找一种实现/数据结构来管理我的某些类别和子类别。我考虑使用搜索树，但不确定如何开始实现。

让我展示一下数据的样子。实际上，它作为一个JSON结构从后端传递给我，但它看起来像这样：

  [
    {
      "id": 94,
      "category_name": "New In", //this is the category category_name
      "description": "",
      "children": [ //this is the category children which can also be a sub-category
        {
          "id": 322,
          "category_name": "New Studio",
          "description": "Chic, sophisticated and polished with a classic edge."
        },
        {
          "id": 365,
          "category_name": "New Soho",
          "description": "Fresh, eclectic, and trendy. Oozes effortless cool."
        },
        {
          "id": 809,
          "category_name": "Summer Collection",
          "description": "Your ultimate summer look"
        }
      ]
    },
    {
      "id": 12,
      "category_name": "Clothes",
      "description": "",
      "children": [
        {
          "id": 22,
          "category_name": "All Clothes",
          "description": ""
        },
        {
          "id": 63,
          "category_name": "Tops",
          "description": "",
          "children": [
            {
              "id": 5,
              "category_name": "All Tops",
              "description": ""
            }

          ]
        },
        {
          "id": 641,
          "category_name": "Accessories",
          "description": "",
          "children": [
            {
              "id": 61,
              "category_name": "All Accessories",
              "description": ""
            },
            {
              "id": 622,
              "category_name": "Jewelry",
              "description": "",
              "children": [ // here is an example of a child that is a sub-category also
                {
                  "id": 52,
                  "category_name": "All Jewelry",
                  "description": ""
                },
                {
                  "id": 68,
                  "name": "Necklaces",
                  "description": ""
                },
                {
                  "id": 69,
                  "name": "Bracelets",
                  "description": ""
                },

              ]
            },

  ]

如果我需要画出这个结构，它看起来会像这样：

所以我想要能够获取任何东西的路径。例如，如果我想搜索项链，那么除了得到一条项链之外，我还希望得到路径：类别/配件/珠宝/项链

是否有内置的数据结构可以实现这一点？我正在使用Java进行编码。我想也许还需要对节点按某种顺序排序，比如按字母顺序A-Z。

到目前为止，我有以下代码：

class Node{
 String label;
 List<Node> children;
}

但是如何进行搜索？是否有更好的数据结构？我不想在搜索过程中迭代所有的节点，有没有一种方法可以对树进行排序，使我不必这样做？按照我的现有方式，我必须迭代所有的子节点。也许有一种按字母顺序或某种排序方式可以使查找更快吗？

- j2emanue

Answer 1

到目前为止，我不知道有任何Java内置的数据结构可以处理您要查找的内容。 在Github上有一些树实现或者这个stackoverflow线程可能会对您有所帮助。

但是如果我理解正确的话，您也希望在树上进行高效的搜索。尽管对树进行排序可以显著提高搜索性能，但这并不能完全解决问题，因为仍然需要搜索每个子树。据我所知，Java中没有现成的数据结构可用。

我想到的另一种方法是使用Map，其中包含您的和相应Node的引用。但是，您需要一个可以从叶子节点到根节点遍历以获取完整路径的树，并且必须注意重复的信息。例如，如果删除一个节点，则还必须在Map中将其删除。如果您还想从根部遍历树，则可能要构建一个双向树。

以下是我的方法：

class Node {
    String label;
    Node parent;
}

class Tree {
    HashMap<String, List<Node>> tree;
}

如果您有多个相同的标签名称，那么它是一个List<Node>。例如，如果您在jewelry和summer collection中都有necklaces。

- Alex

Answer 2

你需要两件事情：

在你的Node对象中，还需要一个对父节点的引用：

class Node{
    String label;
    List<Node> children;
    Node parent;
}

创建一个HashMap将标签映射到节点：

HashMap<String, Node> labelsToNodes;

然后使用HashMap中的get()方法进行搜索。通过重复获取父节点来获取类别列表。如果您需要此代码，请告诉我，我会添加它（我现在时间很紧）。

- Brian Risk

---

正如我在答案中提到的，如果您需要处理同一个标签多次，您可能需要在HashMap中使用List<Node>。 - Alex

Answer 3

我这个学期有一个关于树的搜索项目。我使用了不同类型的算法，例如BFS或DFS，这取决于您想要什么以及如何在树中移动节点。但是，我更喜欢IDS（迭代加深深度优先搜索）算法。要使用此算法，您可以访问这些链接。 与其使用子节点，最好使用父节点，因为这样效果更好，而且不会耗尽内存。 在Youtube上显示IDS剪辑 IDS的完整教学 如果需要其他好的算法，您可以随时问我。 您需要定义一个状态类。

    class State{
    String name;
    State father;
    }

- Masoud Erfani