Assignment •  FAQ •  Development Guide •  Code •  Checklist  

HW7 Assignment

What to do?

You must turn in your program by Wednesday, November 10th, 2021 at 11:59am (NOON).
In the assignment, you are to implement a binary tree data structure. This structure will be used to allow variable assignment in the calculator, as in hw6. You are also to write the member methods for the UCSDStudent class as part of the Driver.java file used to test your Tree data structure. Please note that you do not have to implement the copy constructor or assignValue() for your UCSDStudent.

Modifications to provided and existing code:

You are to provide the missing code to the member methods in the Tree.java file, and the missing portions of the UCSDStudent class definition to the Driver.java file.

The binary tree will be of the structure described in class. Each binary tree contains one Tree instance and zero or more TNode instances. A Tree contains root, occupancy, and name of the tree (treeName). Nodes of the binary tree are represented by TNode objects. Each TNode contains the data stored in the TNode, height and balance information, and references to left and right children, as well as to the parent TNode. Each TNode of the Tree will have a hasBeenDeleted field, which is used for the lazy remove algorithm. This simplifies removing a TNode from the Tree such that the binary tree does not have to be restructured when a non-leaf node is removed.

Note that the insert, lookup, and remove methods must be LOOP-BASED for this assignment. Any use of recursion for these methods (insert, lookup, and remove) will have a SEVERE negative impact on your grade for this assignment.

The Tree methods to write in Tree.java:

public static void debugOn ()
public static void debugOff ()

public Tree (String name, String caller)
public void jettison ()
public void jettisonAllNodes (TNode root)
public boolean insert (Whatever element)
public boolean isEmpty ()
public Whatever lookup (Whatever element)
public Whatever remove (Whatever element)

The TNode methods to write in Tree.java:

public TNode (Whatever element, String caller)
public void jettison ()

Additional code to write in Driver.java:

Add appropriate class methods for UCSDStudent

For all methods in this assignment, make sure to include code to display the corresponding catastrophic error and debug messages.

Method Descriptions

debugOn:

Turns on debugging for this Tree.

debugOff:

Turns off debugging for this Tree.

Tree constructor:

Allocates and initializes the memory associated with the Tree object. You should provide an initial value to each Tree data member.

  • Values of name are expected to be a String displayed when writing the Tree.
  • Values of caller are expected to be a String indicate where this method is called.
    •

    jettison:

    Called when jettison this Tree. Here, you need to jettison all of the nodes in the tree.
    Hint: What method might you use to do that?

    jettisonAllNodes:

  • Values of root are expected to be a TNode.

    • insert:

    Inserts the element into the binary tree. Returns true or false indicating success of insertion.

  • Values of element are expected to be complete elements (both name and number are preset) to insert.
    •

    isEmpty:

    Checks if tree is empty or not.

    lookup:

    Looks up the matching data in the binary tree. Returns a pointer to the data if found, null otherwise.

  • Values of element are expected to be incomplete elements (name is present but number is missing) to look up.
    •

    remove:

    Removes the matching data from the binary tree. Returns a pointer to the data if found, null otherwise.

  • Values of element are expected to be incomplete elements (name is present but number is missing) to remove.
    •

    TNode constructor:

    Allocates and initializes the memory associated with the TNode object.

  • Values of element are expected to be the data stored in the TNode. They must be of the same type as the rest of the objects present in the tree.
  • Values of caller are expected to be a String of where this method is being called.
    •

    jettison:

    The TNode jettison method, which is called to jettison this TNode.

    Grading breakdown

    Comments/Documentation:
    20%
    Style:
    14%
    Correctness/Execution:
    66%

    How to get started?

    Enter the following commands into the terminal.

    cd
    cd ../public/hw7
    make install
    cd
    cd hw7/java
    mv Tree.java.empty Tree.java
    mv Driver.java.empty Driver.java
    ls

     

      Assignment •  FAQ •  Development Guide •  Code •  Checklist