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
}


}

Binary Tree continues example in java

Finding a Node

Finding a node  with a specified key is the simplest of the major tree operations.

Code example:

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;
 }
}

• Can not find the node
• Found the node

Tree Efficiency:

The time required to find a node depends on how many levels down it is situated.

So it is O(log N) .

Inserting a Node:

To insert a node,we must first find the place to insert it.This is much the same process as trying to find that a node that turns out not to exist.

Sample Code:

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.leftChild)

{

currentcurrent.leftChild;

if(current == null)

{

parent.leftChild=newNode;

return;

}

}

else

{

current= current.rightChild;

if(current ==null)

{

parent.rightChild=newNode;

return;

}

}

}

}

}

Traversing the Tree:

Traversing a tree means visiting each node in a specified order.There are three simple ways to traverse a tree.they are called preorder,inorder and postorder.

Inorder Traversal:

An inorder traversal of a binary search  tree will cause all the nodes to be visited in ascending order,based in their key values.

• Call itself to traverse the nodes left sub-tree.
• visit the node.
• call itself to traverse the nodes right sub-tree.

Code example:

private void inOrder(Node localRoot)

{

if(localRoot !=null)

{

inOrder(localRoot.leftChild);

System.out.println(localRoot.iData + " ");

inOrder(localRoot.rightChild);

}

}

PreOrder Traversal:

• Visit the node
• Call itself to traverse the nodes left sub-tree.
• Call itself to traverse the nodes right sub-tree.

Post Order Traversal:

• Call itself to traverse the nodes left sub-tree;
• Call itself to traverse the nodes right sub-tree.
• Visit the node.

Finding Maximum and Minimum Values:

public Node minimum()

{

Node current,last;

current=root;

while(current!=null)

{

last=current;

current=current.leftChild;

}

 

return last;

}

if you want to find the maximum value in the tree then go right sucha as

  current=current.rightChild;

Deleting a Node:

Deleting a node is bit complicated.you start by finding the node you want to delete ,using the same approach we saw in find() and insert() .When you found the node ,there are three cases to consider.

1. The node to be deleted is a leaf(has no children).
2. The node to be deleted has one child;
3. The node to be deleted has two children.

Java code to Delete a Node with no children:

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=cureent.rightChild;

}

if(current==null)

return false;

}

}

The Node to be Deleted has one Child :

// delete() continued....

// if no right child replace with left sub-tree

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.rightChild;

else if(isLeftChild)

parent.leftChild=current.rightChild;

else

parent.rightChild=current.rightChild;

The Node to be Deleted has two children:

if  the deleted node has two children ,you can not just replace it with one of these children,at least if the child has its own children.

Here,s the trick, To delete a node with two children,replace the node with its in-order successor.

Finding the Successor:

private Node getSuccessor(Node delNode)

{

Node successorParent=delNode;

Node successor =delNode;

Node current=delNode.rightChild;

while(current!=null)

{

successorParent=sucessor;

successor=current;

current=current.leftChild;

}

if(successor!=delNode.rightChild)

{

successorParent.leftChild=successor.rightChild;

successor.rightChild=delNode.rightChild;

}

return successor;

}

Binary Trees example in java

Why use Binary Trees?

Because,it combines the advantage  of two other structures: an ordered array and linked list.you can search a tree quickly,as you can ordered array and you can also insert , delete items quickly as you can with linked list.Lets explore why?.

1. Slow Insertion in an Ordered Array 
2. Slow Searching in a Linked List

It would be nice if there were a data structure with the quick insertion and deletion of a linked list and also the quick searching of an ordered array.

Tree Terminology:

1. Path-Thinking of someone walking from node to node along the edges that connect them.
2. Root-The node at the top of the tree is called Root.
3. Parent-Any node except the root has exactly one edge running upward to another node.
4. Child-Any node may have one or more lines running downward to other nodes.
5. Leaf-A node that has no children is called Leaf.
6. Sub Tree-Any node may be considered to be the root of a subtree,which cinsists of its children and its childrens children.
7. Visiting-A node is visited when program control arrives at the node.
8. Traversing-To visit all the nodes in some specified order.
9. Levels-The level of a particular node refers to how many generations the node is from the root.
10. Keys-One data field in an object is usually designated a key value.This value is used to search for the item.

Binary Trees

If every node in a tree can have at most two children,the tree is called a binary tree.

Representing the tree in java code:

The Node class

First we need a class of node objects.these objects contain the data representing the objects being stored and also references to each of the nodes two children.

class Node

{

  int iData;

  double fData;

  Node leftChild;

  Node rightChild;

 public void displayNode()

 {

    // display node

 }

}

The Tree Class

class Tree

{

  private Node root;

  

  public void find(int key)

  {

  }

  public void insert(int id,double dd)

  {

  }

  public void delete(int id)

  {  

  }

  // various other methods

}