Visualize a tree

Visualize a tree
You are encouraged to solve this task according to the task description, using any language you may know.

A tree structure (i.e. a rooted, connected acyclic graph) is often used in programming. It's often helpful to visually examine such a structure. There are many ways to represent trees to a reader, such as indented text (à la unix tree command), nested HTML tables, hierarchical GUI widgets, 2D or 3D images, etc.

Task: Write a program to produce a visual representation of some tree. The content of the tree doesn't matter, nor does the output format, the only requirement being that the output is human friendly. Make do with the vague term "friendly" the best you can.

BBC BASIC

Works with: BBC BASIC for Windows

This creates a native Windows Tree View control:

      INSTALL @lib$+"WINLIB5"
      ON ERROR SYS "MessageBox", @hwnd%, REPORT$, 0, 0 : QUIT
 
      REM!WC Windows constants:
      TVI_SORT = -65533
      TVIF_TEXT = 1
      TVM_INSERTITEM = 4352
      TVS_HASBUTTONS = 1
      TVS_HASLINES = 2
      TVS_LINESATROOT = 4
 
      REM. TV_INSERTSTRUCT
      DIM tvi{hParent%,       \
      \       hInsertAfter%,  \
      \       mask%,          \
      \       hItem%,         \
      \       state%,         \
      \       stateMask%,     \
      \       pszText%,       \
      \       cchTextMax%,    \
      \       iImage%,        \
      \       iSelectedImage%,\
      \       cChildren%,     \
      \       lParam%         \
      \      }
 
      SYS "InitCommonControls"
      hTree% = FN_createwindow("SysTreeView32", "", 0, 0, @vdu.tr%, @vdu.tb%, 0, \
      \                        TVS_HASLINES OR TVS_HASBUTTONS OR TVS_LINESATROOT, 0)
      hroot% = FNinsertnode(0, "Root")
      hchild1% = FNinsertnode(hroot%, "Child 1")
      hchild2% = FNinsertnode(hroot%, "Child 2")
      hchild11% = FNinsertnode(hchild1%, "Grandchild 1")
      hchild12% = FNinsertnode(hchild1%, "Grandchild 2")
      hchild21% = FNinsertnode(hchild2%, "Grandchild 3")
      hchild22% = FNinsertnode(hchild2%, "Grandchild 4")
 
      REPEAT
        WAIT 1
      UNTIL FALSE
      END
 
      DEF FNinsertnode(hparent%, text$)
      LOCAL hnode%
      text$ += CHR$0
 
      tvi.hParent% = hparent%
      tvi.hInsertAfter% = TVI_SORT
      tvi.mask% = TVIF_TEXT
      tvi.pszText% = !^text$
 
      SYS "SendMessage", hTree%, TVM_INSERTITEM, 0, tvi{} TO hnode%
      IF hnode% = 0 ERROR 100, "TVM_INSERTITEM failed"
      SYS "InvalidateRect", hTree%, 0, 0
      = hnode%

C

Print a simple tree to standard output:

#include <stdio.h>
#include <stdlib.h>
 
typedef struct stem_t *stem;
struct stem_t { const char *str; stem next; };
 
void tree(int root, stem head)
{
	static const char *sdown = "  |", *slast = "  `", *snone = "   ";
	struct stem_t col = {0, 0}, *tail;
 
	for (tail = head; tail; tail = tail->next) {
		printf("%s", tail->str);
		if (!tail->next) break;
	}
 
	printf("--%d\n", root);
 
	if (root <= 1) return;
 
	if (tail && tail->str == slast)
		tail->str = snone;
 
	if (!tail)	tail = head = &col;
	else		tail->next = &col;
 
	while (root) { // make a tree by doing something random
		int r = 1 + (rand() % root);
		root -= r;
		col.str = root ? sdown : slast;
 
		tree(r, head);
	}
 
	tail->next = 0;
}
 
int main(int c, char**v)
{
	int n;
	if (c < 2 || (n = atoi(v[1])) < 0) n = 8;
 
	tree(n, 0);
	return 0;
}

Output:

--8
  `--8
     |--7
     |  |--3
     |  |  |--2
     |  |  |  `--2
     |  |  |     `--2
     |  |  |        |--1
     |  |  |        `--1
     |  |  `--1
     |  |--2
     |  |  |--1
     |  |  `--1
     |  |--1
     |  `--1
     `--1

D

Translation of: Haskell

import std.stdio, std.conv, std.algorithm, std.array;
 
struct Node(T) { T value; Node* left, right; }
 
