java - 从平面数据生成层次结构

Question

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

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

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抱着 child List<Node>

1. Trie 本身应该包含一个 Node --root，初始为空；

2. 当新序列到达时，迭代它的项目，试图在当前 Node 的现有子项中找到相应的值，如果找到相应的项目则继续前进。这样你就可以找到一个存在于 trie 中的最长前缀，对于给定的序列是通用的；

3. 如果最长公共(public)前缀没有覆盖整个序列，则使用剩余项构建节点链，其中每个节点只有一个子节点(下一项)，并将其作为子节点附加到您停止的节点在第 (2) 步。

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

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