Question

a java code

In this lab you will implement an inorder traversal, and a search for a 2-3-4 tree. The inorder traversal will print the contents (integers) of the tree, and the search method will return a boolean, indicating whether a given key was found in the tree.

Examine the provided template. The main method is provided for you, as well as a template of the Node and 2-3-4 classes. The main method will read either "inorder" or an integer from the user, build a tree, and then call either the inorder traversal method or the search method on the tree. Your task is to write the inorder traversal and search methods. In both cases, you should have a driver in the 2-3-4 Tree class, and a recursive helper in the Node class.

For example, if the tree was

        [12   16     23]
       /    /    \      \
     /    /        \      \
[4  7]  [13]   [18  21]  [25  29  31]

the input

inorder

would output

4 7 12 13 16 18 21 23 25 29 31

the input

18

would produce the output

The key of 18 was FOUND

and the input

5

would produce the output

The key of 5 was NOT found

Note 1: Similar to Lab 8, rather than using an insert method (which we will not cover in code for multiway trees), the tree is constructed directly from Nodes. This is not proper programming practice, and this approach should not be used in other assignments.

Note 2: Be careful of how you test the number of items in a Node. An interior node could contain one, two, or three items, and has one more child than number of items. A leaf node could contain one, two, or three items, but does not have any children.

used this code

//==============================================================
// Lab10.java
//
// COMP 2140 SUMMER 2020
//
// PURPOSE: Print contents of a 2-3-4 tree, using an inorder traversal,
// and search for values.
//
// NOTE: We will not cover insertion or deletion code for 2-3-4 trees, although you have
// all of the knowledge to write insertion. This template builds a
// tree directly from Nodes, and the instance members in the Node class are public.
// This is not proper programming practice, but will make for a simpler lab. In a
// 2-3-4 tree, insertions should always be done in the leaves.
//==============================================================
import java.util.*;
import java.io.*;

public class Lab10 {

public static void main( String[] args ) {
       Scanner keyboard;
       String input;

       keyboard = new Scanner( System.in );

       //read "inorder" or a key
input = keyboard.nextLine();

       keyboard.close();

       //build tree
       Node temp1 = new Node(5, 8, 10);
       Node temp2 = new Node(23, 28);
       Node temp3 = new Node(37, 39, 41);
       Node temp4 = new Node(45, 51, 53);
       Node temp5 = new Node(64, 71);
       Node temp6 = new Node(82, 86, 89);
       Node temp7 = new Node(99);
       Node temp8 = new Node(12, 30, 42, temp1, temp2, temp3, temp4);
       Node temp9 = new Node(80, 95, temp5, temp6, temp7);
       Node temp10 = new Node(60, temp8, temp9);
       My234Tree testTree = new My234Tree(temp10);

       if (input.equals("inorder")){ //traverse tree
           testTree.inorder();
       }
       else { //search tree
           int key = Integer.parseInt(input);
           if (testTree.search(key))
               System.out.println( "The key of " + key + " was FOUND" );
           else
               System.out.println( "The key of " + key + " was NOT found" );
       }

} // end main
}

class Node{
   public int dataLeft;
   public int dataMid;
   public int dataRight;
   public Node left;
   public Node midLeft;
   public Node midRight;
   public Node right;

   public Node(int d){
       dataLeft = d;
       dataMid = dataRight = Integer.MIN_VALUE;
       left = midLeft = midRight = right = null;
   }

   public Node(int d, Node l, Node ml){
       dataLeft = d;
       dataMid = dataRight = Integer.MIN_VALUE;
       left = l;
       midLeft = ml;
       midRight = right = null;
   }

   public Node(int d1, int d2){
       dataLeft = d1;
       dataMid = d2;
       dataRight = Integer.MIN_VALUE;
       left = midLeft = midRight = right = null;
   }

   public Node(int d1, int d2, Node l, Node ml, Node mr){
       dataLeft = d1;
       dataMid = d2;
       dataRight = Integer.MIN_VALUE;
       left = l;
       midLeft = ml;
       midRight = mr;
       right = null;
   }

   public Node(int d1, int d2, int d3){
       dataLeft = d1;
       dataMid = d2;
       dataRight = d3;
       left = midLeft = midRight = right = null;
   }

   public Node(int d1, int d2, int d3, Node l, Node ml, Node mr, Node r){
       dataLeft = d1;
       dataMid = d2;
       dataRight = d3;
       left = l;
       midLeft = ml;
       midRight = mr;
       right = r;
   }

   //NOTE: Leaf nodes could have one, two, or three items, even though all pointers are null
   public void inorder(){
   //****Fill in this recursive helper method****

   }

   public boolean search(int key){
   //****Fill in this recursive helper method****

   }
}//end Node class

class My234Tree{
   public Node root;

   public My234Tree(){
       root = null;
   }

   public My234Tree(Node r){
       root = r;
   }

   public void inorder(){
       //****Fill in this driver method. It should call the recursive helper method on the root.****
      
   }

   public boolean search(int key){
   //****Fill in this driver method. It should call the recursive helper method on the root.****
      
   }
}

Answer 1

////////////////////////////////////////////////////////

