A Java class for printing binary trees as ASCII text
It hasn't been optimized for run time efficiency, but since we're talking about printing in ASCII, I figured it's not going to be used on very large trees. It does have some nice features though.
- It makes efficient use of space in that a large subtree extends under a smaller one as much as possible.
- It's generic, working for any binary tree data objects, as long as you can provide functions (lambda functions will do) to get a nodes label as a String, and to get the left and right sub-nodes.
- There's a parameter to set the minimum horizontal space between node labels.
- Node labels are strings of arbitrary length.
- In addition to a method for printing a single tree, there's a method for printing a list of trees horizontally across the page (with a parameter for page width), using as many rows as necessary.
- There's an option to print trees with diagonal branches (using slash and backslash characters) or with horizontal branches (using ascii box drawing characters). The latter is more compact and makes tree levels more visually clear.
- It works.
Some demo/test programs are included.
The TreePrinter object has two methods for printing binary trees as ASCII text. PrintTree prints a single tree. PrintTrees prints a list of trees horizontally across the page, in multiple rows if necessary.
The TreePrinter object has a few settable parameters affecting how it prints trees. A positive integer parameter 'hspace' specifies the minimum number of horizontal spaces between any two node labels in the tree. A boolean parameter 'squareBranches' determines whether the tree is drawn with horizontal branches (using ascii box drawing characters) or diagonal branches (using slash and backslash characters). The boolean 'lrAgnostic' parameter only affects trees drawn with the ascii box drawing characters. Its effect is is that tree nodes with only a single subtree are drawn with a straight down vertical branch, providing no indication of whether it is a left or right subtree.
A few test/demo programs are included. For instance, the program EnumTrees can be used to print an enumeration of all binary trees of a given size. All trees of size 5, labeled with number words (one, two, etc) is printed as:
mvn compile
mvn exec:java -Dexec.mainClass="EnumTrees"
This produces output like:
one one one one one one one one one
\ \ \ \ \ \ \ \ \
two two two two two three three four four
\ \ \ \ \ / \ / \ / \ / \
three three four five five two four two five two five / \
\ \ / \ / / \ / \ three five
four five / \ three four five four three /
\ / three five \ / two
five four four three
one one one one one two two two two
\ \ \ \ \ / \ / \ / \ / \
five five five five five / \ / \ one four one five
/ / / / / one three one three / \ /
two two three four four \ \ / \ three
\ \ / \ / / four five three five \
three four two four two three \ / four
\ / \ / five four
four three three two
two three three three three four four four
/ \ / \ / \ / \ / \ / \ / \ / \
one five one four / \ two four two five one five one five two five
/ \ \ / \ / \ / / \ \ / \
four two five one five one five one four two three / \
/ \ / \ / one three
three two four three two
four four five five five five five five five
/ \ / \ / / / / / / /
/ \ / \ one one one one one two two
three five three five \ \ \ \ \ / \ / \
/ / two two three four four / \ one four
one two \ \ / \ / / one three /
\ / three four two four two three \ three
two one \ / \ / four
four three three two
five five five five five five five
/ / / / / / /
three three four four four four four
/ \ / \ / / / / /
one four two four one one two three three
\ / \ \ / \ / /
two one two three / \ one two
\ / one three \ /
three two two one
RandomTree can be used to print a single randomly generated tree. The following is an example of the same tree printed 4 different ways, with horizontal spacing of 1 and of 3, and with diagonal and horizontal branches. To run this from the command line using maven type:
mvn compile
mvn exec:java -Dexec.mainClass="RandomTree"
This produces output like:
27
┌─────┴─────┐
13 29
┌──────┴──────┐ ┌─┴─┐
8 23 28 30
┌──┴──┐ ┌──┴──┐
4 11 21 26
┌─┴─┐ ┌┴┐ ┌─┴─┐ ┌┘
2 5 9 12 18 22 24
┌┴┐ └┐ └┐ ┌─┴─┐ └┐
1 3 6 10 17 19 25
└┐ ┌┘ └┐
7 15 20
┌─┴─┐
14 16
27
/ \
/ \
13 29
/ \ / \
/ \ 28 30
/ \
/ \
/ \
/ \
8 23
/ \ / \
/ \ / \
4 11 / \
/ \ / \ 21 26
2 5 9 12 / \ /
/ \ \ \ 18 22 24
1 3 6 10 / \ \
\ 17 19 25
7 / \
15 20
/ \
14 16
27
┌────────┴────────┐
13 29
┌─────────┴─────────┐ ┌──┴──┐
8 23 28 30
┌────┴────┐ ┌────┴────┐
4 11 21 26
┌──┴──┐ ┌─┴─┐ ┌──┴──┐ ┌┘
2 5 9 12 18 22 24
┌─┴─┐ └┐ └┐ ┌──┴──┐ └┐
1 3 6 10 17 19 25
└┐ ┌┘ └┐
7 15 20
┌──┴──┐
14 16
27
/ \
/ \
/ \
/ \
13 29
/ \ / \
/ \ / \
/ \ 28 30
/ \
/ \
/ \
/ \
/ \
8 23
/ \ / \
/ \ / \
/ \ / \
4 11 / \
/ \ / \ 21 26
2 5 9 12 / \ /
/ \ \ \ / \ 24
1 3 6 10 18 22 \
\ / \ 25
7 / \
17 19
/ \
15 20
/ \
/ \
14 16
There's a demo program that produces a tree diagram of all Collatz sequences (https://en.wikipedia.org/wiki/Collatz_conjecture) of a given length. This demonstrates an option to print trees in such a way that if there is only a single subtree, it is treated the same regardless of whether it is a left or right subtree. This produces output like:
1
│
2
│
4
│
8
│
16
┌─────────────────────┴─────────────────────┐
32 5
│ │
64 10
┌──────────┴──────────┐ ┌─────────┴─────────┐
128 21 20 3
│ │ │ │
256 42 40 6
┌──────────┴──────────┐ │ ┌────────┴────────┐ │
512 85 84 80 13 12
│ │ │ │ │ │
1024 170 168 160 26 24
┌─────┴─────┐ │ │ ┌────┴────┐ │ │
2048 341 340 336 320 53 52 48
│ │ ┌────┴────┐ │ │ │ ┌───┴───┐ │
4096 682 680 113 672 640 106 104 17 96
┌──┴──┐ ┌──┴──┐ │ │ │ ┌──┴──┐ ┌─┴─┐ │ │ │
8192 1365 1364 227 1360 226 1344 1280 213 212 35 208 34 192
│ │ │ │ ┌──┴──┐ ┌─┴─┐ │ │ │ │ │ ┌─┴─┐ ┌─┴─┐ │
16384 2730 2728 454 2720 453 452 75 2688 2560 426 424 70 416 69 68 11 384