Finish remove(int x) method and leveltraversal() method in BinarySearchTree clas
ID: 3694754 • Letter: F
Question
Finish remove(int x) method and leveltraversal() method in BinarySearchTree class.
//BINARY HEAP CLASS
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;
}
}
//BINARY SEARCH TREE CLASS
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;
}
}
//MAIN CLASS
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()+" ");
}
}
}
}
Explanation / Answer
Hello there ,
Please find below code and it's Output.
Let me know if you have any quereis.
Thanks.
package com.binarytree;
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 'No such Element in the tree'
*
* @param - integer that has to be removed from the tree.
*/
public void delete(int x) {
root = delete(root, x);
}
private BinaryHeap delete(BinaryHeap node, int x) {
if (node == null)
return null;
if (find(x) == null) {
System.out.println("No such Element in the tree.");
return node;
}
int cmp = x - node.getData();
if (cmp < 0)
node.setLeft(delete(node.getLeft(), x));
else if (cmp > 0)
node.setRight(delete(node.getRight(), x));
else {
if (node.getRight() == null)
return node.getLeft();
if (node.getLeft() == null)
return node.getRight();
BinaryHeap t = node;
node = findMinimumNode(t.getRight());
node.setRight(deleteMin(t.getRight()));
node.setLeft(t.getLeft());
}
return node;
}
private BinaryHeap deleteMin(BinaryHeap x) {
if (x.getLeft() == null)
return x.getRight();
x.setLeft(deleteMin(x.getLeft()));
return 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() {
if (root != null) {
Queue<Integer> keys = new LinkedList<Integer>();
Queue<BinaryHeap> queue = new LinkedList<BinaryHeap>();
queue.add(root);
while (!queue.isEmpty()) {
BinaryHeap x = queue.remove();
if (x == null)
continue;
keys.add(x.getData());
queue.add(x.getLeft());
queue.add(x.getRight());
}
return (List) keys;
} else {
return null;
}
}
/*
* 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;
}
}
===O/P==
Tree has : 5 3 10 2 8 12 14
Delete : 14
Tree has : 5 3 10 2 8 12
Delete : 3
Tree has : 5 2 10 8 12
Delete : 10
Tree has : 5 2 12 8
Delete : 5
Tree has : 8 2 12
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.