给定一组随机分布的键,每个键都映射到一组值,您将如何将其转换为多棵树?
示例数据集
- NB2 => {NC2 ND2
- ND1 => {NG1 NH1}
- NA1 => {NB1}
- NB1 => {NC1 ND1 NE1}
- NA2 => {NB2}
- NC1 => {NF1}
- NE1 => {NI1 NJ1 NK1}
NA1的结果树
NA1 `-- NB1 |-- NC1 | `-- NF1 |-- ND1 | |-- NG1 | `-- NH1 `-- NE1 |-- NI1 |-- NJ1 `-- NK1
NA2的结果树
NA2 `-- NB2 |-- NC2 `-- ND2
最佳答案
我不知道有任何库方法可以进行这种转换。这就是我的做法。 IMO,这非常简单。
public class Tree {
public Tree(String key) {
// ...
}
public void addChild(Tree child) {
// ...
}
}
public Set<Tree> transform(Map<String, List<String>> input) {
// Potential tree roots. We start with all LHS keys as potential roots,
// and eliminate them when we see their keys on the RHS.
Set<String> roots = new HashSet<String>(input.keySet());
// This map associates keys with the tree nodes that we create for them
Map<String, Tree> map = new HashMap<String, Tree>();
for (Map.Entry<String, List<String>> entry : input.entrySet()) {
String key = entry.getKey();
List<String> childKeys = entry.getValue();
Tree tree = map.get(key);
if (tree == null) {
tree = new Tree(key);
map.put(key, tree);
}
for (String childKey : childKeys) {
roots.remove(childKey);
Tree child = map.get(childKey);
if (child == null) {
child = new Tree(childKey);
map.put(childKey, child);
}
tree.addChild(child);
}
}
Set<Tree> res = new HashSet<Tree>(roots.size());
for (String key : roots) {
res.add(map.get(key));
}
return res;
}
编辑:请注意,如果输入表示一组 DAG(有向无环图),则此算法将“有效”。但是,我刚刚意识到生成的一组树将共享输入数据中任何公共(public)子树的 TreeNode 实例。
请注意我还没有调试这段代码:-)
关于java - 将具有多个值的 map 转换为树?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1250169/