package com.binarytree; import java.util.Iterator; import java.util.List; public

Question

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()+" ");
}
}
}

}

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;
}
}

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;
}
}

a blackboard.albany.edu , University at Albany - MyUAlbany Portal Labs- Spring 2016-Data Structures https://blackboard.albany.edu/bbcswebdav/pid-2270843-dt-content-rid-10683...+ Lab 11 ICSI 310- Data Structures Level Order Traversal or Breath First Search This traversal works by visiting each node which are in different levels of the tree. Traversal starts from the 'root node and goes till it reaches the leaf nodes. Level -0 Level 1 10 Level -2 12 Fig. 1 14 Level 3 For Example, from the above graph it traverses as follows: First it visits '5 Second it visits '5's children '3' and '10 Third it visits '3's children which is only '2 Fourth it visits '10's children which are '8' and '12' Lastly since there are no children for '2' and '8', it will go to '12's children which is '14 Hence the total traversing looks like: 5, 3,10, 2, 8, 12,14 Hint: You need to use a 'queue' data structure and keep on enqueue when you are visiting new node and apply dequeue to visit their children.

Explanation / Answer

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()+" ");
}
}
}

}

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;

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);
}
}


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);
}

public void delete(int x) {
}


private BinaryHeap findMinimumNode(BinaryHeap node) {
BinaryHeap temp = node;
  
while(temp.getLeft() != null) {
temp = node.getLeft();
}
  
return temp;
}


public List levelOrderTravesal() {
  
}



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;
}


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;
}
}

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;
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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