Custom binary tree Printer ~ HTML Title Kartik Mandal

Description:

This is one algorithm where dynamic create a binary tree printer no need to code changes. I am also thinking how to create a mWay tree printer But that is not generating

Code 1:

/**

* @author kartik

* Blog java2blogs.blogspot.com

* This is one algorithm where dynamic create a binary tree printer no need to code changes

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;

/**
* The {@code BTreePrinter} class provides a basic capability for creating
* drawings with your programs. It uses a simple graphics model that allows you
* to create drawings consisting of points, lines, squares, circles, and other
* geometric shapes in a window on your computer and to save the drawings to a
* file. Standard drawing also includes facilities for text, color, pictures,
* and animation, along with user interaction via the keyboard and mouse.
* 
* Getting started. To use standard drawing, you must have
* <tt>BTreePrinter.class</tt> in your Java classpath. If you used our autoinstaller,
* you should be all set. Otherwise, download <a href =
* "http://www.kartikchandramandal.blogspot.in/2015/10/how-to-draw-atree-from-array-of-integer.html"
* >BTreePrinter.java</a> and put a copy in your working directory.
* 
* Now, type the following short program into your editor:
*
* <pre>
* public class TestBTreePrinter {
* 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));
* }
* }
* </pre>
*
* If you compile and execute the program, you should see a window appear with a
* thick magenta line and a blue point. This program illustrates the two main
* types of methods in standard drawing—methods that draw geometric shapes
* and methods that control drawing parameters. The methods
* {@code BTreePrinter.line()} and {@code BTreePrinter.point()} draw lines and
* points; the methods {@code BTreePrinter.setPenRadius()} and
* {@code BTreePrinter.setPenColor()} control the line thickness and color.
* 
* Points and lines. You can draw points and line segments with the
* following methods:
* <ul>
* <li> {@link #point(double x, double y)}
* <li> {@link #line(double x1, double y1, double x2, double y2)}
* </ul>
* 
* The x- and y-coordinates must be in the drawing area
* (between 0 and 1 and by default) or the points and lines will not be visible.
* 
* Squares, circles, rectangles, and ellipses. You can draw squares,
* circles, rectangles, and ellipses using the following methods:
* <ul>
* <li> {@link #circle(double x, double y, double radius)}
* <li>
* {@link #ellipse(double x, double y, double semiMajorAxis, double semiMinorAxis)}
* <li> {@link #square(double x, double y, double radius)}
* <li> {@link #rectangle(double x, double y, double halfWidth, double halfHeight)}
* </ul>
* 
* All of these methods take as arguments the location and size of the shape.
* The location is always specified by the x- and y
* -coordinates of its center. The size of a circle is specified by its
* radius and the size of an ellipse is specified by the lengths of its
* semi-major and semi-minor axes. The size of a square or rectangle is
* specified by its half-width or half-height. The convention for drawing
* squares and rectangles is parallel to those for drawing circles and ellipses,
* but may be unexpected to the uninitiated.
* 
* The methods above trace outlines of the given shapes. The following methods
* draw filled versions:
* <ul>
* <li> {@link #filledCircle(double x, double y, double radius)}
* <li>
* {@link #filledEllipse(double x, double y, double semiMajorAxis, double semiMinorAxis)}
* <li> {@link #filledSquare(double x, double y, double radius)}
* <li>
* {@link #filledRectangle(double x, double y, double halfWidth, double halfHeight)}
* </ul>
* 
* Circular arcs. You can draw circular arcs with the following method:
* <ul>
* <li> {@link #arc(double x, double y, double radius, double angle1, double angle2)}
* </ul>
* 
* The arc is from the circle centered at (x, y) of the
* specified radius. The arc extends from angle1 to angle2. By convention, the
* angles are polar (counterclockwise angle from the x-axis)
* and represented in degrees. For example,
* {@code BTreePrinter.arc(0.0, 0.0, 1.0, 0, 90)} draws the arc of the unit circle
* from 3 o'clock (0 degrees) to 12 o'clock (90 degrees).
* 
* Polygons. You can draw polygons with the following methods:
* <ul>
* <li> {@link #polygon(double[] x, double[] y)}
* <li> {@link #filledPolygon(double[] x, double[] y)}
* </ul>
* 
* The points in the polygon are ({@code x[i]}, {@code y[i]}). For example, the
* following code fragment draws a filled diamond with vertices (0.1, 0.2),
* (0.2, 0.3), (0.3, 0.2), and (0.2, 0.1):
*
* <pre>
* double[] x = { 0.1, 0.2, 0.3, 0.2 };
* double[] y = { 0.2, 0.3, 0.2, 0.1 };
* BTreePrinter.filledPolygon(x, y);
* </pre>
* 
* Pen size. The pen is circular, so that when you set the pen radius to
* r and draw a point, you get a circle of radius r. Also,
* lines are of thickness 2r and have rounded ends. The default pen
* radius is 0.005 and is not affected by coordinate scaling. This default pen
* radius is about 1/200 the width of the default canvas, so that if you draw
* 100 points equally spaced along a horizontal or vertical line, you will be
* able to see individual circles, but if you draw 200 such points, the result
* will look like a line.
* <ul>
* <li> {@link #setPenRadius(double radius)}
* </ul>
* 
* For example, {@code BTreePrinter.setPenRadius(0.025)} makes the thickness of the
* lines and the size of the points to be five times the 0.005 default. To draw
* points with the minimum possible radius (one pixel on typical displays), set
* the pen radius to 0.0.
* 
* Pen color. All geometric shapes (such as points, lines, and circles)
* are drawn using the current pen color. By default, it is black. You can
* change the pen color with the following methods:
* <ul>
* <li> {@link #setPenColor(int red, int green, int blue)}
* <li> {@link #setPenColor(Color color)}
* </ul>
* 
* The first method allows you to specify colors using the RGB color system.
* This <a href = "http://johndyer.name/lab/colorpicker/">color picker</a> is a
* convenient way to find a desired color. The second method allows you to
* specify colors using the {@link Color} data type that is discussed in Chapter
* 3. Until then, you can use this method with one of these predefined colors in
* standard drawing: {@link #BLACK}, {@link #BLUE}, {@link #CYAN},
* {@link #DARK_GRAY}, {@link #GRAY}, {@link #GREEN}, {@link #LIGHT_GRAY},
* {@link #MAGENTA}, {@link #ORANGE}, {@link #PINK}, {@link #RED},
* {@link #WHITE}, and {@link #YELLOW}. For example,
* {@code BTreePrinter.setPenColor(BTreePrinter.MAGENTA)} sets the pen color to magenta.
* 
* Canvas size. By default, all drawing takes places in a 512-by-512
* canvas. The canvas does not include the window title or window border. You
* can change the size of the canvas with the following method:
* <ul>
* <li> {@link #setCanvasSize(int width, int height)}
* </ul>
* 
* This sets the canvas size to be width-by-height pixels. It
* also erases the current drawing and resets the coordinate system, pen radius,
* pen color, and font back to their default values. Ordinarly, this method is
* called once, at the very beginning of a program. For example,
* {@code BTreePrinter.setCanvasSize(800, 800)} sets the canvas size to be 800-by-800
* pixels.
* 
* Canvas scale and coordinate system. By default, all drawing takes
* places in the unit square, with (0, 0) at lower left and (1, 1) at upper
* right. You can change the default coordinate system with the following
* methods:
* <ul>
* <li> {@link #setXscale(double xmin, double xmax)}
* <li> {@link #setYscale(double ymin, double ymax)}
* <li> {@link #setScale(double min, double max)}
* </ul>
* 
* The arguments are the coordinates of the minimum and maximum x- or
* y-coordinates that will appear in the canvas. For example, if you
* wish to use the default coordinate system but leave a small margin, you can
* call {@code BTreePrinter.setScale(-.05, 1.05)}.
* 
* These methods change the coordinate system for subsequent drawing commands;
* they do not affect previous drawings. These methods do not change the canvas
* size; so, if the x- and y-scales are different, squares
* will become rectangles and circles will become ellipsoidal.
* 
* Text. You can use the following methods to annotate your drawings with
* text:
* <ul>
* <li> {@link #text(double x, double y, String text)}
* <li> {@link #text(double x, double y, String text, double degrees)}
* <li> {@link #textLeft(double x, double y, String text)}
* <li> {@link #textRight(double x, double y, String text)}
* </ul>
* 
* The first two methods write the specified text in the current font, centered
* at (x, y). The second method allows you to rotate the text.
* The last two methods either left- or right-align the text at (x,
* y).
* 
* The default font is a Sans Serif font with point size 16. You can use the
* following method to change the font:
* <ul>
* <li> {@link #setFont(Font font)}
* </ul>
* 
* You use the {@link Font} data type to specify the font. This allows you to
* choose the face, size, and style of the font. For example, the following code
* fragment sets the font to Arial Bold, 60 point.
*
* <pre>
* Font font = new Font("Arial", Font.BOLD, 60);
* BTreePrinter.setFont(font);
* BTreePrinter.text(0.5, 0.5, "Hello, World");
* </pre>
* 
* Images. You can use the following methods to add images to your
* drawings:
* <ul>
* <li> {@link #picture(double x, double y, String filename)}
* <li> {@link #picture(double x, double y, String filename, double degrees)}
* <li> {@link #picture(double x, double y, String filename, double width)}
* <li>
* {@link #picture(double x, double y, String filename, double width, double degrees)}
* </ul>
* 
* These methods draw the specified image, centered at (x, y).
* The supported image formats are JPEG, PNG, and GIF. The image will display at
* its native size, independent of the coordinate system. Optionally, you can
* rotate the image a specified number of degrees counterclockwise or rescale it
* to fit inside a width-by-height pixel bounding box.
* 
* Saving to a file. You save your image to a file using the
* File -> Save menu option. You can also save a file programatically
* using the following method:
* <ul>
* <li> {@link #save(String filename)}
* </ul>
* 
* The supported image formats are JPEG and PNG. The filename must have either
* the extension .jpg or .png. We recommend using PNG for drawing that consist
* solely of geometric shapes and JPEG for drawings that contains pictures.
* 
* Clearing the canvas. To clear the entire drawing canvas, you can use
* the following methods:
* <ul>
* <li> {@link #clear()}
* <li> {@link #clear(Color color)}
* </ul>
* 
* The first method clears the canvas to white; the second method allows you to
* specify a color of your choice. For example,
* {@code BTreePrinter.clear(BTreePrinter.LIGHT_GRAY)} clears the canvas to a shade of
* gray. Most often, these two methods are used in conjunction with animation
* mode.
* 
* Animations. Animation mode is one of the trickier features of standard
* drawing. The following two methods control the way in which objects are
* drawn:
* <ul>
* <li> {@link #show()}
* <li> {@link #show(int t)}
* </ul>
* 
* By default, animation mode is off, which means that as soon as you call a
* drawing method—such as {@code point()} or {@code line()}—the
* results appear on the screen. {@code BTreePrinter.show()} turns off animation
* mode.
* 
* You can call {@link #show(int t)} to turn on animation mode. This defers all
* drawing to the screen until you are aready to display them. Once you are
* ready to display them, you call {@link #show(int t)} again, which transfer
* the offscreen drawing to the screen and waits for the specified number of
* milliseconds. In conjuction with {@link #clear()}, you can create the
* illusion of movement by iterating the following three steps:
* <ul>
* <li>Clear the background canvas.
* <li>Draw geometric objects.
* <li>Show the drawing and wait for a short while.
* </ul>
* 
* Waiting for a short while is essential; otherwise, the drawing will appear
* and disappear so quickly that your animation will flicker.
* 
* Here is a simple example of an animation:
* 
* Keyboard and mouse inputs. Standard drawing has very basic support for
* keyboard and mouse input. It is much less powerful than most user interface
* libraries provide, but also much simpler. You can use the following methods
* to intercept mouse events:
* <ul>
* <li> {@link #mousePressed()}
* <li> {@link #mouseX()}
* <li> {@link #mouseY()}
* </ul>
* 
* The first method tells you whether a mouse button is currently being pressed.
* The last two methods tells you the x- and y-coordinates of
* the mouse's current position, using the same coordinate system as the canvas
* (the unit square, by default). You should use these methods in an animation
* loop that waits a short while before trying to poll the mouse for its current
* state. You can use the following methods to intercept keyboard events:
* <ul>
* <li> {@link #hasNextKeyTyped()}
* <li> {@link #nextKeyTyped()}
* <li> {@link #isKeyPressed(int keycode)}
* </ul>
* 
* If the user types lots of keys, they will be saved in a list until you
* process them. The first method tells you whether the user has typed a key
* (that your program has not yet processed). The second method returns the next
* key that the user typed (that your program has not yet processed) and removes
* it from the list of saved keystrokes. The third method tells you whether a
* key is currently being pressed.
* 
* Accessing control parameters. You can use the following methods to
* access the current pen color, pen radius, and font:
* <ul>
* <li> {@link #getPenColor()}
* <li> {@link #getPenRadius()}
* <li> {@link #getFont()}
* </ul>
* 
* These methods are useful when you want to temporarily change a control
* parameter and reset it back to its original value.
* 
* Corner cases. To avoid clutter, the API doesn't explicitly refer to
* arguments that are null, infinity, or NaN.
* <ul>
* <li>Any method that is passed a {@code null} argument will throw a
* {@link NullPointerException}.
* <li>Except as noted in the APIs, drawing an object outside (or partly
* outside) the canvas is permitted—however, only the part of the object
* that appears inside the canvas will be visible.
* <li>Except as noted in the APIs, all methods accept {@link Double#NaN},
* {@link Double#POSITIVE_INFINITY}, and {@link Double#NEGATIVE_INFINITY} as
* arugments. An object drawn with an x- or y-coordinate that
* is NaN will behave as if it is outside the canvas, and will not be visible.
* </ul>
* 
* Performance tricks. Standard drawing is capable of drawing large
* amounts of data. Here are a few tricks and tips:
* <ul>
* <li>Use animation mode for static drawing with a large number of
* objects. That is, call {@code BTreePrinter.show(0)} before and after the sequence
* of drawing commands. The bottleneck operation is not drawing the geometric
* shapes but rather drawing them to the screen. By using animation mode, you
* draw all of the shapes to an offscreen buffer, then copy them all at once to
* the screen.
* <li>When using animation mode, call {@code show()} only once per
* frame, not after drawing each object.
* <li>If you call {@code picture()} multiple times with the same filename, Java
* will cache the image, so you do not incur the cost of reading from a file
* each time.
* <li>Do not call {@code setFont()} in an animation loop (unless you really
* need to change the font in each iteration). It can cause flicker.
* </ul>
* 
* Known bugs and issues.
* <ul>
* <li>The {@code picture()} methods may not draw the portion of the image that
* is inside the canvas if the center point (x, y) is outside
* the canvas. This bug appears only on some systems.
* <li>Some methods may not draw the portion of the geometric object that is
* inside the canvas if the x- or y-coordinates are infinite.
* This bug appears only on some systems.
* </ul>
* 
* Reference. For additional documentation, see <a
* href="http://www.kartikchandramandal.blogspot.in/2015/10/how-to-draw-atree-from-array-of-integer.html">Section 1.5</a> of
* Introduction to Programming in Java: An Interdisciplinary Approach
* by Kartik Chandra Mandal.
*
* @author Kartik Chandra Mandal
*/
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));
}

}

Example 1 Draw Binary Tree :

/ \

23 11

/ \ / \

89 77 98 4

/ \ /

28 65 43

/ \

A R

/ \ / \

T I K M

/ \ / \ /

A N D A L

Example 2 Custom Tree Printer:

About Kartik Chandra Mandal

I am Kartik Chandra Mandal from Bangalore, India. Working as software engineer in Java technology. Have good knowledge of OWASP and CSRF in security for applications and it's implementation in Java technology.

HTML Title Kartik Mandal

Custom binary tree Printer

About Kartik Chandra Mandal

Related Post

Java 8 support static method or default method or both in the interface