Question

A 2-3-4 tree can be used as a sorting machine. Write a sort() method that has passed an array of key values from main() and writes them back to the array in sorted order.

Answer 1

1). ANSWER :

GIVENTHAT :

Executable Code

//my234TreeNode.java
//Package Name.
package my234tree;

//Class.
class my234TreeNode
{
   
    //Declare the needed node variables.
    my234TreeNode tLeft, tRight;
    int tData;

    //Empty Constructor.
    public my234TreeNode()
    {
       
        //Initialize left node as NULL.
        tLeft = null;
       
        //Initialize right node as NULL.
        tRight = null;
       
        //Initialize data as NULL.
        tData = 0;
    }
   
    //Constructor with one parameter.
    public my234TreeNode(int d)
    {
       
        //Initialize left node as NULL.
        tLeft = null;
       
        //Initialize right node as NULL.
        tRight = null;
       
        //Assign d to data.
        tData = d;
    }
   
    //Setter method for node left.
    public void setTLeft(my234TreeNode d)
    {
       
        //Set d to left node.
        tLeft = d;
    }
   
    //Setter method for node right.
    public void setTRight(my234TreeNode d)
    {
       
        //Set d to right node.
        tRight = d;
    }
   
    //Getter method for node left.
    public my234TreeNode getTLeft()
    {
       
        //Return the left node value.
        return tLeft;
    }
   
    //Getter method for node right.
    public my234TreeNode getTRight()
    {
       
        //Return the right node value.
        return tRight;
    }
   
    //Setter method for node data.
    public void setTData(int d)
    {
        //Set d to data.
        tData = d;
    }
   
    //Getter method for node data.
    public int getTData()
    {
       
        //Return the data.
        return tData;
    }
}

//my234TreeNode.java
//Package Name.
package my234tree;

//Class.
class my234Tree
{
   
    //Declare the needed tree node variable for root.
    private my234TreeNode root;
   
    //Constructor.
    public my234Tree()
    {
        root = null;
    }
   
    //Method insertDate to insert data.
    public void insertTData(int tData)
    {
       
        //Insert the data to root.
        root = insertTData(root, tData);
    }
   
    //Method insertDate to insert data.
    private my234TreeNode insertTData(my234TreeNode node, int tData)
    {
       
        //Check for root emptiness.
        if (node == null)
           
            //Insert node data.
            node = new my234TreeNode(tData);
       
        //Otherwise.
        else
        {
           
            //Condition check to insert in left node.
            if (tData <= node.getTData())
               
                //Insert in left.
                node.tLeft = insertTData(node.tLeft, tData);
           
            //Otherwise.
            else
               
                //Insert in left.
                node.tRight = insertTData(node.tRight, tData);
        }
       
        //Return the node.
        return node;
    }
   
    //Method to display the tree data in data inserted order.
    public void displayTData()
    {
       
        //Display the root.
        displayTData(root);
    }
   
    //Method to display the tree data in data inserted order.
    private void displayTData(my234TreeNode r)
    {
       
        //Check for non emptiness of root.
        if (r != null)
        {
           
            //Display.
            System.out.print(r.getTData() + " ");
           
            //Recursive call to method displayTData().
            displayTData(r.getTLeft());
           
            //Recursive call to method displayTData().
            displayTData(r.getTRight());
        }
    }
   
    //Method sort to display the data in sorted order.
    public void sort()
    {
       
        //Display the root.
        sort(root);
    }   
   
    //Method sort to display the data in sorted order.
    private void sort(my234TreeNode r)
    {
       
        //Check for non emptiness of root.
        if (r != null)
        {
           
            //Recursive call to sort() method.
            sort(r.getTLeft());
           
            //Display.
            System.out.print(r.getTData() + " ");
           
            //Recursive call to sort() method.
            sort(r.getTRight());
        }
    }   
}

//my234TreeDriver.java
//Package Name.
package my234tree;

//Include the needed variable.
import java.util.Random;

//Class.
public class my234TreeDriver
{
   
    //Declare the input size.
    public static int N = 10;
   
    //Main.
    public static void main(String args[])
    {
       
        //Create a new instance for Random.
        Random random = new Random();
       
        //Create a new instance for my234Tree.
        my234Tree my234t = new my234Tree();
       
        //Display.
        System.out.println("\nSorting randomly generated numbers using 2-3-4 Tree");
       
        //For loop to get randomly generated numbers.
        for (int i = 0; i < N; i++)
           
            //Function call to insertTData().
            my234t.insertTData(Math.abs(random.nextInt(100)));
           
            //Display.
            System.out.println("\nThe data of the 2-3-4 Tree: ");
           
            //Function call to displayTData().
            my234t.displayTData();
           
            //Display.
            System.out.println("\n\nThe sorted data of 2-3-4 Tree: ");
           
            //Function call to sort().
            my234t.sort();
           
            //Print new line.
            System.out.println();
    }
}