寻找更好的树形数据结构

Question

我有一个可展开的树（在HTML页面中）：

+ Category 1
- Category 2
  + Subcategory 1
  - Subcategory 2
    |- Foo
    |- Bar
    |- Link 42

这是由后端定义的一个结构表示：

class Demo {
  static ImmutableList<Item> sample() {
    return ImmutableList.of(
        new Item("Category 1", ImmutableList.of(
            new Item("Some link title", "resource_id_1"),
            new Item("Another link title", "resource_id_2"))),
        new Item("Category 2", ImmutableList.of(
            new Item("Subategory 1", ImmutableList.of(
                new Item("Another link title", "resource_id_3"))),
            new Item("Subcategory 2", ImmutableList.of(
                new Item("Foo", "resource_id_1"),
                new Item("Bar", "resource_id_2"),
                new Item("Link 42", "resource_id_42"))))));
  }
}

假设已经定义了Item:

public class Item {
  private String readableName;
  private String resourceId;
  private ImmutableList<Item> children;

  Item(String name, String resourceId) {
    this.readableName = name;
    this.resourceId = resourceId;
  }

  Item(String name, ImmutableList<Item> children) {
    this.readableName = name;
    this.children = children;
  }

  public String getReadableName() {
    return readableName;
  }

  public String getResourceId() {
    return resourceId;
  }

  public ImmutableList<Item> getChildren() {
    return children;
  }
}

resourceId 可以有不同的可读名称，并且可以在整个结构中放置多次，但在当前类别/子类别中只能放置一次。

目前，当用户单击链接或输入URL时，资源会被加载（例如，链接Foo映射到/showResource?id=resource_id_1:uniqe_magic_id），并且树形结构会展开。这仅因为一个hack而起作用 - 前端创建了自己的结构副本，将一些:uniqe_magic_id字符串附加到每个资源ID（每个叶子）上，并在向后端发送请求时删除了魔术部分。 :uniqe_magic_id 仅由前端用于展开上面显示的树中的正确项目。对我来说，这似乎是一个巧妙的解决方案（我正在重构此代码并删除了cleanId方法，我认为这不是必要的，但在向后端发送请求之前会strip掉magic...），我正在寻找更好的解决方案。

我可以修改前端和后端。我考虑过一些节点的树形结构：

class Node {
  Node next;
  Node child;
  String readableName;
  String resourceId;
  String someUniqueHash;
}

并且使用 someUniqueHash。

有没有更好的方法在前端实现相同的结果而不必复制整个结构？

- Xaerxess

---

“List”在这里最初用于指示它以某种方式进行排序，“Item”到目前为止没有hashCode/equals，但这是一个小而有用的建议，实际上并没有解决我的问题。 - Grzegorz Rożniecki

后端维护结构如何？在前端显示树形结构，并始终向服务器请求从所点击节点开始的子树？此外，使用WeakHashMap可能会有用。 - Ravi Bhatt

在获取所点击节点的子树时，您也可以获取第一级节点的子项。 - Ravi Bhatt

通过new Item(String, ImmutableList<Item>)构造函数将子项的ID更改为以父项的ID开头怎么样？这样你就会拥有唯一的ID，无需复制或更改结构。 - HericDenis

请问您能否提供一下您前端代码的样例？ - Petro Semeniuk

Answer 1

如何断言在创建菜单时，项目的id在本地是唯一的，当子项附加到每个项目时，更新对父项的引用呢？

这将使您能够展开url中聚焦的任何子树，前端（假设为html）将动态导航菜单并向用户呈现各种类别。

可以通过添加一个名为Menu的新类，并使Menu中的children可变来通过工厂模式断言项目的本地唯一性。

class Menu {
    final HashMap<String, Item> items = new HashMap<String, Item>();
    final List<Item> root = new ArrayList<Item>();

    public Item createItem(String title, String id, Item parent) {
        if (items.containsKey(id)) {
            raise SomeRuntimeException();
        }

        final Item item = new Item(title, id, parent, this);

        if (parent == null) {
            root.add(item);
        }
        else {
            parent.addChild(item);
        }

        items.put(id, item);
    }

    /* default to have no parent, these are root items. */
    public Item createItem(String title, String id, Item parent) {
        return addItem(title, id, null);
    }
}

对Item类进行了一些修改。

class Item {
    private final Menu menu;
    private final Item parent;
    private final List<Item> children = new ArrayList<Item>();

    public Item(String name, String resourceId, Menu menu, Item parent) {
        ...
        this.menu = menu;
        this.parent = parent;
    }

