从平面数据生成层次结构

Question

我需要从平面数据生成层次结构。这个问题不是用于家庭作业或面试测试，尽管我想这对任何一个都是一个很好的例子。我看过 this and this and this，其中 none 完全符合我的情况。

我的数据如下。我有一个对象列表。每个对象都有面包屑和文本。示例如下：

Object 1:
---------
breadcrumb: [Person, Manager, Hourly, New]
text: hello world

Object 2:
---------
breadcrumb: [Person, Manager, Salary]
text: hello world again

我需要将其转换为层次结构：

Person
  |--Manager
       |--Hourly
            |--New
                 |--hello world
       |--Salary
             |--hello world again

我在 Java 中执行此操作，但任何语言都可以。

Answer 1

你需要一个 Trie 数据结构，其中每个 Node 包含 children List<Node>

Trie本身应该包含一个Node--根，最初是空的；
当新序列到达时，遍历它的项目试图在当前Node的现有children中找到对应的值，如果找到对应的项目则继续前进。这样你就找到了一个存在于 trie 中的最长前缀，对于给定的序列是通用的；
如果最长公共前缀没有覆盖整个序列，则使用剩余项构建一个节点链，其中每个节点只有一个 child（下一项），并将其附加为child 到您在第 (2) 步停止的节点。

你看，这可没那么容易。实现代码会很长而且不明显。不幸的是，JDK 没有标准的 trie 实现，但您可以尝试找到一些现有的或编写您自己的。

有关详细信息，请参阅 https://en.wikipedia.org/wiki/Trie#Algorithms

从平面数据生成层次结构

Generating hierarchy from flat data

java

hierarchy

hierarchical-data

trie

hierarchical