Part 1:Implement the following: 1./**** @param e* @return the node that contains the parameter e and...

Question

Part 1:Implement the following:	1./**** @param e* @return the node that contains the parameter e and its parent node inside the* NodeAndParent, or* null if the e is not in the tree*/private NodeAndParent findNode(E e){NodeAndParent nodeNparent = new NodeAndParent();	//add the codereturn nodeNparent;}	2. Modify the remove so it usesfindNode( E e )		instead of find() method and in the removal of nodes that have 1 child.	3. Modify the case of remove with 2 children using findNode( E e ) .				4. Modify the case of remove method with 2 children as follows:		Currently, w		hen the					node to be deleted is found, the existing loop with the 3 pointers takes 1 left and then keeps on going right until the first pointer hits null. Modify the loop to take 1 right instead, and then to keep on going left until the 1st pointer hits null. The BST property must be preserved after the removal. That is, the parent is greater that its left child and smaller that its right child.	Part 2:	(Add new methods in BST) Add the following new methods in BST./** Displays the nodes in a breadth-first traversal */public void breadthFirstTraversal()/** Returns the height of this binary tree */public int height()	4.**25.3 (Implement inorder traversal without using recursion) Implement the inordermethod in BST using a stack instead of recursion. Write a test program thatprompts the user to enter 10 integers, stores them in a BST, and invokes theinorder method to display the elements.	**25.6 (Find the leaves) Add a method in the BST class to return the number of theleaves as follows:/** Returns the number of leaf nodes */public int getNumberOfLeaves()	**25.7 (Find the nonleaves) Add a method in the BST class to return the number of thenonleaves as follows:/** Returns the number of nonleaf nodes */public int getNumberofNonLeaves()	**25.9 (Tree clone and equals) Implement the clone and equals methods in theBST class. Two BST trees are equal if they contain the same elements. Theclone method returns an identical copy of a BST.

Ketaki · Accepted Answer

//package lab1;
public class Main > 
{
  
   Node root;    
    class Node 
            {
              E e;
              Node lChild;
              Node rChild;
                            
            } 
private boolean find (E e)
    {
        Node p = root;
        
        while ( p != null )
          {
            if ( e.compareTo(p.e) == 0 )
                return true;
            else if ( e.compareTo(p.e) > 0)
                p = p.rChild;
            else
                p = p.lChild;
                        
          }
        
        return false;
    }

private String findNode(E e)
{
	//NodeAndParent nodeNparent = new NodeAndParent();
//return nodeNparent;
Node p = root;
Node parent=null;
String s="";
       while ( p != null )
          {
            if ( e.compareTo(p.e) == 0 )
            {
                s="NODE : "+p.e+" Parent : "+parent.e;
                return s;
            }
                
            else if ( e.compareTo(p.e) > 0)
            {
                parent=p;
                p=p.rChild;
                
            }
            else
            {
                parent=p;
                p = p.lChild;
            }
                        
          }
        
        return null;
}
    public boolean insert( E e )
    {
        Node p = new Node();
        p.e = e;
        
        if ( root == null) //tree is empty
            root = p;
        else//find the proper position
          {
            Node p2 = root;
            Node pTrail = p2;
            
            while ( p2 != null )
              {
                pTrail = p2;
                if ( p2.e.equals(e) )
                    return false;
               
                else if ( e.compareTo( p2.e) > 0 )//go to right subtree
                    p2 = p2.rChild;
                else//go the left subtree
                    p2 = p2.lChild;              
              }
            
            //insert the node
            if ( e.compareTo( pTrail.e ) > 0 )               
                pTrail.rChild = p;
            else
                pTrail.lChild = p;
            
          }
        
         return true;
    }
    /** We visit: left child, the parent, then the right child
     * 
     * @param p 
     */
   private void inOrder( Node p )
   {
       if ( p == null )
           return;
       inOrder( p.lChild );
       System.out.println(p.e);
       inOrder( p.rChild );
   }
    public void inOrder()
    {
        inOrder( root);
    }
	
	// Iterative solution
    public void inOrderIter(Node p ) {
 
        if(p == null)
            return;
 
        Stack> s = new Stack >();
        Node currentNode=p;
 
        while(!s.empty() || currentNode!=null){
 
            if(currentNode!=null)
            {
                s.push(currentNode);
                currentNode=currentNode.lChild;

Part 1: Implement the following: 1. /** * * @param e * @return the node that contains the parameter e and its parent node inside the * NodeAndParent, or * null if the e is not in the tree */ private...

Answer To: Part 1: Implement the following: 1. /** * * @param e * @return the node that contains the parameter...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment