Question

TreeBuilder.java This class is used to create the binary trees for the program. They must be created using a queue-based approach, very similar to the level-order traversal that uses queues, but here the tree is being built rather than traversed. This class must use generics to build trees of any type.

In Java. How would this method look?

LinkedBinaryTree.java

import java.util.Iterator;

public class LinkedBinaryTree implements BinaryTreeADT {
   private BinaryTreeNode root;

   /**
   * Creates an empty binary tree.
   */
   public LinkedBinaryTree() {
       root = null;
   }
   /**
   * Creates a binary tree from an existing root.
   */
   public LinkedBinaryTree(BinaryTreeNode root) {
       this.root = root;
   }

   /**
   * Creates a binary tree with the specified element as its root.
   * @param element the element that will become the root of the new binary tree
   */
   public LinkedBinaryTree (T dataItem) {
       root = new BinaryTreeNode (dataItem);
   }

   /**
   * Constructor creates a tree from a node storing dataItem as root and two subtrees
   * as left and right subtrees of root.
   * @param dataItem       data to be stored at root node
   * @param leftSubtree   left subtree
   * @param rightSubtree   right subtree
   */

   public LinkedBinaryTree (T dataItem, LinkedBinaryTree leftSubtree,
           LinkedBinaryTree rightSubtree) {
       root = new BinaryTreeNode (dataItem);
       if (leftSubtree != null) root.setLeft(leftSubtree.root);
       else root.setLeft(null);

       if (rightSubtree !=null) root.setRight(rightSubtree.root);
       else root.setRight(null);
   }   

   /**
   * Returns a reference to root node
   * @return a reference to the root node
   */
   public BinaryTreeNode getRoot() {
       return root;
   }   

   /**
   * Returns a reference to the element at the root
   * @return a reference to the specified target
   * @throws EmptyCollectionException if the tree is empty
   */
   public T getDataRoot() throws EmptyCollectionException {
       if (isEmpty()) {
           throw new EmptyCollectionException("Empty tree");
       }
       return root.getData();
   }

   /**
   * Returns true if this binary tree is empty and false otherwise.
   * @return true if this binary tree is empty
   */
   public boolean isEmpty() {
       return root == null;
   }

   /**
   * Returns the integer size of this tree.
   * @return the integer size of this tree
   */
   public int size (BinaryTreeNode r) {
       if (r == null) {
           return 0;
       }

       int tmp = 1;

       if (r.getLeft() != null) {
           tmp += size(r.getLeft());
       }
       if (r.getRight() != null) {
           tmp += size(r.getRight());
       }

       return tmp;
   }

   /**
   * Returns true if the tree with root r contains an element that matches the
   * specified target element and false otherwise.
   * @param r                           root r of a binary tree
   * @param targetElement the element being sought in this tree
   * @return true if the element in is this tree
   * @throws ElementNotFoundException if an element not found exception occurs
   */
   public boolean contains (BinaryTreeNode r, T targetElement) {
       if (r == null) {
           return false;
       }

       if (r.getData().equals(targetElement)) {
           return true;
       } else {

           if (r.getLeft() != null) {
               boolean tmp = contains(r.getLeft(), targetElement);
               if (tmp) {
                   return true;
               }
           }
           if (r.getRight() != null) {
               boolean tmp = contains(r.getRight(), targetElement);
               if (tmp) {
                   return true;
               }
           }

       }

       return false;
   }

   /**
   * Performs an inorder traversal on this binary tree by calling an
   * overloaded, recursive inorder method that starts with
   * the root.
   * @return an in order iterator over this binary tree
   */
   public Iterator iteratorInOrder() {
       ArrayUnorderedList tempList = new ArrayUnorderedList();
       inorder (root, tempList);

       return tempList.iterator();
   }

   /**
   * Performs a recursive inorder traversal.
   * @param node the node to be used as the root for this traversal
   * @param tempList the temporary list for use in this traversal
   */
   protected void inorder (BinaryTreeNode node, ArrayUnorderedList tempList) {
       if (node != null) {
           inorder (node.getLeft(), tempList);
           tempList.addToRear(node.getData());
           inorder (node.getRight(), tempList);
       }
   }

