import java.util.Scanner;
import java.util.Stack;
public class Node
{
int info;
Node next,prev;
Node left,right;
}
public class BinaryTree
{
Node Insert(int val)
{
Node t=new Node();
t.info=val;
return(t);
}
void setLeft(Node p,int val)
{
if(p==null || p.left!=null)
System.out.println("\nInvalid Insertion");
else
p.left=Insert(val);
}
void setRight(Node p,int val)
{
if(p==null || p.right!=null)
System.out.println("\nInvalid insertion");
else
p.right=Insert(val);
}
void InRecur(Node Start)
{
if(Start!=null)
{
InRecur(Start.left);
System.out.print(Start.info + " ");
InRecur(Start.right);
}
}
void PreRecur(Node Start)
{
if(Start!=null)
{
System.out.print(Start.info + " ");
PreRecur(Start.left);
PreRecur(Start.right);
}
}
void PostRecur(Node Start)
{
if(Start!=null)
{
PostRecur(Start.left);
PostRecur(Start.right);
System.out.print(Start.info + " ");
}
}
void PrintLeaves(Node Start)
{
if(Start!=null)
{
PrintLeaves(Start.left);
PrintLeaves(Start.right);
if (Start.left==null&&Start.right==null)
System.out.print(Start.info + " ");
}
}
void InOrder(Node Start)
{
Node p;
Stack s=new Stack();
p=Start;
do
{
while(p!=null)
{
s.push(p);
p=p.left;
}
if(s.isEmpty()==false)
{
p=(Node)s.pop();
System.out.print(p.info + " ");
p=p.right;
}
}while(s.isEmpty()==false||p!=null);
}
void PreOrder(Node Start)
{
Node p;
Stack s=new Stack();
s.push(Start);
while (s.isEmpty()==false)
{
p=(Node)s.pop();
System.out.print(p.info + " ");
if(p.right!=null)
s.push(p.right);
if (p.left!=null)
s.push(p.left);
}
}
void Delete(int val,Node Start)
{
Node curr;
Node par;
par=curr=Start;
while(curr!=null&&val!=curr.info)
{
par=curr;
if(val<par.info)
curr=par.left;
else
curr=par.right;
}
if(curr.left==null && curr.right==null)
{
if(par.right==curr)
par.right=null;
if(par.left==curr)
par.left=null;
}
if(curr.left!=null && curr.right==null)
{
if(curr==par.left)
par.left=curr.left;
if(curr==par.right)
par.right=curr.left;
}
if(curr.left==null && curr.right!=null)
{
if(curr==par.left)
par.left=curr.right;
if(curr==par.right)
par.right=curr.right;
}
if(curr.left!=null&&curr.right!=null)
{
Node t=curr.right;
Node pt=curr.right;
while(t.left!=null)
{
pt=t;
t=t.left;
}
if(par.left==curr)
par.left.info=t.info;
else par.right.info=t.info;
if(t.right==null)
pt.left=null;
else
pt.left=t.right;
}
}
void Search(int val,Node Start)
{
if(Start!=null)
{
if(Start.info==val) System.out.println("Element Found");
Search(val,Start.left);
Search(val,Start.right);
}
}
void printPaths(Node Start)
{
int[] path = new int[10];
Paths(Start, path, 0);
}
void Paths(Node Start, int[] path, int pathLen)
{
if (Start==null) return;
path[pathLen] = Start.info;
pathLen++;
if (Start.left==null && Start.right==null)
printArray(path, pathLen);
else
{
Paths(Start.left, path, pathLen);
Paths(Start.right, path, pathLen);
}
}
void printArray(int[] path, int len)
{
int i;
for (i=0; i<len; i++)
System.out.print(path[i] + " ");
System.out.println();
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
Node p,q;
int i=0,val;
Node Start=new Node();
BinaryTree BT=new BinaryTree();
Insertion:
{
while(true)
{
System.out.print("Enter Node Value :");
val=in.nextInt();
if(val==0) break Insertion;
if(i++==0)
{
Start = BT.Insert(val);
continue;
}
p=q=Start;
while(q!=null&&val!=p.info)
{
p=q;
if(val<p.info)
q=p.left;
else
q=p.right;
}
if(val==p.info)
{
System.out.println("Duplicate Number");
continue;
}
else if(val<p.info)
BT.setLeft(p,val);
else
BT.setRight(p,val);
}
}
System.out.println("++++++++++++++++++++++++++++++");
System.out.println("InOrder - Non Reursive");
BT.InOrder(Start);
System.out.println("\nInOrder - Reursive");
BT.InRecur(Start);
System.out.println("\nPreOrder - Non Reursive");
BT.PreOrder(Start);
System.out.println("\nPreOrder - Reursive");
BT.PreRecur(Start);
System.out.println("\nPostOrder - Reursive");
BT.PostRecur(Start);
System.out.println("\nPrint Leaves");
BT.PrintLeaves(Start);
System.out.println(" ");
BT.printPaths(Start);
System.out.print("Enter a Number = ");
val=in.nextInt();
BT.Search(val,Start);
System.out.print("Enter number to Delete = ");
val=in.nextInt();
BT.Delete(val,Start);
System.out.println("*****");
BT.printPaths(Start);
}
}
No comments:
Post a Comment