Menu
You start traversing from the root, then go to the left node, then you again go to the left node until you reach a leaf node. At that point in time, you print the value of the node or mark it as visited and move to the right subtree. Continue the same algorithm until all nodes of the binary tree are visited.
Algorithm: There are basically two functions in this method. One is to print all nodes at a given level (printCurrentLevel), and the other is to print the level order traversal of the tree (printLevelorder). printLevelorder makes use of printCurrentLevel to print nodes at all levels one by one starting from the root.
Print a [large] tree by lines.
output example:
z
├── c
│ ├── a
│ └── b
├── d
├── e
│ └── asdf
└── f
code:
public class TreeNode {
final String name;
final List<TreeNode> children;
public TreeNode(String name, List<TreeNode> children) {
this.name = name;
this.children = children;
}
public String toString() {
StringBuilder buffer = new StringBuilder(50);
print(buffer, "", "");
return buffer.toString();
}
private void print(StringBuilder buffer, String prefix, String childrenPrefix) {
buffer.append(prefix);
buffer.append(name);
buffer.append('\n');
for (Iterator<TreeNode> it = children.iterator(); it.hasNext();) {
TreeNode next = it.next();
if (it.hasNext()) {
next.print(buffer, childrenPrefix + "├── ", childrenPrefix + "│ ");
} else {
next.print(buffer, childrenPrefix + "└── ", childrenPrefix + " ");
}
}
}
}
P.S. This answer doesn't exactly focus on "binary" trees -- instead, it prints all kinds of trees. Solution is inspired by the "tree" command in linux.
I've created simple binary tree printer. You can use and modify it as you want, but it's not optimized anyway. I think that a lot of things can be improved here ;)
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BTreePrinterTest {
private static Node<Integer> test1() {
Node<Integer> root = new Node<Integer>(2);
Node<Integer> n11 = new Node<Integer>(7);
Node<Integer> n12 = new Node<Integer>(5);
Node<Integer> n21 = new Node<Integer>(2);
Node<Integer> n22 = new Node<Integer>(6);
Node<Integer> n23 = new Node<Integer>(3);
Node<Integer> n24 = new Node<Integer>(6);
Node<Integer> n31 = new Node<Integer>(5);
Node<Integer> n32 = new Node<Integer>(8);
Node<Integer> n33 = new Node<Integer>(4);
Node<Integer> n34 = new Node<Integer>(5);
Node<Integer> n35 = new Node<Integer>(8);
Node<Integer> n36 = new Node<Integer>(4);
Node<Integer> n37 = new Node<Integer>(5);
Node<Integer> n38 = new Node<Integer>(8);
root.left = n11;
root.right = n12;
n11.left = n21;
n11.right = n22;
n12.left = n23;
n12.right = n24;
n21.left = n31;
n21.right = n32;
n22.left = n33;
n22.right = n34;
n23.left = n35;
n23.right = n36;
n24.left = n37;
n24.right = n38;
return root;
}
private static Node<Integer> test2() {
Node<Integer> root = new Node<Integer>(2);
Node<Integer> n11 = new Node<Integer>(7);
Node<Integer> n12 = new Node<Integer>(5);
Node<Integer> n21 = new Node<Integer>(2);
Node<Integer> n22 = new Node<Integer>(6);
Node<Integer> n23 = new Node<Integer>(9);
Node<Integer> n31 = new Node<Integer>(5);
Node<Integer> n32 = new Node<Integer>(8);
Node<Integer> n33 = new Node<Integer>(4);
root.left = n11;
root.right = n12;
n11.left = n21;
n11.right = n22;
n12.right = n23;
n22.left = n31;
n22.right = n32;
n23.left = n33;
return root;
}
public static void main(String[] args) {
BTreePrinter.printNode(test1());
BTreePrinter.printNode(test2());
}
}
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;
}
}
Output 1 :
2
/ \
/ \
/ \
/ \
7 5
/ \ / \
/ \ / \
2 6 3 6
/ \ / \ / \ / \
5 8 4 5 8 4 5 8
Output 2 :
2
/ \
/ \
/ \
/ \
7 5
/ \ \
/ \ \
2 6 9
/ \ /
5 8 4
I've made an improved algorithm for this, which handles nicely nodes with different size. It prints top-down using lines.
package alg;
import java.util.ArrayList;
import java.util.List;
/**
* Binary tree printer
*
* @author MightyPork
*/
public class TreePrinter
{
/** Node that can be printed */
public interface PrintableNode
{
/** Get left child */
PrintableNode getLeft();
/** Get right child */
PrintableNode getRight();
/** Get text to be printed */
String getText();
}
/**
* Print a tree
*
* @param root
* tree root node
*/
public static void print(PrintableNode root)
{
List<List<String>> lines = new ArrayList<List<String>>();
List<PrintableNode> level = new ArrayList<PrintableNode>();
List<PrintableNode> next = new ArrayList<PrintableNode>();
level.add(root);
int nn = 1;
int widest = 0;
while (nn != 0) {
List<String> line = new ArrayList<String>();
nn = 0;
for (PrintableNode n : level) {
if (n == null) {
line.add(null);
next.add(null);
next.add(null);
} else {
String aa = n.getText();
line.add(aa);
if (aa.length() > widest) widest = aa.length();
next.add(n.getLeft());
next.add(n.getRight());
if (n.getLeft() != null) nn++;
if (n.getRight() != null) nn++;
}
}
if (widest % 2 == 1) widest++;
lines.add(line);
List<PrintableNode> tmp = level;
level = next;
next = tmp;
next.clear();
}
int perpiece = lines.get(lines.size() - 1).size() * (widest + 4);
for (int i = 0; i < lines.size(); i++) {
List<String> line = lines.get(i);
int hpw = (int) Math.floor(perpiece / 2f) - 1;
if (i > 0) {
for (int j = 0; j < line.size(); j++) {
// split node
char c = ' ';
if (j % 2 == 1) {
if (line.get(j - 1) != null) {
c = (line.get(j) != null) ? '┴' : '┘';
} else {
if (j < line.size() && line.get(j) != null) c = '└';
}
}
System.out.print(c);
// lines and spaces
if (line.get(j) == null) {
for (int k = 0; k < perpiece - 1; k++) {
System.out.print(" ");
}
} else {
for (int k = 0; k < hpw; k++) {
System.out.print(j % 2 == 0 ? " " : "─");
}
System.out.print(j % 2 == 0 ? "┌" : "┐");
for (int k = 0; k < hpw; k++) {
System.out.print(j % 2 == 0 ? "─" : " ");
}
}
}
System.out.println();
}
// print line of numbers
for (int j = 0; j < line.size(); j++) {
String f = line.get(j);
if (f == null) f = "";
int gap1 = (int) Math.ceil(perpiece / 2f - f.length() / 2f);
int gap2 = (int) Math.floor(perpiece / 2f - f.length() / 2f);
// a number
for (int k = 0; k < gap1; k++) {
System.out.print(" ");
}
System.out.print(f);
for (int k = 0; k < gap2; k++) {
System.out.print(" ");
}
}
System.out.println();
perpiece /= 2;
}
}
}
To use this for your Tree, let your Node class implement PrintableNode.
Example output:
2952:0
┌───────────────────────┴───────────────────────┐
1249:-1 5866:0
┌───────────┴───────────┐ ┌───────────┴───────────┐
491:-1 1572:0 4786:1 6190:0
┌─────┘ └─────┐ ┌─────┴─────┐
339:0 5717:0 6061:0 6271:0
public static class Node<T extends Comparable<T>> {
T value;
Node<T> left, right;
public void insertToTree(T v) {
if (value == null) {
value = v;
return;
}
if (v.compareTo(value) < 0) {
if (left == null) {
left = new Node<T>();
}
left.insertToTree(v);
} else {
if (right == null) {
right = new Node<T>();
}
right.insertToTree(v);
}
}
public void printTree(OutputStreamWriter out) throws IOException {
if (right != null) {
right.printTree(out, true, "");
}
printNodeValue(out);
if (left != null) {
left.printTree(out, false, "");
}
}
private void printNodeValue(OutputStreamWriter out) throws IOException {
if (value == null) {
out.write("<null>");
} else {
out.write(value.toString());
}
out.write('\n');
}
// use string and not stringbuffer on purpose as we need to change the indent at each recursion
private void printTree(OutputStreamWriter out, boolean isRight, String indent) throws IOException {
if (right != null) {
right.printTree(out, true, indent + (isRight ? " " : " | "));
}
out.write(indent);
if (isRight) {
out.write(" /");
} else {
out.write(" \\");
}
out.write("----- ");
printNodeValue(out);
if (left != null) {
left.printTree(out, false, indent + (isRight ? " | " : " "));
}
}
}
will print:
/----- 20
| \----- 15
/----- 14
| \----- 13
/----- 12
| | /----- 11
| \----- 10
| \----- 9
8
| /----- 7
| /----- 6
| | \----- 5
\----- 4
| /----- 3
\----- 2
\----- 1
for the input
8 4 12 2 6 10 14 1 3 5 7 9 11 13 20 15
this is a variant from @anurag's answer - it was bugging me to see the extra |s
Adapted from Vasya Novikov's answer to make it more binary, and use a StringBuilder for efficiency (concatenating String objects together in Java is generally inefficient).
public StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) {
if(right!=null) {
right.toString(new StringBuilder().append(prefix).append(isTail ? "│ " : " "), false, sb);
}
sb.append(prefix).append(isTail ? "└── " : "┌── ").append(value.toString()).append("\n");
if(left!=null) {
left.toString(new StringBuilder().append(prefix).append(isTail ? " " : "│ "), true, sb);
}
return sb;
}
@Override
public String toString() {
return this.toString(new StringBuilder(), true, new StringBuilder()).toString();
}
Output:
│ ┌── 7
│ ┌── 6
│ │ └── 5
└── 4
│ ┌── 3
└── 2
└── 1
└── 0
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With