Print a Binary Search Tree with Correct Formatting

786 views Asked by At

I have a binary tree program that sorts smaller/equal numbers to the left of the parent, and larger numbers to the right of the parent, and I want to print out a diagram of it, but I don't know how to print it so it formats well. Also, should the print method be part of the TreeDriver class, or part of the TreeNode class to recursively access every node.

Here are the classes:

TreeDriver:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

/**
 * This class serves as the driver for a generic TreeNode, giving it the type of Integer.
 */
public class TreeDriver
{
    //region Instance Variables
    TreeNode<Integer> root;
    //endregion


    //region Constructors
    public TreeDriver() throws FileNotFoundException
    {
        fill();
        System.out.println("Count: " + root.getCount());
    }
    //endregion


    //region Public Methods
    public void fill() throws FileNotFoundException
    {
        Scanner reader = new Scanner(new File("TreeValueSource"));
        String temp;
        Integer entry;

        makeRoot();

        while (reader.hasNext())
        {
            temp = reader.nextLine();
            if (temp.contains("//"))
            {
                if (reader.hasNext())
                    temp = reader.nextLine();
                else break;
            }
            else if (checkInt(temp))
            {
                entry = new Integer(temp);
                root.add(entry);
            }
            else System.out.println("ERROR IN FILL");
        }
    }

    private void makeRoot()
    {
        Scanner scan = new Scanner(System.in);

        System.out.println("Enter a root value(default 50): ");
        String input = scan.next();

        if (checkInt(input))
            root = new TreeNode<>(new Integer(input));
        else
            root = new TreeNode<>(50);
    }


    public void printCount()
    {
        System.out.println(root.getCount());
    }
    //endregion


    //region Private Methods
    private boolean checkInt(String candidate)
    {
        boolean parsable = true;

        try
        {
            Integer.parseInt(candidate);
        } catch (NumberFormatException e)
        {
            parsable = false;
        }

        return parsable;
    }
    //endregion
}

TreeNode:

public class TreeNode<T extends Comparable<T>>
{
    //region Instance Variables
    //Links
    private TreeNode<T> leftChild;  //Left Link
    private TreeNode<T> rightChild; //Right Link

    //Properties
    private T data;         //Info Stored by the TreeNode
    private int childCount; //Number of Children
    private int depth;      //Level of the Node in the Tree
    //endregion


    //region Constructors
    public TreeNode(T data, int parentDepth)
    {
        leftChild = null;
        rightChild = null;
        childCount = 0;
        depth = parentDepth + 1;
        this.data = data;
    }

    public TreeNode(T data)
    {
        leftChild = null;
        rightChild = null;
        childCount = 0;
        depth = 0;
        this.data = data;
        System.out.println("A Root was Created");
    }
    //endregion


    //region Public Methods

    /**
     * ADD
     * Adds a new TreeNode to the tree. Left if equal or smaller, Right if larger
     *
     * @param data The data held by the TreeNode
     * @see TreeNode
     */
    public void add(T data)
    {
        if (this.data.compareTo(data) <= 0)
        {
            addLeft(data);
        } else if (this.data.compareTo(data) > 0)
        {
            addRight(data);
        } else
        {
            System.out.println("ERROR IN TREENODE.ADD");
        }
    }


    public int getCount()
    {
        return count();
    }


    /**
     * IS LEAF
     * Determines if the current node has no children
     *
     * @return True if no children, False otherwise
     */
    public boolean isLeaf()
    {
        return childCount == 0;
    }
    //endregion


    //region Private Methods

    //Adds the data to the left of this.TreeNode
    private void addLeft(T data)
    {
        if (null == leftChild)
        {
            leftChild = new TreeNode(data, depth);
            childCount += 1;
        } else
            leftChild.add(data);
    }


    //Adds the data to the right of this.TreeNode
    private void addRight(T data)
    {
        if (null == rightChild)
        {
            rightChild = new TreeNode(data, depth);
            childCount += 1;
        } else
            rightChild.add(data);
    }


    /**
     * COUNT
     * Recursively counts the number of TreeNodes
     *
     * @return the number of TreeNodes, 0 if an error
     */
    private int count()
    {
        if (isLeaf())
        {
            return 1;
        } else if (childCount == 2)
        {
            return 1 + leftChild.count() + rightChild.count();
        } else if (null == leftChild)
        {
            return 1 + rightChild.count();
        } else if (null == rightChild)
        {
            return 1 + leftChild.count();
        } else
        {
            System.out.println("ERROR IN COUNT AT DEPTH " + depth);
            return 0;
        }
    }
    //endregion
}
1

There are 1 answers

0
pantelis300 On

You can use this answer as a model

[How to print binary tree diagram?

Modifying the BtreePrinter Class. And no you shouldn't put the print method in the TreeDriver class.

class Node<T extends Comparable<?>> {
    Node<T> left, right;
    T data;

    public Node(T data) {
        this.data = data;
    }
}

class BTreePrinter {

    public static <T extends Comparable<?>> void printNode(Node<T> root) {
        int maxLevel = BTreePrinter.maxLevel(root);

        printNodeInternal(Collections.singletonList(root), 1, maxLevel);
    }

    private static <T extends Comparable<?>> void printNodeInternal(List<Node<T>> nodes, int level, int maxLevel) {
        if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
            return;

        int floor = maxLevel - level;
        int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
        int firstSpaces = (int) Math.pow(2, (floor)) - 1;
        int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

        BTreePrinter.printWhitespaces(firstSpaces);

        List<Node<T>> newNodes = new ArrayList<Node<T>>();
        for (Node<T> node : nodes) {
            if (node != null) {
                System.out.print(node.data);
                newNodes.add(node.left);
                newNodes.add(node.right);
            } else {
                newNodes.add(null);
                newNodes.add(null);
                System.out.print(" ");
            }

            BTreePrinter.printWhitespaces(betweenSpaces);
        }
        System.out.println("");

        for (int i = 1; i <= endgeLines; i++) {
            for (int j = 0; j < nodes.size(); j++) {
                BTreePrinter.printWhitespaces(firstSpaces - i);
                if (nodes.get(j) == null) {
                    BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
                    continue;
                }

                if (nodes.get(j).left != null)
                    System.out.print("/");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(i + i - 1);

                if (nodes.get(j).right != null)
                    System.out.print("\\");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
            }

            System.out.println("");
        }

        printNodeInternal(newNodes, level + 1, maxLevel);
    }

    private static void printWhitespaces(int count) {
        for (int i = 0; i < count; i++)
            System.out.print(" ");
    }

    private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
        if (node == null)
            return 0;

        return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1;
    }

    private static <T> boolean isAllElementsNull(List<T> list) {
        for (Object object : list) {
            if (object != null)
                return false;
        }

        return true;
    }

}