Tuesday, June 14, 2016

Tree continue example in core-java

Complete Tree program:

import java.util.Stack;
/**
 * 
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
class Node
{
 public int iData;
 public double dData;
 public Node leftChild;
 public Node rightChild;

 public void displayNode()
 {
System.out.println('{');
System.out.println(iData);
System.out.println(",  ");
System.out.println(dData);
System.out.println("}  ");
 }

 class Tree
 {
private Node root;
public Tree()
{
root=null;
}

public Node find(int key)
{
Node current=root;
while(current.iData!=key)
{
if(key < current.iData)
current=current.leftChild;
else
current=current.rightChild;
if(current==null)
return null ;
}
return current;
}

public void insert(int id,int dd)
{
 Node newNode=new Node();

 newNode.iData=id;
 newNode.dData=dd;

 if(root == null)
  root=newNode;

 else
 {
  Node current=root;
  Node parent;
  while(true)
  {
   parent=current;
   if(id< current.iData)
   {
    current=current.leftChild;
    if(current == null)
    {
     parent.leftChild=newNode;
     return;
    }
   }
   else
   {
    current= current.rightChild;
    if(current ==null)
    {
     parent.rightChild=newNode;
     return;
    }
   }
  }
 }
}

public boolean delete(int key)
{
Node current=root;
Node parent=root;
boolean isLeftChild=true;

while(current.iData !=key)
{
parent=current;
if(key<current.iData)
{
isLeftChild=true;
current=current.leftChild;
}
else
{
isLeftChild=false;
current=current.rightChild;
}

if(current==null)
return false;
}

if(current.leftChild ==null && current.rightChild==null)
{
if(current==root)
root=null;
else if(isLeftChild)
parent.leftChild=null;
else
parent.rightChild=null;
}
else if(current.rightChild==null)
if(current==root)
root=current.leftChild;
else if(isLeftChild)
parent.leftChild=current.leftChild;
else
parent.rightChild=current.leftChild;
else if(current.leftChild==null)
if(current==root)
root=current.leftChild;
else if(isLeftChild)
parent.leftChild=current.leftChild;
else
parent.rightChild=current.leftChild;
else if(current.leftChild ==null)
if(current==root)
root=current.rightChild;
else if(isLeftChild)
parent.leftChild=current.rightChild;
else
parent.rightChild=current.rightChild;
else
{
Node successor=getSuccessor(current);
if(current==root)
root=successor;
else if(isLeftChild)
parent.leftChild=successor;
else
parent.rightChild=successor;

successor.leftChild=current.leftChild;

}
return true;


}

private Node getSuccessor(Node delNode)
{
 Node successorParent=delNode;
 Node successor =delNode;
 Node current=delNode.rightChild;
 while(current!=null)
 {
  successorParent=successor;
  successor=current;
  current=current.leftChild;
 }

 if(successor!=delNode.rightChild)
 {
  successorParent.leftChild=successor.rightChild;
  successor.rightChild=delNode.rightChild;
 }
 return successor;
}

public void traverse(int traverseType)
{
switch (traverseType)
{
   case 1:System.out.println("\n Preorer traversal: ");
       preOder(root);
break;

   case 2:System.out.println("\n InOrder traversal: ");
       inOrder(root);
   break;

   case 3:System.out.println("\n PostOrder traversal: ");
       postOrder(root);
    break;


default:
break;
}
}

private void postOrder(Node localRoot)
{
if(localRoot!=null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.println(localRoot.iData + " ");
}

}

private void inOrder(Node localRoot)
{
if(localRoot!=null)
{
inOrder(localRoot.leftChild);
System.out.println(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}

private void preOder(Node localRoot)
{
if(localRoot!=null)
{
System.out.println(localRoot.iData + " ");
preOder(localRoot.leftChild);
preOder(localRoot.rightChild);
}
}


public void displayTree()
{
Stack globalStack=new Stack();
globalStack.push(root);
int nBlank=32;
boolean isRowEmpty=false;
System.out.println("....................................................");
while(isRowEmpty==true)
{
Stack localStack=new Stack();
isRowEmpty=false;
for(int i=0;i<nBlank;i++)
System.out.println(' ');
while(globalStack.isEmpty()==false)
{
Node temp=(Node)globalStack.pop();
if(temp!=null)
{
System.out.println(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);

if(temp.leftChild!=null || temp.rightChild!=null)
isRowEmpty=false;

}
else
{
System.out.println("----");
localStack.push(null);
localStack.push(null);
}
for(int i=0;i<nBlank*2*2;i++)
System.out.println(' ');
}
System.out.println(" ");
nBlank/=2;
while(localStack.isEmpty()==false)
globalStack.push(localStack.pop());
}
System.out.println(" ");
}

 }

}

public class BinaryTreeApp {

/**
* @param args
*/
public static void main(String[] args) {

         Tree theTree=new Tree();
         theTree.insert(50,1.5);
         theTree.insert(25,1.2);
         theTree.insert(75,1.7);

         theTree.displayTree();
       
         // do somthing like this
}


}

No comments: