Construct a tree structure from list of string paths

Asked 2009-06-17T07:18:21.453

I have a collection of string paths like ["x1/x2/x3","x1/x2/x4","x1/x5"] in a list. I need to construct a tree-like structure from this list which can be iterated to get a pretty printed tree. like this

Any ideas/suggestions? I believe that the problem can be attacked first by processing the list of strings EDIT: The correct answer chosen was an elegant implementation, other suggestions were good too.

java tree

Edit Report

2 Answers

Follow an implementation of naive implementation of a visitable tree:

class Tree<T> implements Visitable<T> {

    // NB: LinkedHashSet preserves insertion order
    private final Set<Tree> children = new LinkedHashSet<Tree>();
    private final T data;

    Tree(T data) {
        this.data = data;
    }

    void accept(Visitor<T> visitor) {
        visitor.visitData(this, data);

        for (Tree child : children) {
            Visitor<T> childVisitor = visitor.visitTree(child);
            child.accept(childVisitor);
        }
    }

    Tree child(T data) {
        for (Tree child: children ) {
            if (child.data.equals(data)) {
                return child;
            }
        }

        return child(new Tree(data));
    }

    Tree child(Tree<T> child) {
        children.add(child);
        return child;
    }
}

interfaces for Visitor Pattern:

interface Visitor<T> {

    Visitor<T> visitTree(Tree<T> tree);

    void visitData(Tree<T> parent, T data);
}

interface Visitable<T> {

    void accept(Visitor<T> visitor);
}

sample implementation for Visitor Pattern:

class PrintIndentedVisitor implements Visitor<String> {

    private final int indent;

    PrintIndentedVisitor(int indent) {
        this.indent = indent;
    }

    Visitor<String> visitTree(Tree<String> tree) {
        return new IndentVisitor(indent + 2);
    }

    void visitData(Tree<String> parent, String data) {
        for (int i = 0; i < indent; i++) { // TODO: naive implementation
            System.out.print(" ");
        }

        System.out.println(data);
    }
}

and finally (!!!) a simple test case:

    Tree<String> forest = new Tree<String>("forest");
    Tree<String> current = forest;

    for (String tree : Arrays.asList("x1/x2/x3", "x


                        
                        
                            answered 2009-06-17T09:15:08.567


            
            
                
                    
                        
                            
                            
                        
                        2
                        
                            
                            
                        
                        
                    
                    
                        
                        Create an Object Node which contains a parent (Node) and a List of children (Node).

First split the string using ",". For every splitted string you split the string using "/".
Search for the first node identifier (e.g x1) in the root list. 
If you can find it, use the node to find the next node identifier (e.g. x2).

If you can not find a node, add the node to the last node you was able to find in the existing lists.

After you have created the list structure, you can print the list to the screen. I would make it recursive.

NOT TESTED, just an animation

public void print(List nodes, int deep) {
    if (nodes == null || nodes.isEmpty()) {
        return;
    }

    StringBuffer buffer = new StringBuffer();
    for (int i = 0; i < deep; i++) {
        buffer.append("---");
    }

    for (Iterator iterator = nodes.iterator(); iterator.hasNext();) {
        Node node = (Node)iterator.next();

        System.out.println(buffer.toString() + " " + node.getIdentifier());

        print(node.getChildren(), deep + 1);
    }
}


                        
                        
                            answered 2009-06-17T07:52:51.430



        
        
            Your Answer