השאלה כאן

מעקב

סעיף א' בשפת Java

public static boolean isDomino(BinNode<Domino> lst)

{

        if(lst == null)

                return true;

        return isDomino(lst.getLeft() , lst.getValue().getLeft()) && isDomino(lst.getRight() , lst.getValue().getRight()) ;

}

public static boolean isDomino(BinNode<Domino> lst , int father)

{

        if(lst == null)

                return true;

        Domino d = lst.getValue();

        if(  d.getLeft() !=  father  && d.getRight()!=father )

                return false;

        return isDomino(lst.getLeft() , lst.getValue().getLeft()) &&  isDomino(lst.getRight() , lst.getValue().getRight()) ;

        

}

סעיף ב' בשפת C#

public static bool IsDomino(BinNode<Domino> lst)

{

        if(lst == null)

                return true;

        return isDomino(lst.GetLeft() , lst.GetValue().getLeft()) && isDomino(lst.GetRight() , lst.GetValue().GetRight()) ;

}

public static bool IsDomino(BinNode<Domino> lst , int father)

{

        if(lst == null)

                return true;

        Domino d = lst.GetValue();

        if(  d.GetLeft() !=  father  && d.GetRight()!=father )

                return false;

        return IsDomino(lst.GetLeft() , lst.GetValue().GetLeft()) &&  IsDomino(lst.GetRight() , lst.GetValue().GetRight()) ;

        

}

סעיף ב'

הפרמטר n מהווה את מספר הצמתים בעץ.

סיבוכיות זמן הריצה היא O(n מכיוון שאנו סורקים את כל הצמתים בעץ

סעיף ג'

public static boolean addDomino(BinNode<Domino> lst,Domino d)

{

        if(lst == null)

                return true;

        return isDomino(lst.getLeft() , lst, d) || isDomino(lst.getRight() , lst,d) ;

}

public static boolean addDomino(BinNode<Domino> lst BinNode<Domino> father,Domino d)

{

        if(lst == null)

        {

        

        if( !father.hasLeft() && d.getLeft() ==  father.getValue().getLeft()  ||  d.getRight()==father.getValue().getLeft()  )

        {

                father.setLeft(lst);

                return true;

        }

        if(  !father.hasRight() && d.getLeft() ==  father.getValue().getRight()  ||  d.getRight()==father.getValue().getRight()  )

        {

                father.setRight(lst);

                return true;

        }

        return false;

}

return addDomino(lst.getLeft() , lst,d) ||  addDomino(lst.getRight() , lst,d) ;        

}

סעיף ד' בדומה לסעיף ב'