Java: превращение строк в дерево - PullRequest
2 голосов
/ 31 января 2012

У меня есть отсортированный список строк, которые являются каталогами, которые мне нужно отобразить в виде дерева.

Например, если у меня есть эти строки:

"folder a/folder b/file 1"
"folder a/folder b/file 2"
"folder a/folder c"

Мне нужноотобразить их как:

folder a
|- folder b
|  |- file 1
|  |- file 2
|- folder c

В настоящее время я думаю о том, чтобы просмотреть список и отследить «родительскую папку» (т. е. «папку a / folder b» для первой строки) и построить деревов зависимости от того, совпадает ли «родительская папка».Это кажется довольно сложным при перемещении назад по родительским папкам, и мне было интересно, если кто-нибудь мог бы порекомендовать более простой / более эффективный способ сделать это?

Поможет ли это перебрать строки и на самом деле сначала построить дерево,а затем перебрать дерево перед его отображением?Возможно, стоит отметить, что все данные сохраняются в виде строк (это дерево не будет сохранено), поэтому для этого требуется, чтобы я строил древовидную структуру данных каждый раз, когда я хочу ее отобразить.

Ответы [ 6 ]

6 голосов
/ 31 января 2012

Надеюсь, это поможет.Строит всю структуру каталогов.Прошу прощения за короткие имена и отсутствие дженериков.Надеюсь, это будет более читабельным.

public static void main(String[] args) {
    ArrayList<String> listOfPaths = new ArrayList<String>();
    listOfPaths.add("folder a/folder b/file 1");
    listOfPaths.add("folder a/folder b/file 2");
    listOfPaths.add("folder a/folder c");

    TreeMap structure = new TreeMap();
    for (String path : listOfPaths) {
        String[] tmp = path.split("/", 2); // [ "folder a/", "folder b/file 1"]  for first loops step
        put(structure, tmp[0], tmp[1]);
    }

    print(structure, "");
}
private static void put(TreeMap structure, String root, String rest) {
    String[] tmp = rest.split("/", 2);

    TreeMap rootDir = (TreeMap) structure.get(root);

    if (rootDir == null) {
        rootDir = new TreeMap();
        structure.put(root, rootDir);
    }
    if (tmp.length == 1) { // path end
        rootDir.put(tmp[0], null);
    } else {
        put(rootDir, tmp[0], tmp[1]);
    }
}
private static void print(TreeMap map, String delimeter) {
    if (map == null || map.isEmpty())
        return;
    for (Object m : map.entrySet()) {
        System.out.println(delimeter + "-" + ((Map.Entry)m).getKey());
        print((TreeMap)((Map.Entry)m).getValue(), " |" + delimeter);
    }
}
4 голосов
/ 31 января 2012

Если вы просто хотите распечатать дерево, вы можете проверить этот фрагмент. Он выводит то, что вы хотите.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class StringTree {

    public static void main(String[] args) {

    List<String> folders = new ArrayList<String>();
    folders.add("folder a/folder b/file 1");
    folders.add("folder a/folder b/file 2");
    folders.add("folder a/folder c");
    // for a non-lexically sorted folder list
    Collections.sort(folders);

    Map<Integer, String> map = new HashMap<Integer, String>();
    for (String path : folders) {
        String[] parsedPath = path.split("/");
        boolean newBranch = false;
        for (int i = 0; i < parsedPath.length; i++) {
        newBranch |= !parsedPath[i].equals(map.get(i));
        if (newBranch) {
            map.put(i, parsedPath[i]);
            print(i, parsedPath[i]);
        }
        }
    }
    }

    private static void print(int level, String item) {
    String tab = "";
    for (int i = 0; i < level; i++)
        tab = tab + ((i == 0) ? "| " : "|- ");
    System.out.println(tab + item);
    }

}

Обновление: Исправлена ​​ошибка с данными:

folders.add("folder a/folder b/file 1");
folders.add("folder b/folder b/file 1");
1 голос
/ 31 января 2012

Я думаю, многое зависит от вашей конечной цели.Если это просто для того, чтобы распечатать данные, или если вам нужно обработать данные, или если вам нужно манипулировать ими алгоритмически.