string[] treeIndent(T)(in Node!T* t) {
    if (!t) return ["-- (null)"];
    const tr = t.right.treeIndent;
    return "--" ~ t.value.text ~
           t.left.treeIndent.map!q{"  |" ~ a}.array ~
           ("  `" ~ tr[0]) ~ tr[1 .. $].map!q{"   " ~ a}.array;
}
 
void main () {
    static N(T)(T v, Node!T* l=null, Node!T* r=null) {
        return new Node!T(v, l, r);
    }
 
    const tree = N(1, N(2, N(4, N(7)), N(5)), N(3, N(6, N(8), N(9))));
    writefln("%-(%s\n%)", tree.treeIndent);
}

Output:

--1
  |--2
  |  |--4
  |  |  |--7
  |  |  |  |-- (null)
  |  |  |  `-- (null)
  |  |  `-- (null)
  |  `--5
  |     |-- (null)
  |     `-- (null)
  `--3
     |--6
     |  |--8
     |  |  |-- (null)
     |  |  `-- (null)
     |  `--9
     |     |-- (null)
     |     `-- (null)
     `-- (null)

Go

Not the most economical output, but at least json.MarshalIndent is in the Go standard library. Note that the definition of Node has nothing JSON specific about it; it's an ordinary struct.

package main
 
import (
    "encoding/json"
    "fmt"
    "log"
)
 
type Node struct {
    Name     string
    Children []*Node
}
 
func main() {
    tree := &Node{"root", []*Node{
        &Node{"a", []*Node{
            &Node{"d", nil},
            &Node{"e", []*Node{
                &Node{"f", nil},
            }}}},
        &Node{"b", nil},
        &Node{"c", nil},
    }}
    b, err := json.MarshalIndent(tree, "", "   ")
    if err != nil {
        log.Fatal(err)
    }
    fmt.Println(string(b))
}

Output:

{
   "Name": "root",
   "Children": [
      {
         "Name": "a",
         "Children": [
            {
               "Name": "d",
               "Children": null
            },
            {
               "Name": "e",
               "Children": [
                  {
                     "Name": "f",
                     "Children": null
                  }
               ]
            }
         ]
      },
      {
         "Name": "b",
         "Children": null
      },
      {
         "Name": "c",
         "Children": null
      }
   ]
}

Haskell

Tree borrowed from Tree traversal:

data Tree a = Empty | Node { value :: a, left :: Tree a, right :: Tree a }
	deriving (Show, Eq)
 
tree = Node 1 (Node 2 (Node 4 (Node 7 Empty Empty) Empty)
	(Node 5 Empty Empty)) (Node 3 (Node 6 (Node 8 Empty Empty)
	(Node 9 Empty Empty)) Empty)
 
treeIndent Empty = ["-- (nil)"]
treeIndent t = ["--" ++ show (value t)]
	++ map ("  |"++) ls ++ ("  `" ++ r):map ("   "++) rs
	where
	(r:rs) = treeIndent$right t
	ls     = treeIndent$left t
 
main = mapM_ putStrLn $ treeIndent tree

Output:

