Old school tree display

Old school tree display

Rate This
  • Comments 51

I'm back from my various travels, refreshed and ready for more fabulous adventures in coding. A while back I did a coding challenge for you all: to turn a sequence of strings into a fancy comma-separated list. You might also recall that I did a bit on how to generate all possible arbitrary trees, which I notated with a simple bracing format. Today, let's combine those two problems.

What I want to do is create a function which takes an arbitrary tree where each node has some string data, and turns it into a fancy string that has some nice properties. It should be compact and easy to read; the structure of the tree should be apparent from the output string. I'd like to have one node per line, and each line ends with the data in the string (which we can think of as the name of the node.)

Here's my Node class:

class Node
{
    public Node(string text, params Node[] children)
    {
        this.Text = text;
        this.Children = children ?? new Node[] {};
    }
    public string Text { get; private set; }
    public IList<Node> Children { get; private set; }
}

Pretty straightforward. Note that there are no parent pointers.

My challenge to you is to fill in the blanks here:

sealed class Dumper
{
    static public string Dump(Node root) { /* ... */ }
    /* ... */
}

such that the Dump method produces this string:

a
├─b
│ ├─c
│ │ └─d
│ └─e
│   └─f
└─g
  ├─h
  │ └─i
  └─j

when given this tree:

var root = new Node("a",
    new Node("b",
        new Node("c",
            new Node("d")),
        new Node("e",
            new Node("f"))),
    new Node("g",    
        new Node("h",
            new Node("i")),
        new Node("j")));

Notice that I am using the Unicode "box drawing" characters │ ├ ─ └. I used to write code to build user interfaces like this back in my Commodore 64 programming days. Ah, the halcyon days of my youth.

I've posted my solution here, but NO CHEATING. Write your own solution first, and then see how yours compares to mine.

When I discussed how to build a graph colourizer / Sudoku solver in July I did some analysis of the design decisions I made along the way. What are your design criteria as you approach this problem? For example, are you going to automatically go for a recursive solution because tree problems are usually most easily solved with recursion? Or are you going for an iterative solution? Will you prioritize obvious correctness over cleverness or vice versa? Did you miss having parent pointers? And so on - I'd be interested to know what your design criteria and choices were.

And... go!

  • First i did it nearly similar, then i thought about using LINQ to solve it:

    sealed class Dumper

    {

          public static string Dump(Node root)

          {

              return Dump(root, "");

          }

         private static string Dump(Node nod, string str)

          {

              return nod.Children.Aggregate(nod.Text,

                                          (s, n) =>

                                          s + "\n" + str + (n == nod.Children.Last() ? "└─" : "├─") +

                                          Dump(n, str + (n == nod.Children.Last() ? "  " : "│ ")));

          }

    }

    Hope there's no error in it.

  • I wrote somewhat similar code to Eric's solution, and very close to the solution of person with nick Weeble:

       sealed class Dumper

       {

           public const char Cross = '\u251c';    // |-

           public const char EndCross = '\u2514'; // |_

           public const char Line = '\u2502';     // |

           public const char Space = ' ';

           static public string Dump(Node root)

           {

               if (root == null) return string.Empty;

               StringBuilder builder = new StringBuilder();

               StringBuilder prefix = new StringBuilder();

               builder.AppendLine(root.Text);

               DrawChildren(builder, prefix, root);

               return builder.ToString();

           }

           private static void DrawChildren(StringBuilder builder, StringBuilder prefix, Node node)

           {

               for (int i = 0; i < node.Children.Count; i++)

               {

                   bool isLast = i == node.Children.Count - 1;

                   builder.Append(prefix.ToString());

                   builder.Append(isLast ? EndCross : Cross);

                   builder.AppendLine(node.Children[i].Text);

                   prefix.Append(isLast ? Space : Line);

                   DrawChildren(builder, prefix, node.Children[i]);

                   prefix.Length = prefix.Length - 1;

               }

           }

       }

    But instead of string prefix, I used StringBuilder. Could you please comment whether appoach with StringBuilder for prefix is better than string? And why?

  • Very nice to hear that you're an old C64 programmer. :)

  • There is a procedure that uses two instances of the StringBuilder to consume less memory on the line indent.

    static public string Dump(Node root)

    {

    var result = new StringBuilder();

    var indent = new StringBuilder();

    Action<Node> dumpNode = null;

    dumpNode = node =>

    {

    result.AppendLine(node.Text);

    var lastIndex = node.Children.Count - 1;

    for (var i = 0; i < lastIndex; i++)

    {

    result.Append(indent);

    result.Append("├─");

    indent.Append("│ ");

    dumpNode(node.Children[i]);

    indent.Length = indent.Length - 2;

    }

    if (lastIndex >= 0)

    {

    result.Append(indent);

    result.Append("└─");

    indent.Append("  ");

    dumpNode(node.Children[lastIndex]);

    indent.Length = indent.Length - 2;

    }

    };

    dumpNode(root);

    return result.ToString();

    }

  • If not too late...

    string Output(Node root)

    {

    var sb = new StringBuilder();

    Output(sb, root, new bool[0]);

    return sb.ToString();

    }

    void Output(StringBuilder sb, Node node, bool[] levels)

    {

    for (int i = 0; i < levels.Length; ++i)

    {

    bool b = levels[i];

    if (i < levels.Length - 1)

    {

    if (b)

    {

    sb.Append("│ ");

    }

    else

    {

    sb.Append("  ");

    }

    }

    else

    {

    if (b)

    {

    sb.Append("├─");

    }

    else

    {

    sb.Append("└─");

    }

    }

    }

    sb.AppendLine(node.Text);

    foreach (var child in node.Children)

    {

    Output(sb, child, levels.Concat(new[] { child != node.Children.Last() }).ToArray());

    }

    }

  • static public string Dump(Nodee root)

           {

               int count = 0;

               string dumStr = root.Text;

               dumStr += DumpIn(root.Children, count);            

               return dumStr;

           }

           private static string DumpIn(IList<Nodee> root, int count)

           {

               string dumStr = "";

               foreach (var nod in root)

               {

                   dumStr += '\n' + count.Times("│ ") + ((nod.Children.Count == 0) ? "└─" : "├─") + nod.Text;              

                   dumStr += DumpIn(nod.Children, count + 1);                              

               }

               return dumStr;

           }

           static string Times(this int src,string ch)

           {

               string res = "";

               for (int i = 0; i < src; i++)

               {

                   res += ch;

               }

               return res;

           }

Page 4 of 4 (51 items) 1234