Tree Core and Utility Classes

package in.blogspot.arunj2ee.ds.tree;

public class BinaryTreeNode {

private int data;
private BinaryTreeNode left;
private BinaryTreeNode right;

public BinaryTreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public BinaryTreeNode getLeft() {
return left;
}

public void setLeft(BinaryTreeNode left) {
this.left = left;
}

public BinaryTreeNode getRight() {
return right;
}

public void setRight(BinaryTreeNode right) {
this.right = right;
}

}

========================================================================

package in.blogspot.arunj2ee.ds.tree.util;

import in.blogspot.arunj2ee.ds.tree.BinaryTreeNode;

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

public class BTreePrinter {

public static <T extends Comparable<?>> void printBinaryTreeNode(

BinaryTreeNode root) {

int maxLevel = BTreePrinter.maxLevel(root);

printBinaryTreeNodeInternal(Collections.singletonList(root), 1,

maxLevel);

}

private static <T extends Comparable<?>> void printBinaryTreeNodeInternal(

List<BinaryTreeNode> BinaryTreeNodes, int level, int maxLevel) {

if (BinaryTreeNodes.isEmpty()

|| BTreePrinter.isAllElementsNull(BinaryTreeNodes))

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<BinaryTreeNode> newBinaryTreeNodes = new ArrayList<BinaryTreeNode>();

for (BinaryTreeNode BinaryTreeNode : BinaryTreeNodes) {

if (BinaryTreeNode != null) {

System.out.print(BinaryTreeNode.getData());

newBinaryTreeNodes.add(BinaryTreeNode.getLeft());

newBinaryTreeNodes.add(BinaryTreeNode.getRight());

} else {

newBinaryTreeNodes.add(null);

newBinaryTreeNodes.add(null);

System.out.print(" ");

}

BTreePrinter.printWhitespaces(betweenSpaces);

}

System.out.println("");

for (int i = 1; i <= endgeLines; i++) {

for (int j = 0; j < BinaryTreeNodes.size(); j++) {

BTreePrinter.printWhitespaces(firstSpaces - i);

if (BinaryTreeNodes.get(j) == null) {

BTreePrinter.printWhitespaces(endgeLines + endgeLines + i

+ 1);

continue;

}

if (BinaryTreeNodes.get(j).getLeft() != null)

System.out.print("/");

else

BTreePrinter.printWhitespaces(1);

BTreePrinter.printWhitespaces(i + i - 1);

if (BinaryTreeNodes.get(j).getRight() != null)

System.out.print("\\");

else

BTreePrinter.printWhitespaces(1);

BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);

}

System.out.println("");

}

printBinaryTreeNodeInternal(newBinaryTreeNodes, 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(

BinaryTreeNode BinaryTreeNode) {

if (BinaryTreeNode == null)

return 0;

return Math.max(BTreePrinter.maxLevel(BinaryTreeNode.getLeft()),

BTreePrinter.maxLevel(BinaryTreeNode.getRight())) + 1;

}

private static boolean isAllElementsNull(List list) {

for (Object object : list) {

if (object != null)

return false;

}

return true;

}

}

========================================================================package in.blogspot.arunj2ee.ds.tree.util;

import in.blogspot.arunj2ee.ds.tree.BinaryTreeNode;

public class TreeUtil {

// Pre order traversal 1 245 367

/*

*     1       

 / \   

/   \  

2   3   

/ \ / \ 

4 5 6 7 

                

*/

public static BinaryTreeNode makeSampleBinaryTree() {

BinaryTreeNode rootNode = new BinaryTreeNode(1);

BinaryTreeNode LeftNode = new BinaryTreeNode(2);

BinaryTreeNode rightNode = new BinaryTreeNode(3);

rootNode.setLeft(LeftNode);

rootNode.setRight(rightNode);

BinaryTreeNode LeftLeftNode = new BinaryTreeNode(4);

BinaryTreeNode LeftRightNode = new BinaryTreeNode(5);

LeftNode.setLeft(LeftLeftNode);

LeftNode.setRight(LeftRightNode);

BinaryTreeNode rightLeftNode = new BinaryTreeNode(6);

BinaryTreeNode rightRightNode = new BinaryTreeNode(7);

rightNode.setLeft(rightLeftNode);

rightNode.setRight(rightRightNode);

return rootNode;

}

public static void main(String[] args) {

// BTreePrinter.printBinaryTreeNode(makeSampleBinaryTree());

BTreePrinter.printBinaryTreeNode(createRandomBinaryTree());

}

public static BinaryTreeNode createRandomBinaryTree(){

BinaryTreeNode rootNode = new BinaryTreeNode((int)(Math.random()*100));

BinaryTreeNode LeftNode = new BinaryTreeNode((int)(Math.random()*100));

BinaryTreeNode rightNode = new BinaryTreeNode((int)(Math.random()*100));

rootNode.setLeft(LeftNode);

rootNode.setRight(rightNode);

BinaryTreeNode LeftLeftNode = new BinaryTreeNode((int)(Math.random()*100));

BinaryTreeNode LeftRightNode = new BinaryTreeNode((int)(Math.random()*100));

LeftNode.setLeft(LeftLeftNode);

LeftNode.setRight(LeftRightNode);

BinaryTreeNode rightLeftNode = new BinaryTreeNode((int)(Math.random()*100));

BinaryTreeNode rightRightNode = new BinaryTreeNode((int)(Math.random()*100));

rightNode.setLeft(rightLeftNode);

rightNode.setRight(rightRightNode);

return rootNode;

}

}

========================================================================

Share on Google Plus

About Admin

Arun is a JAVA/J2EE developer and passionate about coding and managing technical team.