This is the a full code for creating a Tree Data Structure in Java. This class will be able to create modify and display a tree.
This requires a custom tree Node class which i created.
Data Structures in Java by Robert Lafore
package com.test.ds;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class TreeAppLL {
private TreeNodeLL root;
public TreeAppLL(TreeNodeLL root) {
this.root = root;
}
public TreeNodeLL getRoot(){
return this.root;
}
/**
* Find the code. We are assuming we have a inorder tree
*
* @param key
* @return
*/
public TreeNodeLL find(int key) {
TreeNodeLL current = root;
while (current.key != key) {
if (key > current.key) {
current = current.leftChild;
} else {
current = current.rightChild;
}
if (current == null) {
return null;
}
}
return current;
}
public void insert(int key, int data) {
TreeNodeLL node = new TreeNodeLL(key, data);
if (root == null) {
root = node;
}
/*
* So we have to insert after some node.
*/
else {
TreeNodeLL current = root;
TreeNodeLL parent;
while (true) {
parent = current;
if (key < current.key) {
current = current.leftChild;
if (current == null) {
parent.leftChild = node;
return;
}
} else {
current = current.rightChild;
if (current == null) {
parent.rightChild = node;
return;
}
}
}
}
}
public void traversal() throws IOException {
do {
System.out.println("Enter the choice");
System.out.println("1. In Order");
System.out.println("2. Post Order");
System.out.println("3. Pre Order");
System.out.println("Press 'e' to Exit ");
System.out.print("Choice: ");
String str = getInput();
if (str.equalsIgnoreCase("e")) {
break;
}
switch (Integer.parseInt(str)) {
case 1:
System.out.println("In order traversal is: ");
inOrder(root);
System.out.println("");
break;
case 2:
System.out.println("Post order traversal is: ");
postOrder(root);
System.out.println("");
break;
case 3:
System.out.println("Pre order traversal is: ");
preOrder(root);
System.out.println("");
break;
default:
inOrder(root);
System.out.println("");
break;
}
} while (true);
}
private void inOrder(TreeNodeLL current) {
if (current != null) {
inOrder(current.leftChild);
System.out.print(" " + current.key + " ");
inOrder(current.rightChild);
}
}
private void postOrder(TreeNodeLL current) {
if (current != null) {
postOrder(current.leftChild);
postOrder(current.rightChild);
System.out.print(" " + current.key + " ");
}
}
private void preOrder(TreeNodeLL current) {
if (current != null) {
System.out.print(" " + current.key + " ");
preOrder(current.leftChild);
preOrder(current.rightChild);
}
}
public boolean delete(int key) {
TreeNodeLL current = root;
TreeNodeLL parent = root;
boolean isChildLeft = false;
while (current.key != key) {
parent = current;
if (key < current.key) {
isChildLeft = true;
current = current.leftChild;
} else {
isChildLeft = false;
current = current.rightChild;
}
if (current == null) {
return false;
}
}
/**
* Case 1. Where the both the child nodes are null
*/
if (current.leftChild == null && current.rightChild == null) {
if (isChildLeft) {
parent.leftChild = null;
} else {
parent.rightChild = null;
}
}
/**
* Case 2: where node to be deleted has one child
*
*/
if (current.leftChild == null) {
if (current == root) {
root = current.rightChild;
}
if (isChildLeft) {
parent.leftChild = current.rightChild;
} else {
parent.rightChild = current.rightChild;
}
} else if (current.rightChild == null) {
if (current == root) {
root = current.leftChild;
}
if (isChildLeft) {
parent.leftChild = current.leftChild;
} else {
parent.rightChild = current.leftChild;
}
}
/**
* Case 3: When node to be deleted has both the children
*/
else {
TreeNodeLL successor = successor(current);
if (current == root) {
root = successor;
} else if (isChildLeft) {
parent.leftChild = successor;
} else {
parent.rightChild = successor;
}
successor.leftChild = current.leftChild;
}
return true;
}
/**
* return the inorder Successor of sent node
*
* @param delNode
* @return
*/
public TreeNodeLL successor(TreeNodeLL delNode) {
TreeNodeLL current = delNode.rightChild;
TreeNodeLL sussessorParent = delNode;
TreeNodeLL sussessor = delNode;
while (current != null) {
sussessorParent = sussessor;
sussessor = current;
current = current.leftChild;
}
if (sussessor != delNode.rightChild) {
sussessorParent.leftChild = sussessor.rightChild;
sussessor.rightChild = delNode.rightChild;
}
return sussessor;
}
public void displayTree() {
Stack globalStack = new Stack();
globalStack.push(root);
int nBlank = 32;
boolean isRowBlank = false;
System.out
.println("-------------------------------------------------------------");
while (isRowBlank == false) {
Stack localStack = new Stack();
isRowBlank = true;
for (int i = 0; i < nBlank; i++) {
System.out.print(" ");
}
while (globalStack.isEmpty() == false) {
TreeNodeLL temp = globalStack.pop();
if (temp != null) {
System.out.print(temp.key + "," + temp.leftSum+ "," + temp.rightSum);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if (temp.leftChild != null || temp.rightChild != null) {
isRowBlank = false;
}
} else {
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for (int j = 0; j < nBlank * 2 - 2; j++) {
System.out.print(" ");
}
}
System.out.println("");
nBlank = nBlank / 2;
while (localStack.isEmpty() == false) {
globalStack.push(localStack.pop());
}
}
System.out.println("---------------------------------------------");
}
public static void main(String[] args) throws IOException {
String str;
TreeAppLL tree = new TreeAppLL(null);
do {
System.out.print("Enter the Tree Node, Enter 'Y' to exit: ");
str = getInput();
if (str.equalsIgnoreCase("y")) {
break;
}
tree.insert(Integer.parseInt(str), Integer.parseInt(str));
System.out.println("");
} while (true);
// tree.traversal();
tree.displayTree();
}
public static String getInput() throws IOException {
InputStreamReader inputStream = new InputStreamReader(System.in);
BufferedReader reader = new BufferedReader(inputStream);
String str = reader.readLine();
return str;
}
}
This requires a custom tree Node class which i created.
package com.test.ds;
public class TreeNodeLL {
int key;
int data;
int leftSum;
int rightSum;
TreeNodeLL leftChild;
TreeNodeLL rightChild;
public TreeNodeLL(int key, int data) {
this.key = key;
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
}
I have also created a collection of common Tree problems which one should look at solving before moving on with the topic.
package com.test.ds;
public class SumOfRootProb {
public static void main(String[] args) {
TreeNodeLL item = new TreeNodeLL(5, 10);
TreeAppLL tree = new TreeAppLL(item);
tree.insert(3, 20);
tree.insert(7, 10);
tree.insert(6, 10);
tree.insert(2, 10);
tree.insert(4, 10);
tree.insert(9, 10);
tree.displayTree();
SumOfRootProb obj = new SumOfRootProb();
obj.sum(tree.getRoot());
tree.displayTree();
System.out.println(obj.maxDepth(tree.getRoot()));
System.out.println(obj.hasSumValue(tree.getRoot(), 18));
obj.recPathPrint(tree.getRoot());
TreeNodeLL item2 = new TreeNodeLL(5, 10);
TreeAppLL tree2 = new TreeAppLL(item2);
tree2.insert(3, 20);
tree2.insert(7, 10);
tree2.insert(6, 10);
tree2.insert(2, 10);
tree2.insert(4, 10);
int result = obj.sameTree(tree.getRoot(), tree2.getRoot());
if (result == 0) {
System.out.println("Both with same structure");
}
else{
System.out.println("Tum ho jhoote jhoote jhoote");
}
tree2.displayTree();
tree.displayTree();
}
public int sum(TreeNodeLL node){
if (node == null) {
return 0;
}
else{
node.leftSum = sum(node.leftChild);
node.rightSum = sum(node.rightChild);
return node.key + node.leftSum + node.rightSum;
}
}
public int maxDepth(TreeNodeLL root) {
int lDepth = 0, rDepth = 0;
if(root == null){
return 0;
}
lDepth = maxDepth(root.leftChild);
rDepth = maxDepth(root.rightChild);
if(lDepth > rDepth){
return lDepth + 1;
} else{
return rDepth + 1;
}
}
public boolean hasSumValue(TreeNodeLL node, int sum){
if(node == null){
return (sum == 0);
}
else{
int subSum = sum - node.key;
return (hasSumValue(node.leftChild, subSum)||hasSumValue(node.rightChild, subSum));
}
}
public void recPathPrint(TreeNodeLL root){
int[] path = new int[10];
printPath(root, path, 0);
}
public void printPath(TreeNodeLL node, int[] path, int pathLen){
if(node == null){
return;
}
else{
path[pathLen] = node.key;
pathLen++;
if(node.leftChild == null && node.rightChild == null){
System.out.print("Path ");
for(int i = 0; i< pathLen; i++){
System.out.print(path[i] + " ");
}
System.out.println("");
} else{
printPath(node.leftChild, path, pathLen);
printPath(node.rightChild, path, pathLen);
}
}
}
public void mirror(TreeNodeLL node){
if(node == null){
return;
}
else{
TreeNodeLL temp;
mirror(node.leftChild);
mirror(node.rightChild);
temp = node.leftChild;
node.leftChild = node.rightChild;
node.rightChild = temp;
}
}
public void doubleTree(TreeNodeLL node){
if(node == null){
return;
} else{
doubleTree(node.leftChild);
doubleTree(node.rightChild);
TreeNodeLL newItem = new TreeNodeLL(node.key, node.data);
newItem.leftChild = node.leftChild;
node.leftChild = newItem;
}
}
public int sameTree(TreeNodeLL root1, TreeNodeLL root2){
if(root1 == null && root2 == null){
return 0;
} else if(root1 != null && root2 != null){
int lResult = sameTree(root1.leftChild, root2.leftChild);
int rResult = sameTree(root1.rightChild, root2.rightChild);
if(lResult == 0 && rResult == 0){
return 0;
} else{
return -1;
}
} else{
return -1;
}
}
public void longestPath(TreeNodeLL node, int[] path, int length, int maxLength){
if(node == null){
return;
}
else{
path[length] = node.data;
length++;
if(node.leftChild == null && node.rightChild == null){
if(maxLength < length){
maxLength = length;
}
}
else{
longestPath(node.leftChild, path, length, maxLength);
longestPath(node.rightChild, path, length, maxLength);
}
}
}
}
References:
Data Structures in Java by Robert Lafore
