Chapter 25, Problem 25.1PE

Program Plan Intro

Program Plan:

• Include the required import statement.
• Define the main class.
  • Define the main method using public static main.
    • Allocate memory to the class “Test”.
    • Define the “Test” class.
    • Declare the object for the BST.
    • Display the initial height of the tree.
    • Get the input string from the user.
    • Display the height of the tree.
    • Call the “breathFirstTraversal” method.
    • Create an object and set the string values to that object.
    • Again call the “breathFirstTraversal” method.
    • Create an integer object for class and set the integer values to that object.
    • Display the results.
  • Define the “BST” class.
    • Declare the required variables.
    • Create a default BST class.
    • Create a binary tree from an array of objects.
    • The “height” method will return the height of the tree.
    • Define “breathFirstTraversal” method.
      • Declare the linked list.
      • Add the values to the list.
      • If the list is not empty print the elements.
      • If the left node is not null, add the value to the left subtree.
      • If the right node is not null, add the value to the right subtree.
    • Define the “search” method.
      • Start the traverse from the root of the tree.
      • If the search element is in the left subtree set that value in “current” variable otherwise set the “current” variable as right subtree value.
    • Define the “insert” method.
      • If the root is null create the tree otherwise insert the value into left or right subtree.
    • Define the “createNewNode”
      • Return the result of new node creations.
    • Define the “inorder”
      • Inorder traverse from the root.
    • Define the protected “inorder” method
      • Traverse the tree according to the inorder traversal concept.
    • Define the “postorder”
      • Postorder traverse from the root.
    • Define the protected “postorder” method
      • Traverse the tree according to the postorder traversal concept.
    • Define the “preorder”
      • Preorder traverse from the root.
    • Define the protected “preorder” method
      • Traverse the tree according to the preorder traversal concept.
    • Define the “TreeNode” class
      • Declare the required variables.
      • Define the constructor.
    • Define the “getSize” method.
      • Return the size.
    • Define the “getRoot” method
      • Return the root.
    • Define the “java.util.ArrayList” method.
      • Create an object for the array list.
      • If the “current” is not equal to null, add the value to the list.
      • If the “current” is less than 0, set the “current” as left subtree element otherwise set the “current” as right subtree element.
      • Return the list.
    • Define the “delete” method.
      • If the “current” is not equal to null, add the value to the list.
      • If the “current” is less than 0, delete the “current” as left subtree element otherwise delete the “current” as right subtree element.
      • Return the list.
    • Define the “iterator” method.
      • Call the “inorderIterator” and return the value.
    • Define the “inorderIterator”
      • Create an object for that method and return the value
    • Define the “inorderIterator” class.
      • Declare the variables.
      • Define the constructor.
        • Call the “inorder” method.
      • Define the “inorder” method.
        • Call the inner “inorder” method with the argument.
      • Define the TreeNode “inorder” method.
        • If the root value is null return the value, otherwise add the value into the list.
      • Define the “hasNext” method
        • If the “current” value is less than size of the list return true otherwise return false.
      • Define the “next” method
        • Return the list.
      • Define the “remove” method.
        • Call the delete method.
        • Clear the list then call the “inorder” method.
    • Define the “clear” method
      • Set the values to the variables
  • Define the interface.
    • Declare the required methods.
    • Define the required methods.

Program Description Answer

The below program will add the “breathFirstTraversal” method in the given BST class as follows:

Explanation of Solution

Program:

//import statement

import java.util.*;

//class Test

public class Test

