פעולות עצים

//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))

}

}