QuestionQuestion

Problem Description
For this homework, you need to download the following files from moodle:

• BinaryTree.java
• TestBinaryTree.java
• TestBinarySearchTree.java • Startup.java

Part 1
The BinaryTree.java file contains an implementation of Binary Tree. However, signatures for the following methods are provided but their bodies are not defined.

• width(): should compute and return the width of the tree.
• breadthFirstTraverse(): should traverse the tree in breadth-first order and return a string that represents the breadth-first traversal sequence of the tree.
• postOrderTraverse():should traverse the tree in post order and return a string that represents the post order depth first traversal sequence of the tree.
• inOrderTraverse():should traverse the tree in order and return a string that represents the in order depth first traversal sequence of the tree.

You need to implement the bodies of the aforementioned methods so that they perform the computation in accordance with what they are meant for. For this task you must use your own implementation of queue, that can grow in size when necessary. You must NOT make any other modifications in BinaryTree.java.

Currently the test code in TestBinaryTree.java fails due to empty implementation of the aforementioned two methods. Your implementation, if done correctly, should make all the tests pass. Do NOT modify or submit this provided test code.

Part 2
You need to write BinarySearchTree.java file that should include a generic implementation of a Binary Search Tree in BinarySearchTree class, which must extend/inherit from the provided Binary Tree class (defined in BinaryTree.java).

Your BinarySearchTree must provide the following methods, in addition to any other methods you want:

• public void insert( AnyType value ): add the given element to the binary search tree (does nothing for duplicate entries).
• public void remove(AnyType value): remove the given value from the binary search tree.
• public boolean contains( AnyType value ): returns true if the given value is found in the binary search tree, and false otherwise. 
Your implementation of BinarySearchTree must pass all the tests provided in TestBinarySearchTree.java. Your implementation must also work with the provided Startup.java. Do NOT modify or submit this provided test code.

Test Code
• Your implementation in BinaryTree.java must pass all the JUnit tests provided in TestBinaryTree.java.
• Your implementation of BinarySearchTree must pass all the JUnit tests provided in TestBinarySearchTree.java.

For more about JUnit testing, please see the instructions available on moodle in Homework 2 package.

ReadMe.txt
When the description of the assignment does not explicitly specify something, you have the liberty to make your choices in those scenarios. Please mention any design choices you made including any reasoning behind your choices in a ReadMe.txt file. If you could not complete a certain part correctly, mention it in ReadMe.txt. If you did not find anything to include in the file, simply put your name and email address.

Startup.java
Provided Startup.java contains a main method, which can work as a starting point for your program. For this assignment, this Startup class acts as a sandbox for you to make use of your BinarySearchTree. Your implementation of BinarySearchTree must work with the provided Startup.java. Do NOT submit this provided Startup.java.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.util.ArrayList;
import java.util.List;

public class BinaryTree<T> {

    BinaryNode<T> root = null;

    private T nullSymbol = null;

    /**
    * Default constructor
    */
    public BinaryTree() {

    }

    /**
    * This constructor is useful for test purposes, not meant for use in
    * general.
    *
    * Constructs a binary tree from a given valid breadth-first traversal
    * sequence.
    *
    * @param seq is an array containing breadth-first traversal sequence of the
    * nodes of a tree.
    */
    public BinaryTree(T[] seq) {
       initFromBfsSequence(seq);
    }

    /**
    * This constructor is useful for test purposes, not meant for use in
    * general.
    *
    * Constructs a binary tree from a given valid breadth-first traversal
    * sequence. A given special symbol (nullSymbol) in the sequence is
    * interpreted as absence of node. During construction of the tree, when
    * such a special symbol is encountered, that is considered to be an absent
    * node, and thus no corresponding node is added to the tree.
    *
    * @param seq is an array containing breadth-first traversal sequence of the
    * nodes of a tree.
    * @param nullSymbol is a special symbol in the given sequence that denotes
    * absence of a node.
    */
    public BinaryTree(T[] seq, T nullSymbol) {
       this.nullSymbol = nullSymbol;
       initFromBfsSequence(seq);
    }

    private void initFromBfsSequence(T[] seq) {
       try {
            if (seq.length == 0) {
                throw new IllegalArgumentException("Cannot build tree from empty sequence");
            }
       } catch (IllegalArgumentException e) {
            System.out.println(e.getMessage());
            return;
       }

       try {
            if (seq[0].equals(nullSymbol)) {
                throw new IllegalArgumentException("Symbol for root cannot be nullSymbol");
            }
       } catch (IllegalArgumentException e) {
            System.out.println(e.getMessage());
            return;
       }
       /*if (seq.length == 0) {
            throw new IllegalArgumentException("Cannot build tree from empty sequence");
       }

       if (seq[0].equals(nullSymbol)) {
            throw new IllegalArgumentException("Symbol for root cannot be nullSymbol");
       }
*/
       List<BinaryNode<T>> nodes = new ArrayList<BinaryNode<T>>(seq.length);
       this.root = new BinaryNode<T>(seq[0]);
       nodes.add(root);

       for (int i = 0; i < seq.length; i++) {
            if (nodes.get(i) == null) {
                handelNullParentNode(nodes, i, seq.length);
            } else {
                handleNonNullParentNode(nodes, i, seq);
            }
       }
    }

    // This method will handle the null nodes in the iteration of nodes.get(i) in initFromBfsSequence method.
    private void handelNullParentNode(List<BinaryNode<T>> nodes,
            int nullNodeIndex, int seqLength) {
       int leftIndex = (nullNodeIndex * 2) + 1; // finding the left child index from formula

       if (leftIndex < seqLength) {
            nodes.add(null);

            int rightIndex = (nullNodeIndex * 2) + 2; // finding the right child index from formula
            if (rightIndex < seqLength) {
                nodes.add(null);
            }
       }
    }

    // This method will handle the non-null nodes in the iteration of nodes.get(i) in initFromBfsSequence method.
    private void handleNonNullParentNode(List<BinaryNode<T>> nodes,
            int parentIndex, T[] seq) {
       int leftIndex = (parentIndex * 2) + 1;
       if (leftIndex < seq.length) { //need to check if the index falls outdise of the list index
            BinaryNode<T> leftNode = null;
            if (!seq[leftIndex].equals(nullSymbol)) {
                leftNode = new BinaryNode<T>(seq[leftIndex]);
            }
            nodes.get(parentIndex).leftNode = leftNode;
            nodes.add(leftNode);

            int rightIndex = (parentIndex * 2) + 2;
            if (rightIndex < seq.length) {
                BinaryNode<T> rightNode = null;
                if (!seq[rightIndex].equals(nullSymbol)) {
                   rightNode = new BinaryNode<T>(seq[rightIndex]);
                }
                nodes.get(parentIndex).rightNode = rightNode;
                nodes.add(rightNode);
            }
       }
    }...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$50.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Computer Science - Other Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats