(In JAVA) (Use Binary Search Tree)

Programming Steps:

1) Generate 20 random numbers from 1 to 100 inclusive. Write them to a text file called p9in.txt.

2) Read p9in.txt into a Binary Tree.

3) Write a menu similar to the following:

Choose the following:

1 Add a number into the tree

2 Delete a number from the tree

3 Preorder Traversal

4 Inorder Traversal

5 Postorder Traversal

6 Exit

4) Write the output to a file called p9out.txt

5) At least perform the following operations:

a. Write the content of the input file (from your generated random numbers)

b. Manually draw the tree using the numbers that you have generated.

c. Manually write 3 kinds of Traversal;

d. Have program print the results of 3 kinds of Traversal and compare them with the above.

e. Add a number to the tree and then write 3 kinds of Traversal;

f. Delete a number from the tree and then write 3 kinds of Traversal; Add some error handling if number not found.

III. The Sample Output File (Shown only for 10 random integers)

Result: (p9out.txt)

The generated input: 50 25 75 12 37 43 30 33 87 93 97

Preorder traversal: 50 25 12 37 30 33 43 75 87 93 97

Inorder traversal: 12 25 30 33 37 43 50 75 87 93 97

Postorder traversal: 12 33 30 43 37 25 97 93 87 75 50

Add 8:

(Followed by 3 kinds of Traversal)

Delete 30:

(Followed by 3 kinds of Traversal)

Delete 99:

** Number is not found **

Required programs:

BinaryTreeInterface.java:

/** An interface for the ADT binary tree. */ public interface BinaryTreeInterface extends TreeInterface, TreeIteratorInterface { /** Sets this binary tree to a new one-node binary tree. @param rootData The object that is the data for the new tree's root. */ public void setTree(T rootData); /** Sets this binary tree to a new binary tree. @param rootData The object that is the data for the new tree's root. @param leftTree The left subtree of the new tree. @param rightTree The right subtree of the new tree. */ public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree); } // end BinaryTreeInterface 

TreeInterface.java:

/** An interface of basic methods for the ADT tree. */ public interface TreeInterface { public T getRootData(); public int getHeight(); public int getNumberOfNodes(); public boolean isEmpty(); public void clear(); } // end TreeInterface 

TreeIteratorInterface.java:

import java.util.Iterator; /** An interface of iterators for the ADT tree. */ public interface TreeIteratorInterface { public Iterator getPreorderIterator(); public Iterator getPostorderIterator(); public Iterator getInorderIterator(); public Iterator getLevelOrderIterator(); } // end TreeIteratorInterface 

EmptyTreeException.java: 

