寻找更好的树状数据结构

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我认为不必要的方法，但在向后端发送请求之前是条带魔法......）并且我正在寻找一个更好的解决方案。

我可以修改前端和后端。我想到了某种带有节点的树，例如：

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

并使用someUniqueHash.

有没有更好的方法来实现相同的结果，而无需在前端复制整个结构？

Answer 1

只断言该项目的 id 对于您正在创建的菜单来说是本地唯一的，并且当子项附加到每个项目时更新对父项的引用怎么样？

这将允许您展开 url 中关注的任何内容的子树，前端（假设为 html）将动态导航菜单，向用户呈现各种类别。

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

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中注册的子级。

我希望本文描述的解决方案可以为您提供解决问题的灵感！