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

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.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() 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 = 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; }