class Node{
public int dataLeft;
public int dataMid;
public int dataRight;
public Node left;
public Node midLeft;
public Node midRight;
public Node right;

public Node(int d){
dataLeft = d;
dataMid = dataRight = Integer.MIN_VALUE;
left = midLeft = midRight = right = null;
}

public Node(int d, Node l, Node ml){
dataLeft = d;
dataMid = dataRight = Integer.MIN_VALUE;
left = l;
midLeft = ml;
midRight = right = null;
}

public Node(int d1, int d2){
dataLeft = d1;
dataMid = d2;
dataRight = Integer.MIN_VALUE;
left = midLeft = midRight = right = null;
}

public Node(int d1, int d2, Node l, Node ml, Node mr){
dataLeft = d1;
dataMid = d2;
dataRight = Integer.MIN_VALUE;
left = l;
midLeft = ml;
midRight = mr;
right = null;
}

public Node(int d1, int d2, int d3){
dataLeft = d1;
dataMid = d2;
dataRight = d3;
left = midLeft = midRight = right = null;
}

public Node(int d1, int d2, int d3, Node l, Node ml, Node mr, Node r){
dataLeft = d1;
dataMid = d2;
dataRight = d3;
left = l;
midLeft = ml;
midRight = mr;
right = r;
}

//NOTE: Leaf nodes could have one, two, or three items, even though all pointers are null
public void inorder(){
//****Fill in this recursive helper method****
   inorderHelper(this.left);
   if(this.dataLeft!=Integer.MIN_VALUE){
       System.out.print(this.dataLeft+" ");
   }
   inorderHelper(this.midLeft);
   if(this.dataMid!=Integer.MIN_VALUE){
       System.out.print(this.dataMid+" ");
   }
   inorderHelper(this.midRight);
   if(this.dataRight!=Integer.MIN_VALUE){
       System.out.print(this.dataRight+" ");
   }
   inorderHelper(this.right);
}

public void inorderHelper(Node n){
   if(n==null){
       return ;
   }
   else{
       // recursive call 1
       inorderHelper(n.left);
         
       // display left element
       if(n.dataLeft!=Integer.MIN_VALUE){
           System.out.print(n.dataLeft+" ");
       }
         
       // recursive call 2
       inorderHelper(n.midLeft);
         
       // display middle element
       if(n.dataMid!=Integer.MIN_VALUE){
           System.out.print(n.dataMid+" ");
       }
         
       // recursive call 3
       inorderHelper(n.midRight);
         
        // display right element
       if(n.dataRight!=Integer.MIN_VALUE){
           System.out.print(n.dataRight+" ");
       }
         
       // recursive call 4
       inorderHelper(n.right);
   }
}
public boolean search(int key){
   boolean ret=false;
   if(this.dataLeft==key){
       ret=true;
   }
   // if middle data found
   if(this.dataMid==key){
       ret=true;
   }
   // if right data found
   if(this.dataRight==key){
       ret=true;
   }
   return (ret || searchHelper(this.left,key) || searchHelper(this.midLeft,key) || searchHelper(this.midRight,key) ||searchHelper(this.right,key));
}

public boolean searchHelper(Node n,int key){
   // if node is null
   if(n==null){
       return false ;
   }
   else{
       boolean ret=false;
       // if left data found
       if(n.dataLeft==key){
           ret=true;
       }
       // if middle data found
       if(n.dataMid==key){
           ret=true;
       }
       // if right data found
       if(n.dataRight==key){
           ret=true;
       }
       return(ret || searchHelper(n.left,key) || searchHelper(n.midLeft,key) || searchHelper(n.midRight,key) || searchHelper(n.right,key));
   }
}

}//end Node class

//////////////////////////////////////////////////

class My234Tree{
public Node root;

public My234Tree(){
root = null;
}

public My234Tree(Node r){
root = r;
}

public void inorder(){
this.root.inorder();
}

public boolean search(int key){
return this.root.search(key);
}
}

//////////////////////////////////////////////////////////

//==============================================================
// Lab10.java
//
// COMP 2140 SUMMER 2020
//
// PURPOSE: Print contents of a 2-3-4 tree, using an inorder traversal,
// and search for values.
//
// NOTE: We will not cover insertion or deletion code for 2-3-4 trees, although you have
// all of the knowledge to write insertion. This template builds a
// tree directly from Nodes, and the instance members in the Node class are public.
// This is not proper programming practice, but will make for a simpler lab. In a
// 2-3-4 tree, insertions should always be done in the leaves.
//==============================================================
import java.util.*;
import java.io.*;

public class Lab10 {

public static void main( String[] args ) {
Scanner keyboard;
String input;

keyboard = new Scanner( System.in );

//read "inorder" or a key
input = keyboard.nextLine();

keyboard.close();

//build tree
Node temp1 = new Node(5, 8, 10);
Node temp2 = new Node(23, 28);
Node temp3 = new Node(37, 39, 41);
Node temp4 = new Node(45, 51, 53);
Node temp5 = new Node(64, 71);
Node temp6 = new Node(82, 86, 89);
Node temp7 = new Node(99);
Node temp8 = new Node(12, 30, 42, temp1, temp2, temp3, temp4);
Node temp9 = new Node(80, 95, temp5, temp6, temp7);
Node temp10 = new Node(60, temp8, temp9);
My234Tree testTree = new My234Tree(temp10);

if (input.equals("inorder")){ //traverse tree
testTree.inorder();
}
else { //search tree
int key = Integer.parseInt(input);
if (testTree.search(key))
System.out.println( "The key of " + key + " was FOUND" );
else
System.out.println( "The key of " + key + " was NOT found" );
}

} // end main
}

//////////////////////////////////////////////////////////////