   /**
   * Performs an preorder traversal on this binary tree by calling
   * an overloaded, recursive preorder method that starts with
   * the root.
   * @return an pre order iterator over this tree
   */
   public Iterator iteratorPreOrder() {
       ArrayUnorderedList tempList = new ArrayUnorderedList();
       preorder(root, tempList);

       return tempList.iterator();
   }

   /**
   * Performs a recursive preorder traversal.
   * @param node the node to be used as the root for this traversal
   * @param tempList the temporary list for use in this traversal
   */
   protected void preorder (BinaryTreeNode node, ArrayUnorderedList tempList) {
       if (node != null) {
           tempList.addToRear(node.getData());
           preorder(node.getLeft(), tempList);
           preorder(node.getRight(), tempList);
       }
   }

   /**
   * Performs an postorder traversal on this binary tree by calling
   * an overloaded, recursive postorder method that starts
   * with the root.
   * @return a post order iterator over this tree
   */
   public Iterator iteratorPostOrder() {
       ArrayUnorderedList tempList = new ArrayUnorderedList();
       postorder(root, tempList);

       return tempList.iterator();
   }

   /**
   * Performs a recursive postorder traversal.
   * @param node the node to be used as the root for this traversal
   * @param tempList the temporary list for use in this traversal
   */
   protected void postorder (BinaryTreeNode node, ArrayUnorderedList tempList) {
       if (node != null) {
           postorder(node.getLeft(), tempList);
           postorder(node.getRight(), tempList);
           tempList.addToRear(node.getData());
       }
   }

   /**
   * Performs a levelorder traversal on this binary tree, using a
   * templist.
   * @return a levelorder iterator over this binary tree
   */
   public Iterator iteratorLevelOrder() {
       ArrayUnorderedList tempList = new ArrayUnorderedList();
       LinkedQueue> queue = new LinkedQueue>();
       BinaryTreeNode node = null;

       queue.enqueue(root);

       while (!queue.isEmpty()) {
           node = queue.dequeue();
           tempList.addToRear(node.getData());
           // Add left child.
           if (node.getLeft() != null) {
               queue.enqueue(node.getLeft());
           }
           // Add right child.
           if (node.getRight() != null) {
               queue.enqueue(node.getRight());
           }
       }

       return tempList.iterator();
   }   
}

Answer 1

// TreeBuilder.java

public class TreeBuilder<T> {

   /* method that takes as input an array containing set of values to insert in the new tree's nodes
   * and return the created LinkedBinaryTree object
   */
   public LinkedBinaryTree<T> BuildTree(T array[])
   {
       // create dataQueue to contain all elements of array
       LinkedQueue<T> dataQueue = new LinkedQueue<T>();
       // loop to insert all elements of array in the same order as present in array
       for(int i=0;i<array.length;i++)
       {
           dataQueue.enqueue(array[i]);
       }
      
       // create an empty parentQueue of BinaryNodes
       LinkedQueue<BinaryTreeNode<T>> parentQueue = new LinkedQueue<BinaryTreeNode<T>>();
      
       // create the tree's root node with the first element of dataQueue
       BinaryTreeNode<T> root = new BinaryTreeNode<T>(dataQueue.dequeue());
       parentQueue.enqueue(root); // enqueue root node to parentQueue
      
       // loop till dataQueue is not empty
       while(!dataQueue.isEmpty())
       {
           T a = dataQueue.dequeue(); // dequeue from dataQueue
           T b = dataQueue.dequeue(); // dequeue from dataQueue
          
           // remove the front element from parent
           BinaryTreeNode<T> parent = parentQueue.dequeue();
          
           if(a != null) // if a is not null
           {
               // create a new node with data as a
               BinaryTreeNode<T> node = new BinaryTreeNode<T>(a);
               parent.setLeft(node); // set left child of parent as node
               parentQueue.enqueue(node); // enqueue node to parentQueue
           }
          
           if(b != null) // if b is not null
           {
               // create a new node with data as b
               BinaryTreeNode<T> node = new BinaryTreeNode<T>(b);
               parent.setRight(node); // set right child of parent as node
               parentQueue.enqueue(node); // enqueue node to parentQueue
           }
       }
      
       // return a new Tree with root node as root
       return new LinkedBinaryTree<T>(root);
   }

}

//end of TreeBuilder.java