Printing binary tree to standard output Java

Question

I'm implementing a red/black tree in Java and to verify if my tree is correct and to make debugging easier i simply copy/pasted a method that prints out the tree to standard output.

For an input sequence of: 29, 42, 23, 47, 11, 4
the method would print out:

enter image description here

With a little imagination this is in fact a red/black tree, just not with edges between the nodes.
42 is the black root with a right black child 47 and a left red child 23 (red nodes are surrounded by < and >), etc.

This is just fine for smaller trees but becomes a little complicated for larger trees.
Right now the root is to the left and the tree expands to the right. I was wondering if there are any readily available methods that print out such a tree by printing the root first, and expanding the tree downwards?

Like so:
enter image description here

Or if there is not such a method readily available, how could i change the current method so it prints like the second image?

This is the current method:

private static void printHelper(Node n, int indent) {

    if (n.getRight() != null) {
        printHelper(n.getRight(), indent + INDENT_STEP);
    }

    for (int i = 0; i < indent; i++) {
        System.out.print(" ");
    }

    if (n.getColor() == BLACK) {
        System.out.println(n.getValue());
    } else {
        System.out.println("<" + n.getValue() + ">");
    }

    if (n.getLeft() != null) {
        printHelper(n.getLeft(), indent + INDENT_STEP);
    }
}

And is being called with the root of the tree as node and 0 as indent (and INDENT_STEP is 4).

EDIT: Now that i think of it this is not a specific problem to red/black trees. I'm thus removing the red/black from the title and i replace it with binary tree.

G_H · Accepted Answer · 2011-10-30 16:09:39Z

1

Dammit, I'm so close to getting this to work as expected! Does anyone know why this still falls short of the required result?

package tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Tree {

    private final static int BLACK = 1;
    private final static int RED = 2;
    private Tree left = null;
    private Tree right = null;
    private int color = BLACK;
    private String value = "";

    Tree(final Tree left, final Tree right, final int color, final String value) {
        this.left = left;
        this.right = right;
        this.color = color;
        this.value = value;
    }

    Tree getLeft() {
        return left;
    }

    Tree getRight() {
        return right;
    }

    int getColor() {
        return color;
    }

    String getValue() {
        return value;
    }

    public static void main(String[] args) {

        Tree leaf1 = new Tree(null, null, RED, "20");
        Tree leaf2 = new Tree(null, null, BLACK, "30");
        Tree leaf3 = new Tree(null, null, RED, "2");
        Tree leaf4 = new Tree(null, null, RED, "100");
        Tree leaf5 = new Tree(null, null, BLACK, "5");

        Tree middle1 = new Tree(leaf1, leaf2, RED, "40");
        Tree middle2 = new Tree(middle1, leaf3, BLACK, "200");
        Tree middle3 = new Tree(leaf4, leaf5, RED, "3");

        Tree root = new Tree(middle2, middle3, RED, "50");

        printTree(root);

    }

    static void printTree(final Tree t) {

        final Map<Tree, Integer> widths = new HashMap<Tree, Integer>();
        final Map<Tree, Integer> offsets = new HashMap<Tree, Integer>();

        setWidths(widths, t);

        setOffsets(offsets, widths, t, widths.get(t)/2);

        final List<Tree> root = new ArrayList<Tree>();
        root.add(t);
        printTree(offsets, root);

    }

    static int setWidths(final Map<Tree, Integer> widths, final Tree t) {

        if(widths.containsKey(t))
            return widths.get(t);

        int width = (t.getColor() == BLACK) ? t.getValue().length()
                    : t.getValue().length() + 2;

        final Tree left = t.getLeft();
        final Tree right = t.getRight();

        if(left != null)
            width += setWidths(widths, left);
        if(right != null)
            width += setWidths(widths, right);

        widths.put(t, width);

        return width;

    }

    static void setOffsets(final Map<Tree, Integer> offsets, final Map<Tree, Integer> widths,
            final Tree t, final int offset) {

        offsets.put(t, offset);

        System.out.println("Parent offset for node " + t.getValue() + ", offset " + offset);

        final Tree left = t.getLeft();
        final Tree right = t.getRight();

        if(left != null)
            setOffsets(offsets, widths, left, offset - widths.get(left)/2);
        if(right != null)
            setOffsets(offsets, widths, right, offset + widths.get(right)/2);

    }

    static void printTree(final Map<Tree, Integer> offsets, final List<Tree> trees) {

        if(trees.isEmpty())
            return;

        final List<Tree> children = new ArrayList<Tree>();
        int linePos = 0;

        for(int i = 0; i < trees.size(); ++i) {

            final Tree t = trees.get(i);

            int offset = offsets.get(t);
            final char[] lead = new char[Math.max(offset - linePos, 0)];
            Arrays.fill(lead, ' ');

            System.out.print(new String(lead));
            linePos += Math.max(offset, 0);

            if(t.getColor() == RED) {
                System.out.print(t.getValue());
                linePos += t.getValue().length();
            } else {
                System.out.print("<" + t.getValue() + ">");
                linePos += t.getValue().length() + 2;
            }

            if(t.getLeft() != null)
                children.add(t.getLeft());
            if(t.getRight() != null)
                children.add(t.getRight());

        }

        System.out.println("");

        printTree(offsets, children);

    }

}

answered Oct 30, 2011 at 16:09

G_H

12.1k3 gold badges43 silver badges85 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Aerus Over a year ago

I've edited the code to my project and i'm testing it right now. It definately starts to look the way it should. Will keep this updated if i find a fix so it completely works. Thanks a lot already!

G_H Over a year ago

I'll take another shot at getting this right later. It's actually more difficult than I had thought.

Aerus Over a year ago

I'm still going a bit through the code but it seems as if it goes wrong as soon as the subtree of a right child of a certain node has to be printed. Thus the root is printed correctly, his right child is printed correctly but the subtree of the right child is somehow shifted to the left...

G_H Over a year ago

@Aerus Indeed. Getting the required width of each tree seems like a good first step, but setting the offsets right is rather difficult.

Aerus Over a year ago

Marking this as answer since, despite a minor problem, it gives me a good enough overview of the tree im wanting to print. Thanks for your effort G_H.

Kai Sternad · Accepted Answer · 2011-10-30 13:38:13Z

1

Perhaps you may consider using a different method for drawing more complicated trees. An excellent tool for this is the dot language which is part of the Graphviz software.

Here's an example of how to write a red-black tree in dot from within python: http://code.activestate.com/recipes/576817-red-black-tree/

answered Oct 30, 2011 at 13:38

Kai Sternad

23k8 gold badges50 silver badges43 bronze badges

1 Comment

Aerus Over a year ago

Aah i've looked into other ways of representing them, but they were all to complicated but this actually looks very interesting and easy. I will give it a try and most likely use it for the images in my report.

Collectives™ on Stack Overflow

Printing binary tree to standard output Java

2 Answers 2

5 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related