פעולות עצים
//import unit4.collectionsLib.*;
public class TreeOp2
{
public static void inToSearchTree( BinTreeNode<Integer> t, int num)
{ הפעולה מקבלת עץ חיפוש של מספרים ומספר ומכניסה אותו למקומו הנכון בעץ//
if(num<t.getInfo())
{
if(t.getLeft()==null)
t.setLeft(new BinTreeNode<Integer>(num));
else
inToSearchTree( t.getLeft() , num);
}
else
{
if(t.getRight()==null)
t.setRight(new BinTreeNode<Integer>(num));
else
inToSearchTree( t.getRight() , num);
}
}
public static int height(BinTreeNode<Integer> t)
{ הפעולה מקבלת עץ ומחזירה את גובהו//
if(t==null) return -1;
return 1+Math.max(gova(t.getLeft()), gova(t.getRight()));
}
public static boolean isExist(BinTreeNode<Integer> t, int num)
{ הפעולה מקבלת עץ מספרים ומספר ומחזירה אמת אם המספר נמצא בעץ ושקר, אחרת//
if(t==null)
return false;
if(t.getInfo()==num)
return true;
return isExist( t.getLeft(), num) || isExist( t.getRight(), num) ;
}
public static boolean descendant(BinTreeNode<Integer> t, BinTreeNode<Integer> t1)
הפעולה מקבלת עץ ותת-עץ הנמצא בעץ ומחזירה אמת אם הוא צאצא שלו ושקר,אחרת //
{
if(t==null) return false;
if(t==t1) return true;
return descendant( t.getLeft(), t1) || descendant( t.getRight(), t1);
}
public static int distFromRoot(BinTreeNode<Integer> t,BinTreeNode<Integer> t1 )
{הפעולה מקבלת עץ ותת עץ הנמצא בעץ ומחזירה את המרחק ביניהם //
if(t==t1)return 0;
if(descendant(t.getLeft(),t1)) return 1+distFromRoot(t.getLeft(), t1 );
return 1+distFromRoot(t.getRight(), t1 );
}
public static void levelSearch(BinTreeNode<Integer> t)
{ הפעולה מקבלת עץ ומדפיסה את איבריו לפי רמות//
Queue<BinTreeNode<Integer>> q=new Queue<BinTreeNode<Integer>>();
BinTreeNode<Integer>temp;
q.insert(t);
while(!q.isEmpty())
{
temp=q.remove();
System.out.println(temp.getInfo());
if(temp.getLeft()!=null)
q.insert(temp.getLeft());
if(temp.getRight()!=null)
q.insert(temp.getRight());
}
}
public static boolean fullTree(BinTreeNode<Integer> t)
{ הפעולה מקבלת ע ץ ומחזירה אמת אם הוא עץ מלא ושקר, אחרת //
if(t==null) return true;
if(t.getLeft()!=null && t.getRight()==null)
return false;
if(t.getRight()!=null && t.getLeft()==null)
return false;
return fullTree(t.getLeft()) && fullTree(t.getRight());
}
public static int numOfLeaves(BinTreeNode<Integer> t)
{ הפעולה מק בלת עץ ומחזירה את מספר העלים בעץ//
if(t==null) return 0;
if(t.getLeft()==null && t.getRight()==null)
return 1;
return numOfLeaves(t.getLeft()) + numOfLeaves(t.getRight());
}
public static boolean perfect(BinTreeNode<Integer> t)
{ הפעולה מקבלת עץ ומחזירה אמת אם הוא עץ שלם ושקר , אחרת//
int h=height(t);
int leaves= numOfLeaves(t);
return leaves==Math.pow(2,h);
}
public static boolean balanced(BinTreeNode<Integer> t)
{ הפעולה מקבלת עץ ומחזירה אמת אם הוא עץ מאוזן ושקר, אחרת//
if(t==null) return true;
if(Math.abs(height(t.getLeft())-height(t.getRight()))>1)
return false;
return balanced(t.getLeft()) && balanced(t.getRight());
}
public static void main(String[] args)
{
BinTreeNode<Integer> t5=new BinTreeNode<Integer>(5);
BinTreeNode<Integer> t4=new BinTreeNode<Integer>(4);
BinTreeNode<Integer> t3=new BinTreeNode<Integer> (null,3,t5);
BinTreeNode<Integer> t2=new BinTreeNode<Integer>(t4,2,null);
BinTreeNode<Integer> t1=new BinTreeNode<Integer>(t3,1,t2);
BinTreeNode<Integer> t6=new BinTreeNode<Integer>(6);
BinTreeNode<Integer> t7=new BinTreeNode<Integer>(7);
BinTreeNode<Integer> t8=new BinTreeNode<Integer>(8);
BinTreeNode<Integer> t9=new BinTreeNode<Integer>(9);
t2.setRight(t6);
t3.setLeft(t7);
t5.setLeft(t8);
t8.setRight(t9);
System.out.println(t1);
System.out.println( perfect(t1));
System.out.println( balanced(t1))
}
}