Мой инстинкт инстинкта состоит в том, чтобы делать все это с использованием LinkedHashMap и в основном делатьэто карта карты, и т. д. Однако сделать это аккуратно может быть немного сложно, поскольку у вас есть два различных возможных значения для вашей карты - папка и файл.Обратите внимание, что LinkedHashMap используется для поддержания порядка данных при их вставке.Если вы хотите, чтобы это было отсортировано, или в случайном порядке, то вы можете выбрать другие реализации.

По сути, я бы увидел это как что-то вроде следующего (псевдокод)

public interface DirectoryEntry{
  boolean isFile;
  boolean isFolder;
}

public class Folder implements DirectoryEntry{
    public boolean isFile(){ return false;}
    public boolean isFolder(){ return true;}

    private Map<String, DirectoryEntry> entries = new LinkedHashMap<String, DriectoyrEntry>();

    public Map<String, DirectoryEntry>getEntries(){ return entries;}
    public void addFile( String filename ){ entries.put( filename, new File();}
    public void addFolder( String foldername){entries.put(foldername, new Folder();}
}

public class File implements DirectoryEntry{
    public boolean isFile(){ return true;}
    public boolean isFolder(){ return false;}
 }

Затем соберитедерево (вы также можете сделать это рекурсивно):

Map<String, DirectoryEntry> entries = new LinkedHashMap<String, DirectoryEntry>()

while( !end of list){
  Map entry = entries;

  1. Split string on '/'
  2. foreach( token ){
         if file
        entries.put( token, new File() );
         else{
        if( !entry.containsKey( token ) )
           entry.put(token, new Folder );

        // use the folder map for any sub-folders/files
        entry = ((Folder)entry.get( token )).getEntries();
         }
  }
}

Затем вы можете просмотреть свой окончательный список и играть с ним, как вам нравится.Я специально создал Файл и Папку, но вы можете добавить туда дополнительные метаданные / информацию, если у вас есть необходимость.

Имейте в виду, что это всего лишь один из вариантов, чтобы дать вам представление о том, как анализировать/ map файлы / папки, но не предназначенные как функциональное решение, как есть.

Что касается того, проще ли сначала анализировать и печатать, как я уже сказал, все зависит от того, чего вы надеетесь достичь с помощью окончательного варианта.набор данных.Но мой инстинктивный инстинкт должен был бы проанализировать все это и затем показать то, что вы проанализировали, чтобы убедиться, что то, что вы показываете, является тем, что вы «поняли» и будете манипулировать им.

0 голосов
/ 13 декабря 2013

У меня есть реализация дерева, которая может сделать это с помощью простого кода:

PathTreeBuilder.Funnel<String, String> urlFunnel = new PathTreeBuilder.Funnel<String, String>() {
    @Override
    public List<String> getPath(String value) {
        return Lists.newArrayList(value.split("/"));
    }
};
PathTreeBuilder<String, String> builder = new PathTreeBuilder<String, String>(urlFunnel);
List<Tree<String>> build = builder.build(urls);
build.toStringTree();

Надеюсь, это кому-нибудь пригодится.

0 голосов
/ 31 января 2012

Лучше сначала построить дерево, а затем отобразить, так как это может вместить любые изменения позже.Вы можете создать объект Node, например

class Node{
  // level deep of this node, can use to format the display like
  // 4 level deep will have four leading spaces
  private int level;
  // the actual text
  private String text;
  // Parent Node for this, can be null if this is the root node, set this when creating
  private Node parent;
  // children of this Node
  private List<Node> children; 
  // Getters and setters for the above properties....
}
0 голосов
/ 31 января 2012

По сути, все начинается с «корня». Что вы можете сделать, это:

while(!End of List)
{
    tempNode = Root;
    1. Resolve each line into tokens (with '/' as delimiter)
    2. while(hasMoreTokens())
       {
           3. Check if nextToken() is the child of tempNode
           4. If not, create node with nextToken(), continue till all tokens of line are exhausted.
           5. If yes, go to tempNode.nextToken(). Go to step 3.
       }
}

Таким образом, вы создаете дерево каждый раз, когда проходите каждую строку списка.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...