将带分隔符的文件转换为树

Question

我正在努力将分隔文件转换为有序树结构。以下是示例输入...

1.2.3.4.5
1.3.2.4.5
1.2.4.5.6

我需要能够将其转换为如下所示的输出（在可搜索的树结构中）...

1
-2
--3
---4
----5
--4
---5
----6
-3
--2
---4
----5

我对此的解决方案是...

迭代文本文件并创建一个代表每一行的数组列表
使用 Collections.sort() 对数组列表进行排序
使用 TreeMap 将 "base" 记录存储为键（在本例中为 1），并使用字符串数组列表存储所有记录
迭代 TreeMap 的键并将其 arrayList 转换为包含代表每个条目的节点的 LinkedHashSet
迭代树的键并打印每个节点购买其索引值

我认为一切正常，但当我开始测试这种方法时，我发现我的输出如下所示...

1
-2
--3
---4
----5
--4
---5
----6
-3
--2

可以看出，3/2/xx 下的节点不存在，这是由于我使用的逻辑为我的节点值 (Node(3, 4)) 构建 LinkedHashSet 将只是忽略因为它是一个重复的节点。我以为我正朝着正确的方向前进，但现在我可以看到我的逻辑显然有缺陷。有没有人对这样的方法有任何建议？我当前的代码如下...

TreeBuilder.java

public class TreeBuilder {

 public static void main(String[] args) {

    // Get a list of records
    List<String> data = new ArrayList<String>();
    data.add("1.2.3.4.5");
    data.add("1.3.2.4.5");
    data.add("1.2.4.5.6");

    Collections.sort(data);

    // Build the "Base" tree
    TreeMap<String, List<String>> tree = buildBaseTree(data);

    // Build the target tree structure
    TreeMap<String, LinkedHashSet<Node>> finalTree = convertListToSet(tree);

    printRecords(finalTree);

 }

 public static void printRecords(
        TreeMap<String, LinkedHashSet<Node>> recordTree) {

    System.out.println("---------Records---------");

    for (Map.Entry<String, LinkedHashSet<Node>> entry : recordTree
            .entrySet()) {

        System.out.println(entry.getKey());

        // Print out the structured data
        StringBuilder stringBuilder = new StringBuilder();
        Iterator<Node> iterator = entry.getValue().iterator();
        while (iterator.hasNext()) {

            Node node = iterator.next();
            for (int i = 0; i < node.index; i++) {
                stringBuilder.append("-");
            }

            System.out.println(stringBuilder.toString() + node.value);

            // "reset" the builder
            stringBuilder.setLength(0);
        }
    }

 }

 private static TreeMap<String, LinkedHashSet<Node>> convertListToSet(
        TreeMap<String, List<String>> tree) {

    TreeMap<String, LinkedHashSet<Node>> finalMap = new TreeMap<String, LinkedHashSet<Node>>();
    LinkedHashSet<Node> linkedHashSet = new LinkedHashSet<Node>();

    // Iterate the entry set
    for (Map.Entry<String, List<String>> entry : tree.entrySet()) {

        List<String> records = entry.getValue();
        for (String record : records) {
            String[] recordArray = record.split("\.");

            for (int i = 1; i < recordArray.length; i++) {
                Node node = new Node(i, Integer.parseInt(recordArray[i]));
                linkedHashSet.add(node);
            }
        }

        finalMap.put(entry.getKey(), linkedHashSet);

        // reset our linkedHashSet
        linkedHashSet = new LinkedHashSet<Node>();

    }

    System.out.println("Final map " + finalMap);

    return finalMap;
 }

 /**
  * Builds a tree with base record keys and a list of records for each key.
  * 
  * @param data
  * @return
  */
 private static TreeMap<String, List<String>> buildBaseTree(List<String> data) {

    TreeMap<String, List<String>> tree = new TreeMap<String, List<String>>();
    List<String> recordList = null;

    // First find all base records
    for (String record : data) {

        String[] baseEntry = record.split("\.");
        if (!tree.containsKey(baseEntry[0])) {
            recordList = new ArrayList<String>();
            tree.put(baseEntry[0], recordList);
        }
    }

    // Now place all sub-records in each base record
    for (String record : data) {

        String[] baseEntry = record.split("\.");
        tree.get(baseEntry[0]).add(record);
    }

    System.out.println("------------------Base Tree---------------");
    System.out.println(tree);
    System.out.println("------------------------------------------");

    return tree;
 }

