JAVA CODE BELOW ####MAIN#### package com.binarytree; import java.util.Iterator;

Question

JAVA CODE BELOW

####MAIN####

package com.binarytree;

import java.util.Iterator;
import java.util.List;

public class Main {

public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(5);
tree.insert(3);
tree.insert(2);
tree.insert(10);
tree.insert(8);
tree.insert(12);
tree.insert(14);

List list = tree.levelOrderTravesal();
iterator(list);

System.out.println(" Delete : 14");
tree.delete(14);

list = tree.levelOrderTravesal();
iterator(list);

System.out.println(" Delete : 3");
tree.delete(3);

list = tree.levelOrderTravesal();
iterator(list);

System.out.println(" Delete : 10");
tree.delete(10);

list = tree.levelOrderTravesal();
iterator(list);

System.out.println(" Delete : 5");
tree.delete(5);

list = tree.levelOrderTravesal();
iterator(list);
}

public static void iterator(List list) {
if(list == null)
System.out.println("No Elements to Traverse");
else {
Iterator iterate = list.iterator();
System.out.print("Tree has : ");
while(iterate.hasNext()) {
System.out.print(iterate.next()+" ");
}
}
}

}

####binarysearchtree####

package com.binarytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinarySearchTree {

private BinaryHeap root = null;

/*
* insert the new element 'x' into the BinarySearchTree
* create a NEW BinaryHeap with data = 'x', left = NULL and right = NULL
*
* if root is NULL then
* insert the new BinaryHeap into root
* else
* find the location where the NEW BinaryHeap has to be inserted
*
* @Param
* - 'x' - New integer
*/
public void insert(int x) {
BinaryHeap heap = new BinaryHeap(x);
if(root == null) {
root = heap;
} else {
BinaryHeap temp = root;
BinaryHeap temp2 = null;
while(temp != null) {
temp2 = temp;
if(temp.getData() > heap.getData()) {
temp = temp.getLeft();
} else {
temp = temp.getRight();
}
}

if(temp2.getData() > heap.getData())
temp2.setLeft(heap);
else
temp2.setRight(heap);
}
}

/*
* check the 'parent' if it is null then it makes node as root
* otherwise, places 'node' in appropriate position to 'parent'
*/
private void replace(BinaryHeap parent, BinaryHeap node, int x) {
if(parent == null)
root = node;
else if(x < parent.getData())
parent.setLeft(node);
else
parent.setRight(node);
}

/*
* If there is any node with integer 'x' then it deletes that node from the tree.
* otherwise print 'So such Element in the tree'
* @param
* - integer that has to be removed from the tree.
*/
public void delete(int x) {
}

/*
* Finds the minimum node in the subtree.
*
* @return
* - Returns minimum BinaryHeap node
*
* @param
* - 'node' represents the subtree where it has to find the minimum node.
*/
private BinaryHeap findMinimumNode(BinaryHeap node) {
BinaryHeap temp = node;
  
while(temp.getLeft() != null) {
temp = node.getLeft();
}
  
return temp;
}

/*
* It is a Breath First Search algorithm in a tree.
* It traverses according to the level of the each node
*
* if there are no elements then return null otherwise traverse the tree
*
* @return
* - list of integers at each level from the root.
*/
public List levelOrderTravesal() {
  
}

/*
* Find the parent node for the given node.
*
* @return
* - returns the parent node.
*
* @param
* - takes the 'node' to which it has to find the parent
*/
private BinaryHeap findParent(BinaryHeap node) {
BinaryHeap temp = root;
BinaryHeap parent = null;
  
while(temp != null) {
if(node.getData() < temp.getData()) {
parent = temp;
temp = temp.getLeft();
}
else if(node.getData() > temp.getData()) {
parent = temp;
temp = temp.getRight();
}
else if(node.getData() == temp.getData())
return parent;
}
  
if(temp != null)
return parent;
else
return null;
}

/*
* Finds the node of the given integer 'x'
*
* @return
* - Returns the 'node' of the given integer 'x'
*
* @param
* - Takes the integer to which it has to find the node.
*/
private BinaryHeap find(int x) {
BinaryHeap node = root;
while(node != null) {
if(x < node.getData())
node = node.getLeft();
else if(x > node.getData())
node = node.getRight();
else if(x == node.getData())
return node;
}
return null;
}
}

####binaryheap####

package com.binarytree;

public class BinaryHeap {

private int data;
private BinaryHeap left;
private BinaryHeap right;
  
public BinaryHeap(int x) {
data = x;
left = null;
right = null;
}

public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public BinaryHeap getLeft() {
return left;
}
public void setLeft(BinaryHeap left) {
this.left = left;
}
public BinaryHeap getRight() {
return right;
}
public void setRight(BinaryHeap right) {
this.right = right;
}
}

Delete an element from the tree. When you are deleting an element from the tree, the following steps to be considered: Find the 'node' (x) of that element. Find the 'minimum node' (y) which is in the right subtree of the 'node' (x). Replace the ‘node' (x) with ‘minimum node, (y). Make sure the parent nodes of node(x) and minimum node (y), points to the correct node when replacing x and y 1. 2. 3. 4. Ex: When we delete '10' from fig. 1 then the resultant tree looks like: 12 14 Need to implement the following methods: Method levelordertraversal) It traverses all the nodes which are in different levels of a tree. delete(int x) Implementation It deletes the element 'x' from the tree. Note: You are advised to use the auxiliary helper methods 'findParent', findMinimumNode', 'find', replace' and 'iterator which are provided in the source files. You can also check the elements present in the tree with the help of 'levelordertraversal

Explanation / Answer

Delete Method:

public void delete(int x)
{
BinaryHeap heap=new BinaryHeap(x);
   BinaryHeap p=root;
   BinaryHeap g;
   BinaryHeap q=root;
while(p!=NULL)
   {
       if(n<p.getData())
       {
           q=p;
           p=p.getLeft();

       }
        else if(n>p.getData())
       {
           q=p;
           p=p.getRight();
        }
        else
           break;
   }
    if(p==NULL)
        System.out.println(" there is no such element..");

   else if(p.getLeft()==NULL||p.getRight==NULL)
    {
       if(n<q.getData())
       {
           if(p.getLeft()==NULL)
               q.getLeft()=p.getRight();
           else
              q.getLeft()=p.getLeft();
       }
        else
        {
            if(p.getLeft()==NULL)
               q.getRight()=p.getRight();
           else
              q.getRight()=p.getRight();
       }
   }
    else if(p.getLeft()!=NULL&&p.getRight()!=NULL)
   {
       g=p.getRight();
       if(g.getLeft==NULL)
        {
           g.getLeft()=p.getLeft();
           g.getRight()=p.getRight().getRight();
           if(n==q.getLeft().getData())
              q.getLeft()=g;
          else
               q.getRight()=g;
        }
       else
       {
           while(g.getLeft()!=NULL)
          {
              h=g;
              g=g.getLeft();
          }
          h.getLeft()=g.getLeft();
          g.getLeft()=p.getLeft();
          g.getRight()=p.getRight();
          if(n==q.getLeft().getData())
              q.getLeft()=g;
          else
              q.getRight()=g;
       }
    }
}

levelordertravesal:

public List levelOrderTravesal(BinaryHeap r)
{
  
   if(r!=NULL)
   {
       System.out.println(r.getData());
       levelOrderTravesal(r.getLeft());
       levelOrderTravesal(r.getRight());
}
return;
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.