public class BinTree
{
BinTree left ;
BinTree right;
int value;
public BinTree(int m)
{
left= null;
right= null;
this.value= m;
}
public static void main(String[] args)
{
BinTree root = new BinTree(1);
root.left = new BinTree(2);
root.right = new BinTree(3);
root.left.left= new BinTree(4);
root.left.right = new BinTree(6);
root.right.left = new BinTree(5);
root.right.right = new BinTree(7);
//boolean y= root.find(2);
/*System.out.println(y);
System.out.println(root.numberOfNodes());
System.out.println(root.totalValue());
System.out.println(root.isDescendent(7,3));
System.out.println(root.isSibling(7,5));
System.out.println(root.isCousin(2,7)); */
System.out.println(root.closestCommonAncestor(6,2).value);
}
boolean find(int m)
{
if (this.value==m)
{
//System.out.println(this.value);
return true;
}
else
{
boolean l_result=false,r_result=false;
if (this.left !=null)
{ l_result = this.left.find(m);}
if (this.right !=null)
{r_result = this.right.find(m);}
return (l_result|r_result);
}
}
int numberOfNodes()
{
{
int size_l=0,size_r=0;
if (this.left != null)
{
size_l = this.left.numberOfNodes();
}
if(this.right !=null)
{
size_r= this.right.numberOfNodes();
}
return size_l+size_r+ 1;
}
}
int totalValue()
{
{
int value_l=0,value_r=0;
if (this.left != null)
{
value_l = this.left.totalValue();
}
if(this.right !=null)
{
value_r= this.right.totalValue();
}
return value_l+value_r+ this.value;
}
}
BinTree find2(int m)
{
BinTree x = null;
if (this.value==m)
{
System.out.println(this.value);
x = this ;
return x;
}
else
{
if (this.left !=null)
{ x=this.left.find2(m);}
if (x== null)
{
if (this.right !=null )
{x=this.right.find2(m);}
}
}
return x;
}
boolean isDescendent(int x, int y) //check whether x is decendent of y
{
BinTree m= this.find2(y);
if (m== null)
{
System.out.println("ancestor not found");
}
return m.find(x);
}
boolean isSibling(int m, int n)
{
if( (this.left!=null)& (this.right!=null) )
{ if ((this.left.value == m & this.right.value == n)| (this.left.value ==n & this.right.value ==m))
return true;
else
{
boolean l_result=false,r_result=false;
if (this.left !=null)
{ l_result = this.left.isSibling(m,n);}
if (this.right !=null)
{r_result = this.right.isSibling(m,n);}
return (l_result|r_result);
}
}
return false;
}
boolean isCousin(int m , int n)
{
int l_1= this.getLevel(m);
System.out.println(l_1);
int l_2 =this.getLevel(n);
System.out.println(l_2);
if(l_1==l_2)
{
return true;
}
else
{return false ;}
}
int getLevel(int m)
{
if (this.value==m)
{
return 1 ;
}
else
{
int level=0;
if(this.left!= null)
level= this.left.getLevel(m);
if (level!=1)
{
{if (this.right!=null)
level =this.right.getLevel(m);
}
}
if (level==0)
{
return 0;
}
else
{
return level+1;
}
}
}
BinTree closestCommonAncestor(int m, int n)
{
if( this.left!= null & this.right!=null)
{
boolean b= false;
boolean a = false ;
a= this.left.find(m) | this.value==m;
if (a == true)
{ b = this.right.find(n)| this.value==m;}
else
{
a= this.right.find(m);
if (a == true)
{
b= this.left.find(n)| this.value==n;
}
}
if (a & b)
{
return this;
}
else {
BinTree x= null;
if (this.left!= null)
{
x= this.left.closestCommonAncestor(m,n) ;}
if (x ==null)
{
if (this.right!= null)
{
x = this.right.closestCommonAncestor(m,n) ;}
}
return x;
}
}return null;
}
}
No comments:
Post a Comment