    public Item addChild(String name, String resourceId) {
        final Item item = this.menu.createItem(name, resourceId, this);
        this.children.add(item);
        return item;
    }
}

现在，我牺牲了一些不可变性，因为我相信这种模式在处理错误时比提供一组嵌套列表更具表现力。

生成不可变菜单

如果不可变性很重要，您可以将Menu和Item转换为接口，并实现复制原始Menu和Item的不可变变体，然后在Menu类中添加一个copyImmutable方法来构建请求的结构。

class MenuBuilder {
    /* ... contains all things previously declared in Menu ... */
    Menu copyImmutable() {
        ImmutableList<Item> root = ...
        ImmutableMap<String, Item> items = ...
        return new ImmutableMenu(root, items)
    }
}

这意味着您需要递归地执行所有项目。

生成菜单的算法

1. 从Menu类中查找该项（处理潜在错误）
2. 迭代每个父级菜单并记录pathTaken。
3. 当到达根节点时，将其存储为activeRoot。
4. 按顺序迭代Menu中的所有根节点并呈现它们。 当命中activeRoot时，递归呈现所有子项，但仅进入pathTaken中注册的子项。

我希望这描述了一个解决方案，可以给您启发，以解决您的问题！

- udoprog

Answer 2

在前端制作一个树的副本是必要的，因为它代表了不同的概念：后端中的树表示“模型”，而前端中的树表示“模型的视图”。这是非常重要的区别：后端中的树说出了要显示什么，而前端中的树则说出了如何显示。具体来说，前端知道哪些部分的树是展开的：后端不应该知道这一点，因为树节点的打开/关闭状态对于不同的用户将是不同的。

也许你应该明确分工。不要制作树的副本并向其资源ID添加唯一标识符，而是创建一个独立的VisualItem类，封装实际项的ID，并拥有自己的唯一ID（这个唯一ID永远不会进入后端）：

class VisualItem {
    String resourceId;
    ImmutableList<VisualItem> children;
    String uniqueId;    // Used only in the front end
    boolean isExpanded; // Tells you if the subtree is expanded or not
    // You can add more attributes here to avoid requesting the Item.
    // For example, you could add a readableName here
}

确保ID唯一性的一种方法是使用UUID类：它提供了一个非常方便的randomUUID()方法，为您提供唯一的标识符。

- Sergey Kalinichenko

---

基本上我得出的结论就是，你在这里写的东西 - 没有（优雅的）解决方案可以在没有在前端制作几乎相似的数据结构副本的情况下实现。在这里添加一些唯一ID更容易（其他人建议使用类似于前端结构的hashCode和equals等功能），在后端只会有一个包含纯数据的简单模型-不多也不少。我会稍后发布最终解决方案。 - Grzegorz Rożniecki

Answer 3

如果我理解正确，您正在尝试仅通过非唯一ID可靠地识别树形结构中项目的位置。

生成的URL是否为“永久链接”，即用户可以安全地将其加为书签，并在n年后返回，即使树形结构可能已更改？树形结构会发生变化吗？特别是，您是否曾经将资源移动到不同的类别，但希望其旧链接将用户带到新位置？

如果是后者，则除了为每个资源ID生成或指定唯一标识符之外，您几乎没有其他选择。您可以生成/使用UUID，或要求用户指定ID并让代码强制执行唯一性。

否则，您可以使用树中项目的位置来为您提供唯一的ID（因为树形结构不会更改，或者如果资源在树内发生重大移动，则用户不能依赖于保存的资源链接在未来起作用）。

例如，给定一个树：

- A
  |- Resource1
- B
  + X
  + Y
  - Z
    |- Resource1
    |- Resource24

因此，每个项目可以根据其在树中的位置和非唯一资源标识符在服务器端分配复合资源ID。例如，“A/Resource1”和“B/Z/Resource1”。

或者，如果您不想依赖显示名称或在整个过程中分配ID，请使用每个类别在其父级内的序数位置，例如“1/Resource1”（第一个类别，然后是Resource1）可以与“2/3/Resource1”（第二个类别，然后是它的第三个子项，然后是Resource1）区分开来。

这正是普通文件系统所做的：为资源（文件/文件夹）确定一个唯一路径，这些资源没有唯一名称。

（由于服务器端可以执行此分配 - 向Item添加Parent字段，然后添加一个简单的getUniqueResourceId（）方法，通过Parent链接向上迭代树以组成唯一路径+ getResourceId（），并将其传递给客户端而不是getResourceId（）- HTML前端不需要受到影响。）

- El Zorko