7
\$\begingroup\$

When you're working with trees one of the most useful methods to implement is a clear way to print them, the following is my solution to print a tree in Java:

class BlackRedBST{
    public static final NodeRB NILL = null;
    public static final boolean RED = true;
    public static final boolean BLACK = false;

    NodeRB root;

    public BlackRedBST () {
        root = NILL;
    }

    public void printTree(NodeRB tree, String indent, boolean print_leaf) {
        if(tree == NILL) {
            System.out.print((print_leaf?indent+"   |-+*\n":""));
        } else { 
            indent += "   ";
            if(tree.p == NILL || tree.p == null) {
                printTree(tree.right, indent + " ", print_leaf);
                System.out.print(indent + "+" + tree.value + "\n");
                printTree(tree.left, indent + " ", print_leaf);
            }else if(tree.p.right==tree) {
                printTree(tree.right, indent + " ", print_leaf);
                System.out.print(indent + "|+" + tree.value + "\n");
                printTree(tree.left, indent + "|", print_leaf);
            }
            else {  
                printTree(tree.right, indent + "|", print_leaf);
                System.out.print(indent + "|+" + tree.value + "\n");
                printTree(tree.left, indent + " ", print_leaf);

            }
        }

    }
}

To be clear in the following the NodeRB class:

class NodeRB{

    int value;
    NodeRB p;
    NodeRB left;
    NodeRB right;
    boolean color;
    int level;

    public NodeRB(int v) {
        value = v;
        color = BlackRedBST.RED;
        left = BlackRedBST.NILL;
        right = BlackRedBST.NILL;
        level = 1;
    }
}

To complete the code, here is a class with main to test my code:

public class PreattyPrintTree {

    public static void main(String[] args) {

        BlackRedBST bst = new BlackRedBST();

        // this is a sample, but a method to add the nodes should be write
        bst.root = new NodeRB(1);

        bst.root.left = new NodeRB(2);
        bst.root.left.level = 2;
        bst.root.left.p=bst.root;
        bst.root.right = new NodeRB(3);
        bst.root.right.p = bst.root;
        bst.root.right.level = 2;

        bst.printTree(bst.root, "\t", true);
    }

}

An output sample, with three nodes and print of leaf enabled:

           |-+*
       |+3
       |   |-+*
   +1
       |   |-+*
       |+2
           |-+*

How can the printTree method be improved?

\$\endgroup\$
  • 7
    \$\begingroup\$ Welcome to Code Review! Does this compile? What's NILL? Please always make sure that any code is working as far as you know before posting it here, otherwise it's considered off-topic. Also it wouldn't hurt to include a bit more context, perhaps the class definition for NoteRB, or even a full example so that reviewers can run it too. \$\endgroup\$ – ferada Sep 4 '18 at 23:07
  • 2
    \$\begingroup\$ I've updated the code with complete class. Thanks. \$\endgroup\$ – DAme Sep 20 '18 at 9:34
  • \$\begingroup\$ @DAme is this currently working? If so could you provide an example? I tried but to no success \$\endgroup\$ – dustytrash Apr 8 at 13:25
  • \$\begingroup\$ @DAme p is never filled in. Could you provide an example of a tree to output? \$\endgroup\$ – dfhwze Jun 4 at 6:08
  • 1
    \$\begingroup\$ @dfhwze the method that add a node to the tree is not provided, you should write it and fill p with parent node. I will provide a sample output asap. \$\endgroup\$ – DAme Jun 5 at 8:41
3
\$\begingroup\$

A view more suggestions with explanation to the current source code (first BlackRedBST).

I deleted public static final NodeRB NILL = null; because null can be used instead of NILL for less code.

I also deleted public static final boolean RED = true; and public static final boolean BLACK = false; because color is never used (in the given code).

There is no access modifier for NodeRB root;. Class members should be "as private as possible" to prevent direct modifications from outside (threads and so on) and created appropriate getter and setter methods.

There is a nested if-else tree. I always try to do as less if-else branches as possible with respect to a better readable sourcecode. I stop each if-branch with a return; to ensure correct code reaction.

The tree.p == null branch of if(tree.p == NILL || tree.p == null) was never covered so it is removed as well for less code and a smaller footprint. [1]

The print_leaf branch was never fully covered in the if(tree.p == NILL || tree.p == null) branch thus I removed print_leaf as well.

Then I refactored similar code to the private void printLeaf(final NodeRB tree, final String indent, final String indentSuffix1, final String indentSuffix2, final String indentSuffix3) method and applied it where necessary.

The constructor public BlackRedBST() does nothing special. Initializing root = null; doesn't matter. The constructor is removed.

Since colors aren't used its renamed to BinarySearchTree.

class BinarySearchTree {

    private Node root;

    public void printTree(final Node tree, String indent) {
        if (tree == null) {
            System.out.print(indent + " |-+*\n");
            return;
        }
        indent += " ";
        if (tree.getParentNode() == null) {
            printLeaf(tree, indent, " ", "+", " ");
            return;
        }
        if (tree.getParentNode().getRightNode() == tree) {
            printLeaf(tree, indent, " ", "|+", "|");
            return;
        }
        printLeaf(tree, indent, "|", "|+", " ");
    }

    private void printLeaf(final Node tree, final String indent, final String indentSuffix1, final String indentSuffix2, final String indentSuffix3) {
        printTree(tree.getRightNode(), indent + indentSuffix1);
        System.out.print(indent + indentSuffix2 + tree.getValue() + "\n");
        printTree(tree.getLeftNode(), indent + indentSuffix3);
    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(final Node root) {
        this.root = root;
    }

}

The NodeRB class looks like a model class so i made each attribute private and used getter and setter methods for accessing the data.

Level isn't used therefore its removed.

Since colors aren't used its renamed to Node.

public class Node {

    private int value;
    private Node parentNode;
    private Node leftNode;
    private Node rightNode;

    public Node(final int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public Node getParentNode() {
        return parentNode;
    }

    public void setParentNode(final Node parent) {
        parentNode = parent;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(final Node left) {
        leftNode = left;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public void setRightNode(final Node right) {
        rightNode = right;
    }

}

The PrettyPrintTree class uses the constructors and the getter and setter methods of Node as intended.

public class PrettyPrintTree {

    public static void main(final String[] args) {

        final BinarySearchTree bst = new BinarySearchTree();

        // this is a sample, but a method to add the nodes should be writen
        bst.setRoot(new Node(1));

        final Node root = bst.getRoot();
        root.setLeftNode(new Node(2));

        final Node leftNode = root.getLeftNode();
        leftNode.setParentNode(root);
        root.setRightNode(new Node(3));

        final Node rightNode = root.getRightNode();
        rightNode.setParentNode(root);

        bst.printTree(root, "\t");
    }

}

[1] Codecoverage was used in the Eclipse IDE with the EclEmma plugin.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.