 private static List<String> readData(String file) {

    BufferedReader bufferedReader = null;
    try {
        bufferedReader = new BufferedReader(new FileReader(new File(file)));
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }
    List<String> data = new ArrayList<String>();

    // Get a list of all the records
    String line = null;
    try {
        while ((line = bufferedReader.readLine()) != null) {
            data.add(line);
        }
    } catch (IOException e) {
        e.printStackTrace();
    }

    // Sort the list so its ordered
    System.out.println("-------------Sorted Data Set-----------");
    Collections.sort(data);
    for (String record : data) {
        System.out.println(record);
    }
    System.out.println("---------------------------------------");

    return data;
 }
}

Node.java

public class Node implements Comparable<Node> {

 int index;
 int value;

 public Node(int index, int value) {
    this.index = index;
    this.value = value;
 }

 public int getIndex() {
    return index;
 }

 @Override
 public String toString() {
    return "Node [index=" + index + ", value=" + value + "]";
 }

 public void setIndex(int index) {
    this.index = index;
 }

 public int getValue() {
    return value;
 }

 public void setValue(int value) {
    this.value = value;
 }

 @Override
 public int compareTo(Node o) {

    Node otherNode = (Node) o;

    if (this.index > otherNode.index)
        return 1;

    if (this.index < otherNode.index) {
        return -1;
    }

    return 0;
 }

 @Override
 public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + index;
    result = prime * result + value;
    return result;
 }

 @Override
 public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Node other = (Node) obj;
    if (index != other.index)
        return false;
    if (value != other.value)
        return false;
    return true;
 }

}

Answer 1

不必很复杂。您所需要的只是 SortedMap 个 SortedMap 实例，而且只有一个技巧：为了类型安全（如果需要）对其进行递归参数化。

package com.acme;

import java.util.ArrayList;
import java.util.List;
import java.util.Map.Entry;
import java.util.TreeMap;

public class Main {

    public static void main(String[] args) {
        List<String> rows = new ArrayList<>();
        rows.add("1.2.3.4.5");
        rows.add("1.3.2.4.5");
        rows.add("1.2.4.5.6");

        MyTreeMap root = new MyTreeMap();
        for (String row : rows) {
            MyTreeMap n = root;
            String[] cells = row.split("\.");
            for (String cell : cells) {
                MyTreeMap child = n.get(cell);
                if (child == null) {
                    n.put(cell, child = new MyTreeMap());
                }
                n = child;
            }
        }

        print(root, "", "-");
    }

    static void print(MyTreeMap m, String indentationStr, String indentationStrAddition) {
        for (Entry<String, MyTreeMap> o : m.entrySet()) {
            System.out.println(indentationStr + o.getKey());
            print(o.getValue(), indentationStr + indentationStrAddition, indentationStrAddition);
        }
    }

    /**
     * This is just a construct that helps us to parameterize recursively.
     */
    static class MyTreeMap extends TreeMap<String, MyTreeMap> {private static final long serialVersionUID = 1L;}
}

Answer 2

如果我理解你的问题，你想从共享公共前缀的整数列表中创建搜索树。如果是这样，那么我认为您可以用更少的代码实现这一点：

private static class TreeNode {

    private final Map<Integer, TreeNode> children = new HashMap<>();

    public void insert(List<Integer> values) {
        if (!values.isEmpty()) {
            children.putIfAbsent(values.get(0), new TreeNode());
            children.get(values.get(0)).insert(values.subList(1, values.size()));
        }
    }

    public void print(int level) {
        for (Map.Entry<Integer, TreeNode> entry : children.entrySet()) {
            System.out.print(String.join("", Collections.nCopies(level, "-")));
            System.out.println(entry.getKey());
            entry.getValue().print(level + 1);
        }
    }
}

我不确定您是否打算对整数列表进行排序。如果是这样，您可以在代码中的适当位置添加 Collections.sort。

将带分隔符的文件转换为树

Converting a delimited file into a Tree

java

sorting

list

delimited

treeset