{

// main method

public static void main(String[] args)

{

//allocation of memory

new Test();

}

//definition of "Test"

public Test()

{

//declaration an object of BST

BST<String> tree = new BST<>();

//get the input from the user

System.out.print("The height of tree is " + tree.height());

Scanner input = new Scanner(System.in);

//print the statement

System.out.print("\nEnter strings: ");

//check the condition

for (int i = 0; i < 6; i++)

{

//get the input from the user

String s = input.next();

//insert the value

tree.insert(s.trim());

}

//get the input from the user

System.out.print("\nThe height of tree is " + tree.height());

//insert the value to the tree

tree.insert("Green");

//get the input from the user

System.out.print("\nThe height of tree is " + tree.height());

//print the new line

System.out.println();

//call the "breadthFirstTraversal" method

tree.breadthFirstTraversal();

//create the object for the BST

BST<String> tree1 = new BST<>(new String[]

{"Tom", "George", "Jean", "Jane", "Kevin", "Peter", "Susan",

"Jen", "Kim", "Michael", "Michelle"});

//print the statement

System.out.print("\nThe breadth-first traversal is ");

//call the "breadthFirstTraversal" method

tree1.breadthFirstTraversal();

//get the input from the user

System.out.print("\nThe height of tree1 is " + tree1.height());

//create the object for the BST

BST<Integer> tree2 =

new BST<>(new Integer[]{50, 45, 35, 48, 59, 51, 58});  

//print the statement

System.out.print("\nThe breadth-first traversal for tree2 is ");

//call the "breadthFirstTraversal" method

tree2.breadthFirstTraversal();

//get the input from the user

System.out.print("\nThe height of tree2 is " + tree2.height());  

}

//definition of "BST" class

public class BST<E extends Comparable<E>> implements Tree<E>

{

//declare the variables

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)

{

//check the condition

for (int i = 0; i < objects.length; i++)

//insert the values

insert(objects[i]);

}

// definition of "height"

public int height()

{

//returns the height of this binary tree

return height(root);

}

// definition of "height"

private int height(TreeNode root)

{

//check the condition

if (root == null)

{

//return the value

return -1;

}

else

{

//return the value

return 1 + Math.max(height(root.left), height(root.right));

}

}

// definition of "breadthFirstTraversal" method

public void breadthFirstTraversal()

{

//declaration of linked list

java.util.LinkedList <TreeNode<E>> queue =

new java.util.LinkedList<TreeNode<E>>();

//check the condition

if (root == null)

//return statement

return;

//add the value to the queue

queue.add(root);

//check the condition

while (!queue.isEmpty())

{

//declaration of variable

TreeNode<E> node = queue.removeFirst();

//print the statement

System.out.print (node.element + " ");

//check the condition

if (node.left != null)

//add the value to the queue

queue.add(node.left);

//check the condition

if (node.right != null)

//add the value to the queue

queue.add(node.right);

}

}

//definition of "search" method

public boolean search(E e)

{

//start from the root

TreeNode<E> current = root;

//check the condition

while (current != null)

{

//check the condition

if (e.compareTo(current.element) < 0)

{

//set the value

current = current.left;

}

//check the condition

else if (e.compareTo(current.element) > 0)

{

//set the value

current = current.right;

}

//otherwise

else

//return statement

return true;

}

//return statement

return false;

}

//definition of "insert" method

public boolean insert(E e)

{

//check the condition

if (root == null)

//create a new root

root = createNewNode(e);

//otherwise

else

{

// locate the parent node

TreeNode<E> parent = null;

TreeNode<E> current = root;

//check the condition

while (current != null)

//check the condition

if (e.compareTo(current.element) < 0)

{

//set the value

parent = current;

current = current.left;

}

//check the condition

else if (e.compareTo (current.element) > 0)

{

//set the value

parent = current;

current = current.right;

}

//otherwise

else

//return statement

return false;

//check the condition

if (e.compareTo (parent.element) < 0)

//create a new node

parent.left = createNewNode(e);

else

//create a new node

parent.right = createNewNode(e);

}

//increment the size

size++;

//return statement

return true;

}

//definition of "createNewNode"

protected TreeNode<E> createNewNode(E e)

{

//return the statement

return new TreeNode<E>(e);

}

//definition of "inorder"

public void inorder()

{

//inorder traverse from the root

inorder(root);

}

//definition of inorder

protected void inorder(TreeNode<E> root)

{

//check the condition

if (root == null)

//return statement

return;

// inorder traversal from a subtree

inorder(root.left);

//display the element

System.out.print(root.element + " ");

// inorder traversal from a subtree

inorder(root.right);

}

// definition of "postoder"

public void postorder()

{

// postorder traversal from the root

postorder(root);

}

// definition of "postorder"

protected void postorder(TreeNode<E> root)

{

//check the condition

if (root == null)

//return statement

return;

//postorder traversal from a subtree

postorder(root.left);

postorder(root.right);

//display the element

System.out.print(root.element + " ");

}

//definition of "preorder"

public void preorder()

{

// preorder traversal from the root

preorder(root);

}

//definition of "preorder"

protected void preorder(TreeNode<E> root)

{

//check the condition

if (root == null)

//return statement

return;

//display the value

System.out.print(root.element + " ");

// preorder traversal from a subtree

preorder(root.left);

preorder(root.right);

}

//definition of "TreeNode" class

public class TreeNode<E extends Comparable<E>>

{

//declare the variables

E element;

TreeNode<E> left;

TreeNode<E> right;

//definition of constructor

public TreeNode(E e)

{

//set the value

element = e;

}

}

// definition of "getSize" method

public int getSize()

{

//return statement

return size;

}

// definition of "getRoot" method

public TreeNode getRoot()

{

//return statement

return root;

}

// definition of method

public java.util.ArrayList<TreeNode<E>> path(E e)

{

//create an object

java.util.ArrayList<TreeNode<E>> list = new java.util.ArrayList<TreeNode<E>>();

// start from the root

TreeNode<E> current = root;

//check the condition

while (current != null)

{

//add the node to the list

list.add(current);

//check the condition

if (e.compareTo(current.element) < 0)

{

//set the value

current = current.left;

}

//check the condition

else if (e.compareTo(current.element) > 0)

{

//set the value

current = current.right;

}

else

//break statement

break;

}

//return statement

return list;

}

//definition of "delete" method

public boolean delete(E e)

{

// declare the variables

TreeNode<E> parent = null;

TreeNode<E> current = root;

//check the condition

while (current != null)

{

//check the condition

if (e.compareTo(current.element) < 0)

{

//set the value

parent = current;

current = current.left;

}

//check the condition

else if (e.compareTo(current.element) > 0)

{

//set the value

parent = current;

current = current.right;

}

else

//break statement

break;

}

//check the condition

if (current == null)

return false;

//check the condition

if (current.left == null)

{

//check the condition

if (parent == null)

{

//set the value

root = current.right;

}

else

{

//check the condition

if (e.compareTo(parent.element) < 0)

//set the value

parent.left = current.right;

else

//set the value

parent.right = current.right;

}

}

else

{

//set the value

TreeNode<E> parentOfRightMost = current;

TreeNode<E> rightMost = current.left;

//check the condition

while (rightMost.right != null)

{

//set the value

parentOfRightMost = rightMost;

rightMost = rightMost.right;

}

//set the value

current.element = rightMost.element;

//check the condition

if (parentOfRightMost.right == rightMost)

//set the value

parentOfRightMost.right = rightMost.left;

else

//set the value

parentOfRightMost.left = rightMost.left;

}

//decrement the "size"

size--;

//return statement

return true;

}

//definition of "iterator"

public java.util.Iterator<E> iterator()

{

//return statement

return inorderIterator();

}

//definition of "inorderIterator"

public java.util.Iterator<E> inorderIterator()

{

//return statement

return new InorderIterator();

}

// definition of class "InorderIterator"

class InorderIterator implements java.util.Iterator

{

// store the elements in a list

private java.util.ArrayList<E> list = new java.util.ArrayList<E>();

//declare the variable

private int current = 0;

//constructor

public InorderIterator()

{

//call the method

inorder();

}

/*definition of inorder traversal from the root */

private void inorder()

{

//call the method

inorder(root);

}

/*definition of inorder traversal from a subtree */

private void inorder(TreeNode<E> root)

{

//check the condition

if (root == null)

//return statement

return;

//call the method

inorder(root.left);

//add the value to the list

list.add(root.element);

//call the method

inorder(root.right);

}

//definition of "hasNext"

public boolean hasNext()

{

//check the condition

if (current < list.size())

//return statement

return true;

//return statement

return false;

}

//definition of "next" method

public Object next()

{

//return statement

return list.get(current++);

}

// definition of "remove" method

public void remove()

{

//delete the current element

delete(list.get(current));

// clear the list

list.clear();

// rebuild the list

inorder();

}

}

// definition of "clear" method

public void clear()

{

//set the values

root = null;

size = 0;

}

}

//definition of interface

public interface Tree<E> extends java.util.Collection<E>

{

//declaration of methods

public boolean search(E e);

public boolean insert(E e);

public boolean delete(E e);

public int getSize();

// definition of default method

public default void inorder()

{

}

// definition of default method

public default void postorder()

{

}

// definition of default method

public default void preorder()

{

}

// definition of default method

public default boolean isEmpty()

{

//return statement

return size() == 0;

};

@Override

// definition of default method

public default boolean contains(Object e)

{

//return statement

return search((E)e);

}

@Override

// definition of default method

public default boolean add(E e)

{

//return statement

return insert(e);

}

@Override

// definition of default method

public default boolean remove(Object e)

{

//return statement    

return delete((E)e);

}

@Override

// definition of default method

public default int size()

{

//return statement

return getSize();

}

@Override

// definition of default method

public default boolean containsAll(Collection<?> c)

{

//return statement

return false;

}

@Override

// definition of default method

public default boolean addAll(Collection<? extends E> c)

{

//return statement

return false;

}

@Override

// definition of default method

public default boolean removeAll(Collection<?> c)

{

//return statement

return false;

}

@Override

// definition of default method

public default boolean retainAll(Collection<?> c)

{

//return statement

return false;

}

@Override

// definition of default method

public default Object[] toArray()

{

//return statement

return null;

}

@Override

// definition of default method

public default <T> T[] toArray(T[] array)

{

//return statement

return null;

}

}

}

Sample Output

The height of tree is -1

Enter strings: aaa

bbb

ccc

ddd

eee

fff

The height of tree is 5

The height of tree is 5

aaa Green bbb ccc ddd eee fff

The breadth-first traversal is Tom George Jean Jane Kevin Jen Peter Kim Susan Michael Michelle

The height of tree1 is 7

The breadth-first traversal for tree2 is 50 45 59 35 48 51 58

The height of tree2 is 3