[solved]-Classes Needed Complete Programming Questions Displayed Thank Q39027916
Below are the classes needed to complete the programmingquestions which are displayed above. Thank you.
1. Extend the class BinaryTree to include a boolean method that determines whether a binary tree is a BST. ANSWER: public boolean isBinarySearchTree() { return isBST (root); //helper method called by isBinarySearchTree public boolean isBST (BinaryTreeNode<T> tree) { 2. Extend the class BinaryTree to include a boolean method similarTrees that determines whether the shapes of two trees are the same (the nodes do not have to contain the same values, but each node must have the same number of children) ANSWER: public boolean similarTrees (BinaryTreeNode<T> otherTree) return similar (root, otherTree); //helper method called by similarTrees public boolean similar (BinaryTreeNode<T> treel, BinaryTreeNode<T> tree2) 3-4. Extend the class BinaryTree to include 2 more methods: nodeCount (count the number of leaves in a binary tree) and leavesCount (count the number of nodes in a binary tree). Use recursion in both! Add statements to the client program (lecture notes) to test these new added methods. ANSWER: public int treeLeavesCount() { return leavesCount (root); //helper method called by treeLeavesCount private int leavesCount (BinaryTreeNode<T> t) { public int treeNodeCount() return nodeCount (root); //helper method called by treeNodeCount private int node Count (BinaryTreeNode<T> t) • Binary Tree ADT – Java implementation //Interface: BinaryTreeADT public interface BinaryTreeADT<T> extends Cloneable public Object clone(); //Returns a clone of this BT. public boolean isEmpty(); //Method to determine whether the BT is empty. public void inOrder Traversal(); //Method to do an inorder traversal of a BT. public void preOrderTraversal(); //Method to do a preorder traversal of a BT. 10 void postorderTraversal(); //Method to do a postorder traversal of a BT. public int treeHeight(); //Method to determine the height of a BT. public int treeNodeCount(); //Method to find the number of nodes in a binary tree. public int treeLeaves Count(); //Method to determine the number of leaves in a BT. public void destroyTree(); //Method to destroy a BT. public boolean search (T item); //Method to determine whether item is in a BT. public void insert (T item); //Method to insert item in a BT. public void delete (T item);//Method to delete item from a BT. 1/Class: BinaryTree implements //Interface: BinaryTreeADT //Inner class: BinaryTreeNode import java.util.NoSuchelementException; public abstract class BinaryTree<T> implements BinaryTreeADT<T> //Definition of the BinaryTreeNode class protected class BinaryTreeNode<T> 1 public T info; public BinaryTreeNode<T> lLink; public BinaryTreeNode<T> rLink; //Default constructor //Default constructor public BinaryTreeNode () info – null; Link – null; Link – null; //Alternate constructor public BinaryTreeNode (T item) { info – item 1 Link – null; Link – null; //Alternate constructor public BinaryTreeNode (T item, BinaryTreeNode<T> left, BinaryTreeNode<T> right) info – item; 1 Link – left: rLink – right; public Object elone () { BinaryTreeNode<T> copy – null; try! copy – (BinaryTreeNode<T>) super.clone(); catch (CloneNot SupportedException e) { return null; return copy public String toString() { return info.toString(); //Instance variable vor class BinaryTree protected BinaryTreeNode<I> root; 1/Default constructor public BinaryTree () root = null; //Instance variable vor class BinaryTree protected Binary TreeNode<T> root; //Default constructor public BinaryTree () { root – null; public Object clone () { BinaryTree<T> copy – null; try i copy – (BinaryTree<T>) super.elone(); catch (CloneNot SupportedException e) { return null; if (root ! – null) copy.root – copyTree (root); return copy; //helper method called by clone private BinaryTreeNode<T> copyTree (BinaryTreeNode<T> other TreeRoot) { BinaryTreeNode<T> temp; if (otherTree Root = null) temp = null; else { temp – (BinaryTreeNode<T>) otherTreeRoot.clone(); temp. 1 Link – copyTree (otherTreeRoot. lLink); temp.r Link – copyTree (otherTreeRoot. Link); return tempi public boolean is Empty() { return (root — null); public void inOrder Traversal() { inOrder (root); { //helper method called by inOrderTraversal private void inorder (BinaryTreeNode<T> t) if (t !- null) { inOrder (t.Link); System.out.print(t.info + “); inOrder (t.rLink); public void preOrder Traversal() { preorder (root); //helper method called by preOrder Traversal private void preOrder (BinaryTreeNode<T> t) if (t ! – null) { System.out.print(t.info + ” “); preOrder (t.lLink); preOrder (t.rLink); public void postorderTraversal() { postOrder (root); //helper method called by postOrder Traversal private void postOrder (BinaryTreeNode<T> t) { if (t !- null) { postOrder (t.lLink); postOrder (t.rLink); System.out.print(t.info + ” “); public int treeHeight() { return height (root); //helper method called by treeHeight private int height (BinaryTreeNode<T> t) { if (t — null) return 0; else if (t.1 Link — null && t. Link — null) return 0; else return 1 + Math.max(height (t. lLink), height(t.rLink)); { public int treeNodeCount() return nodeCount (root); //helper method called by treeNodeCount private int nodeCount(BinaryTreeNode<T> t) System.out.println(“To be done later.”); return 0; We were unable to transcribe this image//helper method called by treeNodeCount private int nodeCount (BinaryTreeNode<T> t) { System.out.println(“To be done later.”); return 0; public int treeLeavesCount() { return leaves Count (root); { //helper method called by treeLeavescount private int leavesCount (BinaryTreeNode<T> t) System.out.println(“To be done later.”); return 0; public void destroyTree () { root – null; //abstract methods public abstract boolean search(T item); public abstract void insert(T item); public abstract void delete (T item); 7/class: Binary Searchtree extends //Class: BinaryTree public class BinarySearchTree<T> extends BinaryTree<T> // Default constructor public BinarySearchTree () { super(); public boolean search (T item) { return recSearch (root, item); //helper: recursive method called by search public boolean recSearch (Binary TreeNode<T> tree, T item) if (tree — null) return false; else { Comparable<T> temp – (Comparable<T>) tree.info; if (temp.compareTo(item) — 0) return true; else if (temp.compareTo (item) > 0) return recSearch (tree. lLink, item); else return recSearch (tree.rLink, item); public void insert(T item) { root – recInsert (root, item); //helper: recursive method called by insert public BinaryTreeNode<T> reeInsert (BinaryTreeNode<T> tree, T item) if (tree = null) { //create new node tree – new BinaryTreeNode<T>(item); else { Comparable<T> temp – (Comparable<T>) tree.info, if (temp.compareTo (item) — 0){ System.err.print(“Already in – duplicates are not allowed.”); return null; else if (temp.compareTo (item) > 0) tree. Link – reeInsert (tree. 1 Link, item); else tree. ILink – reeInsert (tree. Link, item); return tree; public void delete (T item) { root – recDelete (root, item); //helper: recursive method called by delete public BinaryTreeNode<T> recDelete (BinaryTreeNode<T> tree, Titem) if (tree — null) { //empty tree System.err.println(“Cannot delete from an empty tree.”); return null; elset Comparable<T> temp – (Comparable<T>) tree. info: if (temp.compareto (ites) > 0) tree. ILink – recDelete (tree. ILink, item); else if (temp.compareTo(ites) < 0) tree. Link – recDelete (tree. Link, item); else if(tree. Link !- null && tree. ILink ! – null) { // 2 children tree.info – findMin (tree. Link).info; //tree.info – findMax (tree. Link).info; tree. Link – removeMin (tree. Link); else if (root. Link ! – null) 1/1 left child tree tree.lLink: else if (root.rLink !- null) 1/1 right child tree – tree. Link; return tree; //helper: method called by recDelete protected BinaryTreeNode<T> findMin (BinaryTreeNode<T> tree) { if (tree ! – null) while(tree. ILink ! – null) tree – tree. Link; return tree; 1/helper: method called by recDelete protected BinaryTreeNode<T> removeMin (BinaryTreelodecT> tree) if (tree = null) { //empty tree System.err.println(“Cannot delete from an empty tree.”); return null; else if(tree. Link !- null) { tree. Link – removeMin (tree. lLink); return tree; else return tree. Link; 1/class: clientBST // Input in this order: 70 83 39 27 45 94 55 80 85 105 40 95 102 52 50 125 110 999 import java.util.Scanner; public class clientBST ! public static void main(String[] args) { Scanner input – new Scanner (System.in); BinarySearchTree<Integer> bst – new Binary SearchTree<Integer>(); Integer num; System.out.print(“Enter integers (999 to stop): “); num – input.nextInt(); while (num ! – 999) bst.insert (num); num – input.nextInt(); System.out.println(“Tree Height: ” + bst.treeHeight()); System.out.print(“Enter value to search for: “); num – input.nextInt (); if (bst.search (num)) System.out.println (num + – was found in this tree”); else System.out.println(num + – was NOT found in this tree”); System.out.print(“Inorder traversal: “); bst.inOrderTraversal(); System.out.print(“nPreorder traversal: “); bst.preOrder Traversal(); System.out.print(“nPostorder traversal: “); bst-post Order Traversal(); System.out.print(“nEnter value to be deleted from tree: “); num – input.nextInt(); bst.delete (num); System.out.print(“nInorder traversal after removing” + num + “: “); bst.inOrder Traversal(); System.out.print(“nPreorder traversal after removing ” + num + “: “); bst.preOrder Traversal(); System.out.print(“nPostorder traversal after removing + num + “: “); bst-post Order Traversal(); System.out.println(); OUTPUT: Enter integers (999 to stop) : 70 83 39 27 45 94 55 80 85 105 40 95 102 52 50 125 110 999 Tree Height: 5 Enter value to search for: 55 55 was found in this tree Inorder traversal: 27 39 40 45 50 52 55 70 80 83 85 94 95 102 105 110 125 Preorder traversal: 70 39 27 45 40 55 52 50 83 BO 94 85 105 95 102 125 110 Postorder traversal: 27 40 50 52 55 45 39 80 85 102 95 110 125 105 94 83 70 Enter value to be deleted from tree: 83 Inorder traversal after removing 83: 27 39 40 45 50 52 55 70 80 85 94 95 102 105 110 125 Preorder traversal after removing 83: 70 39 27 45 40 55 52 50 85 BO 94 105 95 102 125 110 Postorder traversal after removing 83: 27 40 50 52 55 45 39 BO 102 95 110 125 105 94 85 70 Show transcribed image text 1. Extend the class BinaryTree to include a boolean method that determines whether a binary tree is a BST. ANSWER: public boolean isBinarySearchTree() { return isBST (root); //helper method called by isBinarySearchTree public boolean isBST (BinaryTreeNode tree) { 2. Extend the class BinaryTree to include a boolean method similarTrees that determines whether the shapes of two trees are the same (the nodes do not have to contain the same values, but each node must have the same number of children)
ANSWER: public boolean similarTrees (BinaryTreeNode otherTree) return similar (root, otherTree); //helper method called by similarTrees public boolean similar (BinaryTreeNode treel, BinaryTreeNode tree2) 3-4. Extend the class BinaryTree to include 2 more methods: nodeCount (count the number of leaves in a binary tree) and leavesCount (count the number of nodes in a binary tree). Use recursion in both! Add statements to the client program (lecture notes) to test these new added methods. ANSWER: public int treeLeavesCount() { return leavesCount (root); //helper method called by treeLeavesCount private int leavesCount (BinaryTreeNode t) { public int treeNodeCount() return nodeCount (root); //helper method called by treeNodeCount private int node Count (BinaryTreeNode t)
• Binary Tree ADT – Java implementation //Interface: BinaryTreeADT public interface BinaryTreeADT extends Cloneable public Object clone(); //Returns a clone of this BT. public boolean isEmpty(); //Method to determine whether the BT is empty. public void inOrder Traversal(); //Method to do an inorder traversal of a BT. public void preOrderTraversal(); //Method to do a preorder traversal of a BT. 10 void postorderTraversal(); //Method to do a postorder traversal of a BT. public int treeHeight(); //Method to determine the height of a BT. public int treeNodeCount(); //Method to find the number of nodes in a binary tree. public int treeLeaves Count(); //Method to determine the number of leaves in a BT. public void destroyTree(); //Method to destroy a BT. public boolean search (T item); //Method to determine whether item is in a BT. public void insert (T item); //Method to insert item in a BT. public void delete (T item);//Method to delete item from a BT. 1/Class: BinaryTree implements //Interface: BinaryTreeADT //Inner class: BinaryTreeNode import java.util.NoSuchelementException; public abstract class BinaryTree implements BinaryTreeADT //Definition of the BinaryTreeNode class protected class BinaryTreeNode 1 public T info; public BinaryTreeNode lLink; public BinaryTreeNode rLink; //Default constructor
//Default constructor public BinaryTreeNode () info – null; Link – null; Link – null; //Alternate constructor public BinaryTreeNode (T item) { info – item 1 Link – null; Link – null; //Alternate constructor public BinaryTreeNode (T item, BinaryTreeNode left, BinaryTreeNode right) info – item; 1 Link – left: rLink – right; public Object elone () { BinaryTreeNode copy – null; try! copy – (BinaryTreeNode) super.clone(); catch (CloneNot SupportedException e) { return null; return copy public String toString() { return info.toString(); //Instance variable vor class BinaryTree protected BinaryTreeNode root; 1/Default constructor public BinaryTree () root = null;
//Instance variable vor class BinaryTree protected Binary TreeNode root; //Default constructor public BinaryTree () { root – null; public Object clone () { BinaryTree copy – null; try i copy – (BinaryTree) super.elone(); catch (CloneNot SupportedException e) { return null; if (root ! – null) copy.root – copyTree (root); return copy; //helper method called by clone private BinaryTreeNode copyTree (BinaryTreeNode other TreeRoot) { BinaryTreeNode temp; if (otherTree Root = null) temp = null; else { temp – (BinaryTreeNode) otherTreeRoot.clone(); temp. 1 Link – copyTree (otherTreeRoot. lLink); temp.r Link – copyTree (otherTreeRoot. Link); return tempi public boolean is Empty() { return (root — null); public void inOrder Traversal() { inOrder (root); { //helper method called by inOrderTraversal private void inorder (BinaryTreeNode t) if (t !- null) { inOrder (t.Link); System.out.print(t.info + “);
inOrder (t.rLink); public void preOrder Traversal() { preorder (root); //helper method called by preOrder Traversal private void preOrder (BinaryTreeNode t) if (t ! – null) { System.out.print(t.info + ” “); preOrder (t.lLink); preOrder (t.rLink); public void postorderTraversal() { postOrder (root); //helper method called by postOrder Traversal private void postOrder (BinaryTreeNode t) { if (t !- null) { postOrder (t.lLink); postOrder (t.rLink); System.out.print(t.info + ” “); public int treeHeight() { return height (root); //helper method called by treeHeight private int height (BinaryTreeNode t) { if (t — null) return 0; else if (t.1 Link — null && t. Link — null) return 0; else return 1 + Math.max(height (t. lLink), height(t.rLink)); { public int treeNodeCount() return nodeCount (root); //helper method called by treeNodeCount private int nodeCount(BinaryTreeNode t) System.out.println(“To be done later.”); return 0;
//helper method called by treeNodeCount private int nodeCount (BinaryTreeNode t) { System.out.println(“To be done later.”); return 0; public int treeLeavesCount() { return leaves Count (root); { //helper method called by treeLeavescount private int leavesCount (BinaryTreeNode t) System.out.println(“To be done later.”); return 0; public void destroyTree () { root – null; //abstract methods public abstract boolean search(T item); public abstract void insert(T item); public abstract void delete (T item);
7/class: Binary Searchtree extends //Class: BinaryTree public class BinarySearchTree extends BinaryTree // Default constructor public BinarySearchTree () { super(); public boolean search (T item) { return recSearch (root, item); //helper: recursive method called by search public boolean recSearch (Binary TreeNode tree, T item) if (tree — null) return false; else { Comparable temp – (Comparable) tree.info; if (temp.compareTo(item) — 0) return true; else if (temp.compareTo (item) > 0) return recSearch (tree. lLink, item); else return recSearch (tree.rLink, item); public void insert(T item) { root – recInsert (root, item); //helper: recursive method called by insert public BinaryTreeNode reeInsert (BinaryTreeNode tree, T item) if (tree = null) { //create new node tree – new BinaryTreeNode(item); else { Comparable temp – (Comparable) tree.info, if (temp.compareTo (item) — 0){ System.err.print(“Already in – duplicates are not allowed.”); return null; else if (temp.compareTo (item) > 0) tree. Link – reeInsert (tree. 1 Link, item); else tree. ILink – reeInsert (tree. Link, item); return tree; public void delete (T item) { root – recDelete (root, item);
//helper: recursive method called by delete public BinaryTreeNode recDelete (BinaryTreeNode tree, Titem) if (tree — null) { //empty tree System.err.println(“Cannot delete from an empty tree.”); return null; elset Comparable temp – (Comparable) tree. info: if (temp.compareto (ites) > 0) tree. ILink – recDelete (tree. ILink, item); else if (temp.compareTo(ites) tree) if (tree = null) { //empty tree System.err.println(“Cannot delete from an empty tree.”); return null; else if(tree. Link !- null) { tree. Link – removeMin (tree. lLink); return tree; else return tree. Link;
1/class: clientBST // Input in this order: 70 83 39 27 45 94 55 80 85 105 40 95 102 52 50 125 110 999 import java.util.Scanner; public class clientBST ! public static void main(String[] args) { Scanner input – new Scanner (System.in); BinarySearchTree bst – new Binary SearchTree(); Integer num; System.out.print(“Enter integers (999 to stop): “); num – input.nextInt(); while (num ! – 999) bst.insert (num); num – input.nextInt(); System.out.println(“Tree Height: ” + bst.treeHeight()); System.out.print(“Enter value to search for: “); num – input.nextInt (); if (bst.search (num)) System.out.println (num + – was found in this tree”); else System.out.println(num + – was NOT found in this tree”); System.out.print(“Inorder traversal: “); bst.inOrderTraversal(); System.out.print(“nPreorder traversal: “); bst.preOrder Traversal(); System.out.print(“nPostorder traversal: “); bst-post Order Traversal(); System.out.print(“nEnter value to be deleted from tree: “); num – input.nextInt(); bst.delete (num); System.out.print(“nInorder traversal after removing” + num + “: “); bst.inOrder Traversal(); System.out.print(“nPreorder traversal after removing ” + num + “: “); bst.preOrder Traversal(); System.out.print(“nPostorder traversal after removing + num + “: “); bst-post Order Traversal(); System.out.println(); OUTPUT: Enter integers (999 to stop) : 70 83 39 27 45 94 55 80 85 105 40 95 102 52 50 125 110 999 Tree Height: 5 Enter value to search for: 55 55 was found in this tree Inorder traversal: 27 39 40 45 50 52 55 70 80 83 85 94 95 102 105 110 125 Preorder traversal: 70 39 27 45 40 55 52 50 83 BO 94 85 105 95 102 125 110 Postorder traversal: 27 40 50 52 55 45 39 80 85 102 95 110 125 105 94 83 70 Enter value to be deleted from tree: 83 Inorder traversal after removing 83: 27 39 40 45 50 52 55 70 80 85 94 95 102 105 110 125 Preorder traversal after removing 83: 70 39 27 45 40 55 52 50 85 BO 94 105 95 102 125 110 Postorder traversal after removing 83: 27 40 50 52 55 45 39 BO 102 95 110 125 105 94 85 70
Expert Answer
Answer to Below are the classes needed to complete the programming questions which are displayed above. Thank you…. . . .
OR
