algorithm – Build a tree structure (for a table of contents) from an array in Java

algorithm – Build a tree structure (for a table of contents) from an array in Java

Here is a working example on Ideone. The code is also below:

public static class Node{
    int level;
    List<Node> children = new ArrayList<Node>();
    Node(int level){ this.level = level;}
}

public static void main (String[] args) throws java.lang.Exception{
    String[] h = {H1, H1, H2, H3, H3, H5, H2, H2, H3, H4,
                  H2, H2, H2, H1, H2, H2, H3,H4, H4, H2};
                        
    Node[] mostRecent = new Node[6];                      // 5 headers + 1 root tag.
    mostRecent[0] = new Node(0);                          // root tag (level = 0)

    for(int i = 0; i < h.length; i++){
        int level = Integer.parseInt(+h[i].charAt(1));  // get tags level
        Node n = new Node(level);                         // create Node for tag
        mostRecent[level] = n;                            // update most recent tag
              
        int pLevel = level - 1;                          
        while(mostRecent[pLevel] == null) --pLevel;       // find nearest parent
        mostRecent[pLevel].children.add(n);               // append tag Node to parent
        
        for(int j = 1; j < level; j++)                    // print tag with indention
            System.out.print(t);
        System.out.println(h[i]);
    } 
}

Code Explaination:

It runs in O(n) time by simply walking though the list of headers h in a for-loop, and keeping track of the most recent H1, H2, H3, and H4, in an array, Node[].

The array is used to retrieved the most recent node of tag Hi by referencing its level using the corresponding integer. For instance, the node with the most recent H1 tag is retrieved using mostRecent[1] (note, element 0 is the used as the root of the whole document).

Note: If you need a dedicated function to print the tree see this Ideone.

Here ya go:

class Example
{
    static class Node
    {
        final String name;
        final int indent;
        Collection<Node> children = new LinkedList<> ();

        Node (final String name)
        {
            this.name = name;
            this.indent = Integer.valueOf (name.substring (1));
        }
        Collection<Node> getChildren ()
        {
            return Collections.unmodifiableCollection (this.children);
        }
        void addChild (final Node child)
        {
            this.children.add (child);
        }
        @Override
        public String toString ()
        {
            final StringBuilder sb = new StringBuilder ();
            for (int i = 0; i < this.indent; i++)
                sb.append (   );
            sb.append (this.name).append (n);
            for (final Node node : this.children)
                sb.append (node.toString ());
            return sb.toString ();
        }
    }

    List<Node> contents = new LinkedList<> ();
    ArrayList<Node> stack = new ArrayList<> ();

    public void add (final String[] headers)
    {
        for (final String h : headers)
        {
            final int n = Integer.valueOf (h.substring (1));
            final Node node = new Node (h);

            while (this.stack.size () > n - 1)
                this.stack.remove (this.stack.size () - 1);

            if (n == 1)
            {
                this.contents.add (node);
                this.stack.add (node);
            }
            else
            {
                this.stack.get (n - 2).addChild (node);

                if (this.stack.size () < n)
                {
                    assert (this.stack.size () == n - 1);
                    this.stack.add (node);
                }
            }
        }
        this.stack.clear ();
    }

    @Override
    public String toString ()
    {
        final StringBuilder sb = new StringBuilder ();
        for (final Node node : this.contents)
            sb.append (node.toString ());
        return sb.toString ();
    }
}

To use:

    final Example ex = new Example ();
    ex.add (new String[] {H1, H1, H2, H3, H3, H2, H2, H3, H4, H2, H2,
            H2, H1, H2, H2, H3, H4, H4, H2});
    System.out.println (ex);

algorithm – Build a tree structure (for a table of contents) from an array in Java

Leave a Reply

Your email address will not be published. Required fields are marked *