Lab 3.2A (Java Lab)

profilehjfnmb12345
LAB3.2A.zip
Home>Computer Science homework help>Lab 3.2A (Java Lab)

LAB 3.2A/Provided Code/BinaryTree.java

LAB 3.2A/Provided Code/BinaryTree.java

import  java . util . Optional ;

public   interface   BinaryTree < K , V >   {
     void  put ( K key , V value );

     Optional < V >  get ( K key );
}

LAB 3.2A/Provided Code/BinaryTreeNode.java

LAB 3.2A/Provided Code/BinaryTreeNode.java

import  java . util . Optional ;

public   class   BinaryTreeNode < K , V >   {
     private   BinaryTreeNode < K , V >  left ;
     private   BinaryTreeNode < K , V >  right ;
     private  K key ;
     private  V value ;

     public   BinaryTreeNode ( K key ,  V value )   {
         this . key  =  key ;
         this . value  =  value ;
     }

     public   Optional < BinaryTreeNode < K , V >>  getLeft ()   {
         return   Optional . ofNullable ( left );
     }

     public   Optional < BinaryTreeNode < K , V >>  getRight ()   {
         return   Optional . ofNullable ( right );
     }

     public   void  setLeft ( BinaryTreeNode < K , V >  left )   {
         this . left  =  left ;
     }

     public   void  setRight ( BinaryTreeNode < K , V >  right )   {
         this . right  =  right ;
     }

     public  K getKey ()   {
         return  key ;
     }

     public   void  setKey ( K key )   {
         this . key  =  key ;
     }

     public  V getValue ()   {
         return  value ;
     }

     public   void  setValue ( V value )   {
         this . value  =  value ;
     }
}

LAB 3.2A/Provided Code/SimpleBinaryTree.java

LAB 3.2A/Provided Code/SimpleBinaryTree.java

import  java . util . LinkedList ;
import  java . util . Optional ;
import  java . util . Queue ;

public   class   SimpleBinaryTree < K ,  V >   implements   BinaryTree < K ,  V >   {
     protected   BinaryTreeNode < K ,  V >  root ;

     public   void  put ( K key ,  V value )   {
         if   ( root  ==   null )
            root  =   new   BinaryTreeNode <> ( key ,  value );
         else
            put ( key ,  value ,  root );
     }

     private   void  put ( K key ,  V value ,   BinaryTreeNode < K ,  V >  node )   {
         if   ((( Comparable )  key ). compareTo ( node . getKey ())   ==   0 )   {
            node . setKey ( key );
            node . setValue ( value );
         }   else   if   ((( Comparable )  key ). compareTo ( node . getKey ())   <   0 )   {
             if   ( node . getLeft (). isPresent ())
                put ( key ,  value ,  node . getLeft (). get ());
             else
                node . setLeft ( new   BinaryTreeNode <> ( key ,  value ));
         }   else   {
             if   ( node . getRight (). isPresent ())
                put ( key ,  value ,  node . getRight (). get ());
             else
                node . setRight ( new   BinaryTreeNode <> ( key ,  value ));
         }
     }

     public   Optional < V >  get ( K key )   {
         return   Optional . ofNullable ( root ). flatMap ( n  ->  get ( key ,  n ));
     }

     private   Optional < V >  get ( K key ,   BinaryTreeNode < K ,  V >  node )   {
         if   ((( Comparable )  key ). compareTo ( node . getKey ())   ==   0 )
             return   Optional . of ( node . getValue ());
         else   if   ((( Comparable )  key ). compareTo ( node . getKey ())   <   0 )
             return  node . getLeft (). flatMap ( n  ->  get ( key ,  n ));
         else
             return  node . getRight (). flatMap ( n  ->  get ( key ,  n ));
     }

     public   Optional < K >  minKey ()   {
         return   Optional . ofNullable ( root ). map ( this :: minKey );
     }

     protected  K minKey ( BinaryTreeNode < K ,  V >  node )   {
         return  node . getLeft (). map ( this :: minKey ). orElse ( node . getKey ());
     }

     public   void  printBfs ()   {
        //Write Your code here
     }

  


     public   void  printDfs ()   {
         Optional . ofNullable ( root ). ifPresent ( this :: printDfs );
     }

     private   void  printDfs ( BinaryTreeNode < K ,  V >  node )   {
         //System.out.println("PREORDER " + node.getKey());
        node . getLeft (). ifPresent ( this :: printDfs );
         System . out . println ( "INORDER "   +  node . getKey ());
        node . getRight (). ifPresent ( this :: printDfs );
         //System.out.println("POSTORDER " + node.getKey());
     }


     public   static   void  main ( String []  args )   {
         SimpleBinaryTree < Integer ,   String >  binaryTree  =   new   SimpleBinaryTree < Integer ,   String > ();
         System . out . println ( binaryTree . minKey ());
        binaryTree . put ( 457998224 ,   "Isabel" );
        binaryTree . put ( 366112467 ,   "John" );
        binaryTree . put ( 671031776 ,   "Ruth" );
        binaryTree . put ( 225198452 ,   "Sarah" );
        binaryTree . put ( 419274013 ,   "Peter" );
        binaryTree . put ( 751965387 ,   "Tom" );

         System . out . println ( binaryTree . get ( 457998224 ));
         System . out . println ( binaryTree . get ( 366112467 ));
         System . out . println ( binaryTree . get ( 671031776 ));
         System . out . println ( binaryTree . get ( 225198452 ));
         System . out . println ( binaryTree . get ( 419274013 ));
         System . out . println ( binaryTree . get ( 751965387 ));

        binaryTree . put ( 751965387 ,   "Sam" );

         System . out . println ( binaryTree . get ( 751965387 ));
         System . out . println ( binaryTree . get ( 999999999 ));
         System . out . println ( binaryTree . minKey ());

        binaryTree . printDfs ();
        binaryTree . printBfs ();
     }
}

LAB 3.2A/Scenario.docx

Scenario

Implement an algorithm that searches the binary tree one level at a time, left to right. The traversal starts from the root node and finishes at the leaf node.

Aim

Apply BFS traversal in Java.

Steps for Completion

1. Implement the psuedocode algorithm from Snippet 3.14 (shown below) in a public method called printBfs()in SimpleBinaryTree. The return value should be void and it should print each node on a newline.

breadthFirstSearch(root)

    if (root != null)

        queue = createQueue()

        enqueue(queue, root)

        while (not isEmpty(queue))

            node = dequeue(queue)

            process(node)

            if(node.left != null) enqueue(queue, node.left)

            if(node.right != null) enqueue(queue, node.right)

Snippet 3.14

Implement the BFS algorithm in the printBfs() method.

2

Checks

printBfs() prints the expected keys

Testing printBfs() with separate SimpleBinaryTree