Problem Description: city.txt has a list of cities which are added using Binary
ID: 3708696 • Letter: P
Question
Problem Description:
city.txt has a list of cities which are added using Binary search tree insert algorithm.
? Cities are to be traversed in Inorder, Preorder and Postorder from the root WITHOUT USING
RECURSION. You need to use Stack push() and pop() to accomplish your task.
? Then you need to search whether a city exists in the tree or not. If the city exist, its path from
the root is displayed for you, else display false
1) Write the code for the following methods to implement traversal BST in BST.java:
- protected void inorder(TreeNode<E> root)
- protected void postorder(TreeNode<E> root)
- protected void preorder(TreeNode<E> root)
- public boolean search(E e)
2) Run the program for city.txt already provided and see if the traversal output is displayed correctly.
Below is the file in which students will have to write their code wherever they find a comment: /*
YOUR CODE HERE */
BST.java
package bst;
import java.util.Stack;
public class BST<E extends Comparable<E>> implements Tree<E> {
protected TreeNode<E> root;
protected int size = 0;
/** Create a default binary tree */
public BST() {
}
/** Create a binary tree from an array of objects */
public BST(E[] objects) {
for (int i = 0; i < objects.length; i++)
add(objects[i]);
}
@Override /** Returns true if the element is in the tree */
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root
/* YOUR CODE HERE */
return false;
}
@Override /** Insert element e into the binary tree
* Return true if the element is inserted successfully */
public void insert(E e) {
root = insertRecord(root, e);
}
@SuppressWarnings("unchecked")
public TreeNode insertRecord(TreeNode root, E e){
if (root == null) {
root = new TreeNode(e);
System.out.print(root.element + " ");
size++;
return root;
}
if (e.compareTo((E) root.element) < 0)
root.left = insertRecord(root.left, e);
else if (e.compareTo((E) root.element) > 0)
root.right = insertRecord(root.right, e);
return root; // Element inserted successfully
}
protected TreeNode<E> createNewNode(E e) {
return new TreeNode<>(e);
}
@Override /** Inorder traversal from the root */
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode<E> root) {
/* YOUR CODE HERE */
}
@Override /** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Postorder traversal from a subtree */
protected void postorder(TreeNode<E> root) {
/* YOUR CODE HERE */
}
@Override /** Preorder t7raversal from the root */
public void preorder() {
preorder(root);
}
/** Preorder traversal from a subtree */
protected void preorder(TreeNode<E> root) {
/* YOUR CODE HERE */
}
@Override /** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode<E> getRoot() {
return root;
}
/** Returns a path from the root leading to the specified element */
public java.util.ArrayList<TreeNode<E>> path(E e) {
java.util.ArrayList<TreeNode<E>> list =
new java.util.ArrayList<>();
TreeNode<E> current = root; // Start from the root
while (current != null) {
list.add(current); // Add the node to the list
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else
break;
}
return list; // Return an array list of nodes
}
@Override /** Delete an element from the binary tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
break; // Element is in the tree pointed at by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left child
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
}
else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // Element deleted successfully
}
@Override /** Obtain an iterator. Use inorder. */
public java.util.Iterator<E> iterator() {
return new InorderIterator();
}
@Override /** Remove all elements from the tree */
public void clear() {
root = null;
size = 0;
}
}
Java helper files (Students DO NOT need to change them):
TestBST.java
package bst;
import java.io.BufferedReader;
import java.io.File;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.FileInputStream;
import java.util.Scanner;
public class TestBST {
public static void main(String[] args) {
// Create a BST
BST<String> tree = new BST<>();
try { // reads in words from a file
String word;
BufferedReader diskInput = new BufferedReader(new InputStreamReader(new
FileInputStream(new File(args[0]))));
Scanner input = new Scanner(diskInput);
while (input.hasNext()) {
word = input.next();
word = word.toLowerCase();
tree.insert(word);
}
} catch (IOException e) {
System.out.println("io exception");
}
System.out.println();
// Traverse tree
System.out.print("Inorder: ");
tree.inorder();
System.out.print(" Postorder: ");
tree.postorder();
System.out.print(" Preorder: ");
tree.preorder();
System.out.print(" The number of nodes is " + tree.getSize());
// Search for an element
boolean found = false;
found = tree.search("athens");
System.out.print(" Is athens in the tree? " + found);
if(found){
// Get a path from the root to athens
System.out.print(" A path from the root to athens is: ");
java.util.ArrayList<TreeNode<String>> path = tree.path("athens");
for (int i = 0; path != null && i < path.size(); i++)
System.out.print(path.get(i).element + " ");
}
found = false;
found = tree.search("assignment4");
System.out.print(" Is assignment4 in the tree? " + found);
}
}
InorderIterator.java
package bst;
import bst.TreeNode;
// Inner class InorderIterator
public class InorderIterator<E extends Comparable<E>> implements
java.util.Iterator<E> {
// Store the elements in a list
private java.util.ArrayList<E> list = new java.util.ArrayList<>();
private int current = 0; // Point to the current element in list
protected TreeNode<E> root;
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/** Inorder traversal from the root */
private void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
private void inorder(TreeNode<E> root) {
if (root == null)
return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
@Override /** More elements for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
@Override /** Get the current element and move to the next */
public E next() {
return list.get(current++);
}
}
Tree.java
package bst;
import java.util.Collection;
public interface Tree<E> extends Collection<E> {
/** Return true if the element is in the tree */
public boolean search(E e);
/** Insert element e into the binary tree
* Return true if the element is inserted successfully */
public void insert(E e);
/** Delete the specified element from the tree
* Return true if the element is deleted successfully */
public boolean delete(E e);
/** Get the number of nodes in the tree */
public int getSize();
/** Inorder traversal from the root*/
public default void inorder() {
}
/** Postorder traversal from the root */
public default void postorder() {
}
/** Preorder traversal from the root */
public default void preorder() {
}
@Override /** Return true if the tree is empty */
public default boolean isEmpty() {
return this.size() == 0;
};
@Override
public default boolean contains(Object e) {
return search((E)e);
}
@Override
public default boolean add(E e) {
return true;
}
@Override
public default boolean remove(Object e) {
return delete((E)e);
}
@Override
public default int size() {
return getSize();
}
@Override
public default boolean containsAll(Collection<?> c) {
// Left as an exercise
return false;
}
@Override
public default boolean addAll(Collection<? extends E> c) {
// Left as an exercise
return false;
}
@Override
public default boolean removeAll(Collection<?> c) {
// Left as an exercise
return false;
}
@Override
public default boolean retainAll(Collection<?> c) {
// Left as an exercise
return false;
}
@Override
public default Object[] toArray() {
// Left as an exercise
return null;
}
@Override
public default <T> T[] toArray(T[] array) {
// Left as an exercise
return null;
}
}
TreeNode.java
package bst;
/**
* This inner class is static, because it does not access any instance members
* defined in its outer class
*/
public class TreeNode<E> {
protected E element;
protected TreeNode<E> left;
protected TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
city.txt
newyork
cairo
toronto
barcelona
london
paris
rome
athens
venice
SAMPLE OUTPUT:
Inserted tree to traverse:
Explanation / Answer
import java.util.Stack;
public class BST<E extends Comparable<E>> implements Tree<E> {
protected TreeNode<E> root;
protected int size = 0;
/** Create a default binary tree */
public BST() {
}
/** Create a binary tree from an array of objects */
public BST(E[] objects) {
for (int i = 0; i < objects.length; i++)
add(objects[i]);
}
@Override /** Returns true if the element is in the tree */
----------------------- Page 2-----------------------
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root
while(true){
if(current.element.compareTo(e) < 0){
if(current.right == null){
return false;
}
current = current.right;
}else if(current.element.compareTo(e) > 0){
if(current.left == null){
return false;
}
current = current.left;
}else{
return true;
}
}
return false;
}
@Override /** Insert element e into the binary tree
* Return true if the element is inserted successfully */
public void insert(E e) {
root = insertRecord(root, e);
}
@SuppressWarnings("unchecked")
public TreeNode insertRecord(TreeNode root, E e){
if (root == null) {
root = new TreeNode(e);
System.out .print(root.element + " ");
size++;
return root;
}
if (e.compareTo((E) root.element) < 0)
root.left = insertRecord(root.left, e);
else if (e.compareTo((E) root.element) > 0)
root.right = insertRecord(root.right, e);
return root; // Element inserted successfully
}
protected TreeNode<E> createNewNode(E e) {
return new TreeNode<>(e);
}
@Override /** Inorder traversal from the root */
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode<E> root) {
Stack<TreeNode<E>> stck = new Stack<>();
if(root == null){
return;
}
stck.push(root);
TreeNode<E> new_node = root.left;
while(!stck.empty()){
if(new_node == null){
new_node = stck.pop();
System.out.println(new_node.element+" ");
new_node = new_node.right;
}else{
stck.push(new_node);
new_node = new_node.left;
}
}
}
@Override /** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Postorder traversal from a subtree */
protected void postorder(TreeNode<E> root) {
if (root == null) {
return;
}
Stack<TreeNode<E>> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode<E> next = stack.peek();
boolean finishedSubtrees = (next.right == root || next.left == root);
boolean isLeaf = (next.left == null && next.right == null);
if (finishedSubtrees || isLeaf) {
stack.pop();
System.out.println(next.element+" ");
root = next;
}
else {
if (next.right != null) {
stack.push(next.right);
}
if (next.left != null) {
stack.push(next.left);
}
}
}
}
----------------------- Page 3-----------------------
@Override /** Preorder t7raversal from the root */
public void preorder() {
preorder(root);
}
/** Preorder traversal from a subtree */
protected void preorder(TreeNode<E> root) {
Stack<TreeNode<E>> stck = new Stack<>();
if(root == null){
return;
}
stck.push(root);
System.out.println(root.element+" ");
TreeNode<E> new_node = root.left;
while(!stck.empty()){
if(new_node == null){
new_node = stck.pop();
new_node = new_node.right;
}else{
stck.push(new_node);
System.out.println(new_node.element+" ");
new_node = new_node.left;
}
}
}
@Override /** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode<E> getRoot() {
return root;
}
/** Returns a path from the root leading to the specified element */
public java.util.ArrayList<TreeNode<E>> path(E e) {
java.util.ArrayList<TreeNode<E>> list =
new java.util.ArrayList<>();
TreeNode<E> current = root; // Start from the root
while (current != null) {
list.add(current); // Add the node to the list
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else
break;
}
return list; // Return an array list of nodes
}
@Override /** Delete an element from the binary tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
----------------------- Page 4-----------------------
parent = current;
current = current.right;
}
else
break; // Element is in the tree pointed at by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left child
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
}
else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // Element deleted successfully
}
@Override /** Obtain an iterator. Use inorder. */
public java.util.Iterator<E> iterator() {
return new InorderIterator();
}
@Override /** Remove all elements from the tree */
public void clear() {
----------------------- Page 5-----------------------
root = null;
size = 0;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.