Monday, May 7, 2012

A good looking tree program

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.

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

No comments: