Homework $1$:

$**25\mathrm{.}3($Implement inorder traversal without using recursion$)$ Implement the inorder

method in BST using a stack instead of recursion. Write a test program that

prompts the user to enter $15$ integers, stores them in a BST$,$ and invokes the

inorder method to display the elements.

Page

$6$

of $6$

package chapter$25$;

import java.util.Scanner;

import chapter$25.$Exercise$25\_03.$BST$.$TreeNode;

public class Exercise$25\_03$HW $\{$

public static void main$($String$[]$ args$)\{$

Scanner input $=$ new Scanner$($System$.$in$)$;

BST tree $=$ new BST;

$//$ Prompt the user to enter $10$ integers and store them in the tree

for $($int i $=0$; i $<mtext\; id="EditorElement\_114176"></mtext><mn\; id="EditorElement\_114177">1</mn><mn\; id="EditorElement\_114178">0</mn>$; i$++)\{$

tree.insert$($input$.$nextInt$())$;

$\}$

tree.inorder$()$;

tree.nonRecursiveInorder$()$;

BST tree$1=$ new BST;

tree$1.$insert$("$George$")$;

tree$1.$insert$("$Michael$")$;

tree$1.$insert$("$Tom$")$;

tree$1.$insert$("$Adam$")$;

tree$1.$insert$("$Jones$")$;

tree$1.$insert$("$Peter$")$;

tree$1.$insert$("$John$")$;

tree$1.$insert$("$Daniel$")$;

tree$1.$inorder$()$;

tree$1.$nonRecursiveInorder$()$;

$\}$

public static class BST$>$ implements Tree $\{$

protected TreeNode root;

protected int size $=0$;

$/**$ Create a default binary search tree $*/$

public BST$()\{$

$\}$

$/**$ Create a binary search tree from an array of objects $*/$

public BST$($E$[]$ objects$)\{$

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

insert$($objects$[$i$])$;

$\}$

$/**$ Return true if the element is in the tree $*/$

public boolean search$($E e$)\{$

TreeNode current $=$ root; $//$ Start from the root

while $($current $!=$ null$)\{$

if $($e$.$compareTo$($current$.$element$)<mtext\; id="EditorElement\_115008"></mtext><mn\; id="EditorElement\_115009">0</mn><mi\; id="EditorElement\_115010">)</mi><mtext\; id="EditorElement\_115011"></mtext><mi\; id="EditorElement\_115012">\{</mi>$

current $=$ current.left;

$\}$ else if $($e$.$compareTo$($current$.$element$)>0)\{$

current $=$ current.right;

$\}$ else

$//$ element matches current.element

return true; $//$ Element is found

$\}$

return false;

$\}$

$/**$

$*$ Insert element e into the binary search tree Return true if the

element is

$*$ inserted successfully

$*/$

public boolean insert$($E e$)\{$

if $($root $==$ null$)$

root $=$ createNewNode$($e$)$; $//$ Create a new root

else $\{$

$//$ Locate the parent node

TreeNode parent $=$ null;

TreeNode current $=$ root;

while $($current $!=$ null$)$

if $($e$.$compareTo$($current$.$element$)<mtext\; id="EditorElement\_115544"></mtext><mn\; id="EditorElement\_115545">0</mn><mi\; id="EditorElement\_115546">)</mi><mtext\; id="EditorElement\_115547"></mtext><mi\; id="EditorElement\_115548">\{</mi>$

parent $=$ current;

current $=$ current.left;

$\}$ else if $($e$.$compareTo$($current$.$element$)>0)\{$

parent $=$ current;

current $=$ current.right;

$\}$ else

return false; $//$ Duplicate node not inserted

$//$ Create the new node and attach it to the parent node

if $($e$.$compareTo$($parent$.$element$)<mtext\; id="EditorElement\_115823"></mtext><mn\; id="EditorElement\_115824">0</mn><mi\; id="EditorElement\_115825">)</mi>$

parent.left $=$ createNewNode$($e$)$;

else

parent.right $=$ createNewNode$($e$)$;

$\}$

size$++$;

return true; $//$ Element inserted

$\}$

protected TreeNode createNewNode$($E e$)\{$

return new TreeNode$($e$)$;

$\}$

$/**$ Inorder traversal from the root $*/$

public void inorder$()\{$

inorder$($root$)$;

$\}$

$/**$ Inorder traversal from a subtree $*/$

protected void inorder$($TreeNode root$)\{$

if $($root $==$ null$)$

return;

inorder$($root$.$left$)$;

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

inorder$($root$.$right$)$;

$\}$

$/**$ Postorder traversal from the root $*/$

public void postorder$()\{$

postorder$($root$)$;

$\}$

$/**$ Postorder traversal from a subtree $*/$

protected void postorder$($TreeNode root$)\{$

if $($root $==$ null$)$

return;

postorder$($root$.$left$)$;

postorder$($root$.$right$)$;

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

$\}$

$/**$ Preorder traversal from the root $*/$

public void preorder$()\{$

preorder$($root$)$;

$\}$

$/**$ Preorder traversal from a subtree $*/$

protected void preorder$($TreeNode root$)\{$

if $($root $==$ null$)$

return;

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

preorder$($root$.$left$)$;

preorder$($root$.$right$)$;

$\}$

$/**$ Inner class tree node $*/$

public static class TreeNode$>\{$

E element;

TreeNode left;

TreeNode right;

public TreeNode$($E e$)\{$

element $=$ e;

$\}$

$\}$

$/**$ Get the number of nodes in the tree $*/$

public int getSize$()\{$

return size;

$\}$

$/**$ Returns the root of the tree $*/$

public TreeNode getRoot$()\{$

return root;

$\}$

$/**$ Returns a path from the root leading to the specified element $*/$

public java.util.ArrayList$>$ path$($E e$)\{$

java.util.ArrayList$>$ list $=$ new

java.util.ArrayList$>()$;

TreeNode current $=$ root; $//$ Start from the root

while $($current $!=$ null$)\{$

list.add$($current$)$; $//$ Add the node to the list

if $($e$.$compareTo$($current$.$element$)<mtext\; id="EditorElement\_117453"></mtext><mn\; id="EditorElement\_117454">0</mn><mi\; id="EditorElement\_117455">)</mi><mtext\; id="EditorElement\_117456"></mtext><mi\; id="EditorElement\_117457">\{</mi>$

current $=$ current.left;

$\}$ else if $($e$.$compareTo$($current$.$element$)>0)\{$

current $=$ current.right;

$\}$ else

break;

$\}$

return list; $//$ Return an array of nodes

$\}$

$/**$

$*$ Delete an element from the binary search 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 parent $=$ null;

TreeNode current $=$ root;

while $($current $!=$ null$)\{$

if $($e$.$compareTo$($current$.$element$)<mtext\; id="EditorElement\_117973"></mtext><mn\; id="EditorElement\_117974">0</mn><mi\; id="EditorElement\_117975">)</mi><mtext\; id="EditorElement\_117976"></mtext><mi\; id="EditorElement\_117977">\{</mi>$

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 by current

$\}$

if $($current $==$ null$)$

return false; $//$ Element is not in the tree

$//$ Case $1$: current has no left children

if $($current$.$left $==$ null$)\{$

$//$ Connect the parent with the right child of the current

node

if $($parent $==$ null$)\{$

root $=$ current.right;

$\}$