Custom binary tree Printer

java

package com.kartik.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class BTreePrinter<T> {
/**
  *
  * @param <T>
  * @param root
  */
public static <T> void printNode(Node<T> root) {
int maxLevel = BTreePrinter.maxLevel(root);
printNodeInternal(Collections.singletonList(root), 1, maxLevel);
}

/**
  *
  * @param <T>
  * @param nodes
  * @param level
  * @param maxLevel
  */
private static <T> 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);
}

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

/**
  *
  * @param node
  * @return
  */
private static <T> int maxLevel(Node<T> node) {
if (node == null)
   return 0;
return Math.max(BTreePrinter.maxLevel(node.left),
    BTreePrinter.maxLevel(node.right)) + 1;
}

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

public static <T> Node<T> drawTree(T[] input) {
Node<T> node = null;
Map<String, Node<T>> mapNode = new HashMap<String, Node<T>>();
int i = 0, c = 0;
int count = 0;
for (i = 0; i < input.length; i++) {
   if (i > 0) {
    for (c = 1; c <= square(i); c++) {
     String stringKey = "n" + i + c;
     if (count < input.length) {
      node = new Node<T>(input[count]);
      mapNode.put(stringKey, node);
     }
     count++;
    }
   } else {
    String stringKey = "n" + i + c;
    node = new Node<T>(input[count]);
    mapNode.put(stringKey, node);
    count++;
   }
}
Map<String, Node<T>> sortMapNode = new TreeMap<String, Node<T>>(mapNode);
Node<T> root = null;
Node<T> prent = null;
int countVal = 1;
int pointerCount = 0;
for (Map.Entry<String, Node<T>> entry : sortMapNode.entrySet()) {
   String key = entry.getKey();
   char p = key.charAt(1);
   char q = key.charAt(2);
   int k = Integer.parseInt(String.valueOf(p));
   int k1 = Integer.parseInt(String.valueOf(p));
   int k2 = Integer.parseInt(String.valueOf(q));
   if (k > 0) {
    String newKey = null;
    if (k1 % 2 == 0) {
     if ((k1 + k2) % 2 == 0) {
      newKey = "n" + (k1 - 1) + (k2 / 2);
      prent = (Node<T>) mapNode.get(newKey);
      prent.right = entry.getValue();
      countVal++;
      pointerCount++;
     } else {
      if (k2 % 2 == 0) {
       newKey = "n" + (k1 - 1) + (k2 / 2);
       prent = (Node<T>) mapNode.get(newKey);
       prent.right = entry.getValue();
       countVal++;
       pointerCount++;
      } else {
       newKey = "n" + (k1 - 1) + countVal;
       prent = (Node<T>) mapNode.get(newKey);
       prent.left = entry.getValue();
       pointerCount++;
      }
     }
    } else {
     if ((k1 + k2) % 2 == 0) {
      if (k1 == 1) {
       newKey = "n00";
       prent = (Node<T>) mapNode.get(newKey);
       if (k2 == 1) {
        prent.left = entry.getValue();
       }
       pointerCount++;
      } else {
       newKey = "n" + (k1 - 1) + countVal;
       prent = (Node<T>) mapNode.get(newKey);
       prent.left = entry.getValue();
       pointerCount++;
      }
     } else {
      if (k1 == 1) {
       newKey = "n00";
       prent = (Node<T>) mapNode.get(newKey);
       if (k2 == 2) {
        prent.right = entry.getValue();
        countVal++;
       }
       pointerCount++;
      } else {
       if (k2 % 2 == 0) {
        newKey = "n" + (k1 - 1) + (k2 / 2);
        prent = (Node<T>) mapNode.get(newKey);
        prent.right = entry.getValue();
        countVal++;
        pointerCount++;
       } else {
        newKey = "n" + (k1 - 1) + countVal;
        prent = (Node<T>) mapNode.get(newKey);
        prent.left = entry.getValue();
        pointerCount++;
       }
      }
     }
    }
    if (pointerCount == square(k1)) {
     countVal = 1;
     pointerCount = 0;
    }
   } else {
    root = entry.getValue();
   }
}
return root;
}

/**
  *
  * @param a
  * @return
  */
public static int square(int a) {
int n = 1;
for (int i = 0; i < a; i++) {
   n = n * 2;
}
return n;
}

public static void main(String... args) {
Integer[] array = { 45, 23, 11, 89, 77, 98, 4, 28, 65, 43 };
BTreePrinter.printNode(BTreePrinter.drawTree(array));

Character[] arrayChar = { 'K', 'A', 'R', 'T', 'I', 'K', 'M', 'A', 'N',
    'D', 'A', 'L' };
BTreePrinter.printNode(BTreePrinter.drawTree(arrayChar));
}

}

The BTreePrinter class in the provided Java code is a utility to print binary trees in a structured format. The class contains methods for building and visualizing the tree, with a special focus on ensuring that the tree is printed in a clear and visually appealing way.

Class Breakdown

printNode(Node<T> root):

This method is the entry point to print the tree. It calculates the maximum level of the tree and then calls the internal printing method.

printNodeInternal(List<Node<T>> nodes, int level, int maxLevel):

This method handles the recursive printing of the tree. It prints nodes level by level, taking care of spacing to ensure the tree's structure is visually represented.
The method also handles printing the branches between parent and child nodes.

printWhitespaces(int count):

Utility method to print a specified number of whitespace characters. This is used to align the tree's nodes properly.

maxLevel(Node<T> node):

Calculates the depth (maximum level) of the tree, which helps in determining how many levels need to be printed.

isAllElementsNull(List<T> list):

Checks if all elements in a list are null, which helps to stop printing when there are no more nodes left at the current level.

drawTree(T[] input):

This method constructs a binary tree from an array of input elements. It maps each element to a node and assigns left and right children accordingly.
It uses a map to track nodes and their positions in the tree, ensuring the structure is correctly built.

square(int a):

Utility method that returns 2a2^a2a. This is used in tree construction to determine the expected number of nodes at each level.

main(String... args):

The main method demonstrates how to use the BTreePrinter to print trees built from an array of integers and characters.
It builds two trees (one from integers and one from characters) and prints them.

Example Output

Given the arrays {45, 23, 11, 89, 77, 98, 4, 28, 65, 43} and {'K', 'A', 'R', 'T', 'I', 'K', 'M', 'A', 'N', 'D', 'A', 'L'}, the program will print two binary trees structured like this:

Integer Array:

Text

23 11

89 77 98 4

28 65 43

Character Array:

text

A R

T I K M

A N D A L

How It Works

Tree Construction:

The tree is built by assigning each element of the input array to a node and connecting nodes as left and right children in a binary tree structure. This construction process uses positional calculation to ensure nodes are placed correctly.

Tree Printing:

The printing method is recursive. It begins at the root and prints each level of the tree. It also prints slashes (/) and backslashes (\) to represent the connections between parent and child nodes.

Summary

This class is a useful tool for visualizing binary trees in Java. It demonstrates how to construct and print trees from arrays, handling both the tree-building logic and the intricate formatting required to represent trees in a terminal or console.