public class EmptyTreeException extends RuntimeException { public EmptyTreeException() { this(null); } // end default constructor public EmptyTreeException(String message) { super(message); } // end constructor } // end EmptyTreeException 

BinaryNode.java:

class BinaryNode { private T data; private BinaryNode leftChild; // Reference to left child private BinaryNode rightChild; // Reference to right child public BinaryNode() { this(null); // Call next constructor } // end default constructor public BinaryNode(T dataPortion) { this(dataPortion, null, null); // Call next constructor } // end constructor public BinaryNode(T dataPortion, BinaryNode newLeftChild, BinaryNode newRightChild) { data = dataPortion; leftChild = newLeftChild; rightChild = newRightChild; } // end constructor /** Retrieves the data portion of this node. @return The object in the data portion of the node. */ public T getData() { return data; } // end getData /** Sets the data portion of this node. @param newData The data object. */ public void setData(T newData) { data = newData; } // end setData /** Retrieves the left child of this node. @return The nodes left child. */ public BinaryNode getLeftChild() { return leftChild; } // end getLeftChild /** Sets this nodes left child to a given node. @param newLeftChild A node that will be the left child. */ public void setLeftChild(BinaryNode newLeftChild) { leftChild = newLeftChild; } // end setLeftChild /** Detects whether this node has a left child. @return True if the node has a left child. */ public boolean hasLeftChild() { return leftChild != null; } // end hasLeftChild /** Retrieves the right child of this node. @return The nodes right child. */ public BinaryNode getRightChild() { return rightChild; } // end getRightChild /** Sets this nodes right child to a given node. @param newRightChild A node that will be the right child. */ public void setRightChild(BinaryNode newRightChild) { rightChild = newRightChild; } // end setRightChild /** Detects whether this node has a right child. @return True if the node has a right child. */ public boolean hasRightChild() { return rightChild != null; } // end hasRightChild /** Detects whether this node is a leaf. @return True if the node is a leaf. */ public boolean isLeaf() { return (leftChild == null) && (rightChild == null); } // end isLeaf /** Counts the nodes in the subtree rooted at this node. @return The number of nodes in the subtree rooted at this node. */ public int getNumberOfNodes() { int leftNumber = 0; int rightNumber = 0; if (leftChild != null) leftNumber = leftChild.getNumberOfNodes(); if (rightChild != null) rightNumber = rightChild.getNumberOfNodes(); return 1 + leftNumber + rightNumber; } // end getNumberOfNodes /** Computes the height of the subtree rooted at this node. @return The height of the subtree rooted at this node. */ public int getHeight() { return getHeight(this); // Call private getHeight } // end getHeight private int getHeight(BinaryNode node) { int height = 0; if (node != null) height = 1 + Math.max(getHeight(node.getLeftChild()), getHeight(node.getRightChild())); return height; } // end getHeight /** Copies the subtree rooted at this node. @return The root of a copy of the subtree rooted at this node. */ public BinaryNode copy() { BinaryNode newRoot = new BinaryNode<>(data); if (leftChild != null) newRoot.setLeftChild(leftChild.copy()); if (rightChild != null) newRoot.setRightChild(rightChild.copy()); return newRoot; } // end copy } // end BinaryNode 

BinaryTree.java:

import java.util.Iterator; import java.util.NoSuchElementException; //import StackAndQueuePackage.*; // Needed by tree iterators /** A class that implements the ADT binary tree. */ public class BinaryTree implements BinaryTreeInterface { private BinaryNode root; public BinaryTree() { root = null; } // end default constructor public BinaryTree(T rootData) { root = new BinaryNode<>(rootData); } // end constructor public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { privateSetTree(rootData, leftTree, rightTree); } // end constructor public void setTree(T rootData) { root = new BinaryNode<>(rootData); } // end setTree public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { privateSetTree(rootData, (BinaryTree)leftTree, (BinaryTree)rightTree); } // end setTree private void privateSetTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { root = new BinaryNode<>(rootData); if ((leftTree != null) && !leftTree.isEmpty()) root.setLeftChild(leftTree.root); if ((rightTree != null) && !rightTree.isEmpty()) { if (rightTree != leftTree) root.setRightChild(rightTree.root); else root.setRightChild(rightTree.root.copy()); } // end if if ((leftTree != null) && (leftTree != this)) leftTree.clear(); if ((rightTree != null) && (rightTree != this)) rightTree.clear(); } // end privateSetTree public T getRootData() { if (isEmpty()) throw new EmptyTreeException(); else return root.getData(); } // end getRootData public boolean isEmpty() { return root == null; } // end isEmpty public void clear() { root = null; } // end clear protected void setRootData(T rootData) { root.setData(rootData); } // end setRootData protected void setRootNode(BinaryNode rootNode) { root = rootNode; } // end setRootNode protected BinaryNode getRootNode() { return root; } // end getRootNode public int getHeight() { return root.getHeight(); } // end getHeight public int getNumberOfNodes() { return root.getNumberOfNodes(); } // end getNumberOfNodes public Iterator getPreorderIterator() { return new PreorderIterator(); } // end getPreorderIterator public Iterator getInorderIterator() { return new InorderIterator(); } // end getInorderIterator public Iterator getPostorderIterator() { return new PostorderIterator(); } // end getPostorderIterator public Iterator getLevelOrderIterator() { return new LevelOrderIterator(); } // end getLevelOrderIterator private class PreorderIterator implements Iterator { private StackInterface> nodeStack; public PreorderIterator() { nodeStack = new LinkedStack<>(); if (root != null) nodeStack.push(root); } // end default constructor public boolean hasNext() { return !nodeStack.isEmpty(); } // end hasNext public T next() { BinaryNode nextNode; if (hasNext()) { nextNode = nodeStack.pop(); BinaryNode leftChild = nextNode.getLeftChild(); BinaryNode rightChild = nextNode.getRightChild(); // Push into stack in reverse order of recursive calls if (rightChild != null) nodeStack.push(rightChild); if (leftChild != null) nodeStack.push(leftChild); } else { throw new NoSuchElementException(); } return nextNode.getData(); } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end PreorderIterator public void iterativePreorderTraverse() { StackInterface> nodeStack = new LinkedStack<>(); if (root != null) nodeStack.push(root); BinaryNode nextNode; while (!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); BinaryNode leftChild = nextNode.getLeftChild(); BinaryNode rightChild = nextNode.getRightChild(); // Push into stack in reverse order of recursive calls if (rightChild != null) nodeStack.push(rightChild); if (leftChild != null) nodeStack.push(leftChild); System.out.print(nextNode.getData() + " "); } // end while } // end iterativePreorderTraverse private class InorderIterator implements Iterator { private StackInterface> nodeStack; private BinaryNode currentNode; public InorderIterator() { nodeStack = new LinkedStack<>(); currentNode = root; } // end default constructor public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); } // end hasNext public T next() { BinaryNode nextNode = null; // Find leftmost node with no left child while (currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } // end while // Get leftmost node, then move to its right subtree if (!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); assert nextNode != null; // Since nodeStack was not empty // before the pop currentNode = nextNode.getRightChild(); } else throw new NoSuchElementException(); return nextNode.getData(); } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end InorderIterator public void iterativeInorderTraverse() { StackInterface> nodeStack = new LinkedStack<>(); BinaryNode currentNode = root; while (!nodeStack.isEmpty() || (currentNode != null)) { // Find leftmost node with no left child while (currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } // end while // Visit leftmost node, then traverse its right subtree if (!nodeStack.isEmpty()) { BinaryNode nextNode = nodeStack.pop(); assert nextNode != null; // Since nodeStack was not empty // before the pop System.out.print(nextNode.getData() + " "); currentNode = nextNode.getRightChild(); } // end if } // end while } // end iterativeInorderTraverse private class PostorderIterator implements Iterator { private StackInterface> nodeStack; private BinaryNode currentNode; public PostorderIterator() { nodeStack = new LinkedStack<>(); currentNode = root; } // end default constructor public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); } // end hasNext public T next() { boolean foundNext = false; BinaryNode leftChild, rightChild, nextNode = null; // Find leftmost leaf while (currentNode != null) { nodeStack.push(currentNode); leftChild = currentNode.getLeftChild(); if (leftChild == null) currentNode = currentNode.getRightChild(); else currentNode = leftChild; } // end while // Stack is not empty either because we just pushed a node, or // it wasn't empty to begin with since hasNext() is true. // But Iterator specifies an exception for next() in case // hasNext() is false. if (!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); // nextNode != null since stack was not empty before pop BinaryNode parent = null; if (!nodeStack.isEmpty()) { parent = nodeStack.peek(); if (nextNode == parent.getLeftChild()) currentNode = parent.getRightChild(); else currentNode = null; } else currentNode = null; } else { throw new NoSuchElementException(); } // end if return nextNode.getData(); } // end next /* public T next() { boolean foundNext = false; BinaryNode leftChild, rightChild, nextNode = null; // Find leftmost leaf while (currentNode != null) { nodeStack.push(currentNode); leftChild = currentNode.getLeftChild(); if (leftChild == null) currentNode = currentNode.getRightChild(); else currentNode = leftChild; } // end while // Stack is not empty either because we just pushed a node, or // it wasn't empty to begin with since hasNext() is true. // But Iterator specifies an exception for next() in case // hasNext() is false. if (!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); // nextNode != null since stack was not empty before pop BinaryNode parent = null; try { parent = nodeStack.peek(); if (nextNode == parent.getLeftChild()) currentNode = parent.getRightChild(); else currentNode = null; } catch(EmptyStackException e) { currentNode = null; } } else { throw new NoSuchElementException(); } // end if return nextNode.getData(); } // end next */ public void remove() { throw new UnsupportedOperationException(); } // end remove } // end PostorderIterator private class LevelOrderIterator implements Iterator { private QueueInterface> nodeQueue; public LevelOrderIterator() { nodeQueue = new LinkedQueue<>(); if (root != null) nodeQueue.enqueue(root); } // end default constructor public boolean hasNext() { return !nodeQueue.isEmpty(); } // end hasNext public T next() { BinaryNode nextNode; if (hasNext()) { nextNode = nodeQueue.dequeue(); BinaryNode leftChild = nextNode.getLeftChild(); BinaryNode rightChild = nextNode.getRightChild(); // Add to queue in order of recursive calls if (leftChild != null) nodeQueue.enqueue(leftChild); if (rightChild != null) nodeQueue.enqueue(rightChild); } else { throw new NoSuchElementException(); } return nextNode.getData(); } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end LevelOrderIterator } // end BinaryTree