--1
  |--2
  |  |--4
  |  |  |--7
  |  |  |  |-- (nil)
  |  |  |  `-- (nil)
  |  |  `-- (nil)
  |  `--5
  |     |-- (nil)
  |     `-- (nil)
  `--3
     |--6
     |  |--8
     |  |  |-- (nil)
     |  |  `-- (nil)
     |  `--9
     |     |-- (nil)
     |     `-- (nil)
     `-- (nil)

J

See: j:Essays/Tree Display

JavaScript

Javascript wrapped in HTML5 document. Should work in modern browsers.

<!doctype html>
<html id="doc">
  <head><meta charset="utf-8"/>
    <title>Stuff</title>
    <script type="application/javascript">
	function gid(id) { return document.getElementById(id); }
 
	function ce(tag, cls, parent_node) {
		var e = document.createElement(tag);
		e.className = cls;
		if (parent_node) parent_node.appendChild(e);
		return e;
	}
 
	function dom_tree(id) {
		gid('tree').textContent = "";
		gid('tree').appendChild(mktree(gid(id), null));
	}
 
	function mktree(e, p) {
		var t = ce("div", "tree", p);
		var tog = ce("span", "toggle", t);
		var h = ce("span", "tag", t);
 
		if (e.tagName === undefined) {
			h.textContent = "#Text";
			var txt = e.textContent;
			if (txt.length > 0 && txt.match(/\S/)) {
				h = ce("div", "txt", t);
				h.textContent = txt;
			}
			return t;
		}
 
		tog.textContent = "−";
		tog.onclick = function () { clicked(tog); }
		h.textContent = e.nodeName;
 
		var l = e.childNodes;
		for (var i = 0; i != l.length; i++)
			mktree(l[i], t);
		return t;
	}
 
	function clicked(e) {
		var is_on = e.textContent == "−";
		e.textContent = is_on ? "+" : "−";
		e.parentNode.className = is_on ? "tree-hide" : "tree";
	}
    </script>
    <style>
      #tree { white-space: pre; font-family: monospace; border: 1px solid }
      .tree > .tree-hide, .tree > .tree
		{ margin-left: 2em; border-left: 1px dotted rgba(0,0,0,.2)}
      .tree-hide > .tree, .tree-hide > .tree-hide { display: none }
      .tag { color: navy }
      .tree-hide > .tag { color: maroon }
      .txt { color: gray; padding: 0 .5em; margin: 0 .5em 0 2em; border: 1px dotted rgba(0,0,0,.1) }
      .toggle { display: inline-block; width: 2em; text-align: center }
    </style>
  </head>
  <body>
    <article>
      <section>
        <h1>Headline</h1>
        Blah blah
      </section>
      <section>
        <h1>More headline</h1>
        <blockquote>Something something</blockquote>
        <section><h2>Nested section</h2>
	  Somethin somethin list:
	  <ul>
	    <li>Apples</li>
	    <li>Oranges</li>
	    <li>Cetera Fruits</li>
	  </ul>
	</section>
      </section>
    </article>
    <div id="tree"><a href="javascript:dom_tree('doc')">click me</a></div>
  </body>
</html>

Mathematica

Tree graph

Make a tree graph. In Mathematica, \[DirectedEdge] will appear as an arrow in the code.

edges = {1 \[DirectedEdge] 2, 1 \[DirectedEdge] 3, 2 \[DirectedEdge] 4, 2 \[DirectedEdge] 5, 
              3 \[DirectedEdge] 6, 4 \[DirectedEdge] 7};
t = TreeGraph[edges, GraphStyle -> "VintageDiagram"]

Show the syntactical structure of the above code. Defer is added to impede TreeGraph from becoming a graphical object.

TreeForm[Defer@
  TreeGraph[{1 \[DirectedEdge] 2, 1 \[DirectedEdge] 3, 2 \[DirectedEdge] 4, 2 \[DirectedEdge] 5, 
   3 \[DirectedEdge] 6,  4 \[DirectedEdge] 7}, VertexLabels -> "Name"]]

Opener view

Here's another way to display a tree. The triangles open/close when clicked on.

OpenerView[{1, Column@{OpenerView[{2, Column@{OpenerView[{4, 7}, True], 5}}, True],
     OpenerView[{3,  OpenerView[{TraditionalForm[Cos[x]], Plot[Cos[x], {x, 0, 10}, ImageSize -> 150]}, 
     True]}, True]}}, True]

Maxima

load(graphs)$
 
g: random_tree(10)$
 
is_tree(g);
true
 
draw_graph(g)$

Perl 6

sub visualize-tree($tree, &label, &children,
                   :$indent = '',
                   :@mid = ('├─', '│ '),
                   :@end = ('└─', '  '),
) {
    sub visit($node, *@pre) {
        gather {
            take @pre[0] ~ label($node);
            my @children := children($node);
            my $end = @children.end;
            for @children.kv -> $_, $child {
                when $end { take visit($child, (@pre[1] X~ @end)) }
                default   { take visit($child, (@pre[1] X~ @mid)) }
            }
        }
    }
    visit($tree, $indent xx 2);
}
 
# example tree built up of pairs
my $tree = root=>[a=>[a1=>[a11=>[]]],b=>[b1=>[b11=>[]],b2=>[],b3=>[]]];
 
.say for visualize-tree($tree, *.key, *.value.list);

Output:

root
├─a
│ └─a1
│   └─a11
└─b
  ├─b1
  │ └─b11
  ├─b2
  └─b3

PicoLisp

'view' is a built-in function in PicoLisp.

(view '(1 (2 (3 (4) (5) (6 (7))) (8 (9)) (10)) (11 (12) (13))))

Output:

+-- 1
|
+---+-- 2
|   |
|   +---+-- 3
|   |   |
|   |   +---+-- 4
|   |   |
|   |   +---+-- 5
|   |   |
|   |   +---+-- 6
|   |       |
|   |       +---+-- 7
|   |
|   +---+-- 8
|   |   |
|   |   +---+-- 9
|   |
|   +---+-- 10
|
+---+-- 11
    |
    +---+-- 12
    |
    +---+-- 13

Prolog

XPCE

XPCE is the SWI-Prolog native GUI library.

% direction may be horizontal/vertical/list
display_tree(Direction) :-
	sformat(A, 'Display tree ~w', [Direction]),
	new(D, window(A)),
	send(D, size, size(350,200)),
	new(T, tree(text('Root'))),
	send(T, neighbour_gap, 10),
	new(S1, node(text('Child1'))),
	new(S2, node(text('Child2'))),
	send_list(T, son,[S1,S2]),
	new(S11, node(text('Grandchild1'))),
	new(S12, node(text('Grandchild2'))),
	send_list(S1, son, [S11, S12]),
	new(S21, node(text('Grandchild3'))),
	new(S22, node(text('Grandchild4'))),
	send_list(S2, son, [S21, S22]),
	send(T, direction, Direction),
	send(D, display, T),
	send(D, open).
 

Python

Python has the pprint module for pretty-printing data.

Python 3.2.3 (default, May  3 2012, 15:54:42) 
[GCC 4.6.3] on linux2
Type "copyright", "credits" or "license()" for more information.
>>> help('pprint.pprint')
Help on function pprint in pprint:
 
pprint.pprint = pprint(object, stream=None, indent=1, width=80, depth=None)
    Pretty-print a Python object to a stream [default is sys.stdout].
 
>>> from pprint import pprint
>>> for tree in [ (1, 2, 3, 4, 5, 6, 7, 8),
	          (1, (( 2, 3 ), (4, (5, ((6, 7), 8))))),
	          ((((1, 2), 3), 4), 5, 6, 7, 8) ]:
	print("\nTree %r can be pprint'd as:" % (tree, ))
	pprint(tree, indent=1, width=1)
 
 
 
Tree (1, 2, 3, 4, 5, 6, 7, 8) can be pprint'd as:
(1,
 2,
 3,
 4,
 5,
 6,
 7,
 8)
 
Tree (1, ((2, 3), (4, (5, ((6, 7), 8))))) can be pprint'd as:
(1,
 ((2,
   3),
  (4,
   (5,
    ((6,
      7),
     8)))))
 
Tree ((((1, 2), 3), 4), 5, 6, 7, 8) can be pprint'd as:
((((1,
    2),
   3),
  4),
 5,
 6,
 7,
 8)
>>> 

Racket

 
#lang racket/base
 
(define (visualize t0)
  (let loop ([t t0] [last? #t] [indent '()])
    (define (I mid last) (cond [(eq? t t0) ""] [last? mid] [else last]))
    (for-each display (reverse indent))
    (unless (eq? t t0) (printf "|\n"))
    (for-each display (reverse indent))
    (printf "~a~a\n" (I "\\-" "+-") (car t))
    (for ([s (cdr t)] [n (in-range (- (length t) 2) -1 -1)])
      (loop s (zero? n) (cons (I "  " "| ") indent)))))
 
(visualize '(1 (2 (3 (4) (5) (6 (7))) (8 (9)) (10)) (11 (12) (13))))
 

Output:

1
|
+-2
| |
| +-3
| | |
| | +-4
| | |
| | +-5
| | |
| | \-6
| |   |
| |   \-7
| |
| +-8
| | |
| | \-9
| |
| \-10
|
\-11
  |
  +-12
  |
  \-13

Tcl

Library: Tcllib (Package: struct::tree)

package require struct::tree
 
proc visualize_tree {tree {nameattr name}} {
    set path {}
    $tree walk [$tree rootname] -order both {mode node} {
	if {$mode eq "enter"} {
	    set s ""
	    foreach p $path {
		append s [expr {[$tree next $p] eq "" ? "  " : "\u2502 "}]
	    }
	    lappend path $node
	    append s [expr {
		[$tree next $node] eq "" ? "\u2514\u2500" : "\u251c\u2500"
	    }]
	    if {[$tree keyexists $node $nameattr]} {
		set name [$tree get $node $nameattr]
	    } else {
		# No node name attribute; use the raw name
		set name $node
	    }
	    puts "$s$name"
	} else {
	    set path [lrange $path 0 end-1]
	}
    }
}

Demonstrating:

# Sample tree to demonstrate with
struct::tree t deserialize {root {} {} a 0 {} d 3 {} e 3 {} f 9 {} b 0 {} c 0 {}}
visualize_tree t

Output:

└─root
  ├─a
  │ ├─d
  │ └─e
  │   └─f
  ├─b
  └─c