A Modified Binary Tree such that each node contains (at least) the following properties:

public class BinaryTreeNode

{

public int data;

public BinaryTreeNode leftChild;

public BinaryTreeNode rightChild;

public BinaryTreeNode parent;

public BinaryTreeNode rightNode;

}

The Modified Binary Tree will use this Binary Tree Node to support the following:

1) The leftChild and rightChild pointers are used the same as an ordinary Binary Search Tree

2) The parent points to the parent BinaryTreeNode (if the BinaryTreeNode is root, parent is null)

3) The rightNode pointer points to the nearest Node to its right on the tree. This Node can either be a sibling or some other node that is on the same level. The far right node of a tree at any level should point to null.

This design modifies the standard Binary Search Tree. In the standard that we discussed in class, the left and right child pointers are such that the data value on the left of any Node is less than it and the data value on the right is greater. This standard remains for this Modified Binary Tree.

In addition, each Node can see (and thus, must maintain) the parent node. The complexity arises when also allowing each Node to see the next Node to its right on the same level (note that this can be the right sibling, first cousin, second cousin, etc.). The rightNode pointer allows us to basically have a Linked List at each level of the tree. For example:

6

4 8

2 7 9

1 3 10

Node 6: left = 4, right = 8, parent = null, rightNode = null

Node 4: left = 2, right = 7, parent = 6, rightNode = 8

Node 8: left = 7, right = 9, parent = 6, rightNode = null

Node 2: left = 1, right = 3, parent = 4, rightNode = 7

Node 3: left = null, right = null, parent = 2, rightNode = 10

...

Part 1) Complete the ModifiedBinaryTree class with the following functions:

public ModifiedBinaryTree()

public void insert(int n)

public boolean delete(int n)

public BinaryTreeNode getNode(int n)

public BinaryTreeNode getRightNode(BinaryTreeNode n)

public void printNode(int n)

public void printTree()

public void printLevel(int n)

The requirements for each function are as follows:

ModifiedBinaryTree():

This function is the default constructor for the Binary Tree and creates an empty tree

insert(int n):

This function inserts a new node into the tree. The insert algorithm is the same as a standard binary tree but you must also make sure to maintain the new nodes parent and rightNode pointers correctly

delete(int n):

This function deletes a node from the tree. The delete algorithm is the same as a standard binary tree but you must also make sure to maintain the correct pointers for all nodes that may be affected by the deletion. If the node is found and deleted, the function must return true, else return false

getNode(int n):

This function searches the tree for the node whose data property equals the given n. If the node is found, it returns the BinaryTreeNode. If the node is not found, the function returns null

getRightNode(BinaryTreeNode n):

This function returns the rightNode of the given BinaryTreeNode n. If there is no rightNode for the given node, the function must return null

printNode(int n):

This function searches the tree for a node with the given value n and prints all contents of the BinaryTreeNode. By printing, you must show the current data property and each BinaryTreeNode pointer property. For each BinaryTreeNode pointer, only show its data value. If the pointer is null, print NULL. For example, given the binary tree example on page 1 of this assignment, printNode(4) would display:

Data item: 4

leftChild: 2

rightChild: NULL

parent: 6

rightNode: 8

If you have other properties added to the BinaryTreeNode, you may want to show those property values as well (though these are minimum requirements)

printTree():

This function prints all the nodes in the tree. For each node that is printed, also print the level in which the node is in starting with the root node level as 1. For example, if the tree root value is 10 and has 2 children, 3 and 13, and 13 has one child with value of 15, printTree could show:

Level 1: 10

Level 2: 3

Level 2: 13

Level 3: 15

Note that the exact order of this example does not have to be followed as long as all 4 node values are shown with their correct level values

This function must also be written using recursion

printLevel(int n):

This function prints all the nodes of a tree on a given level (root level is 1) from left to right. For example, using the tree example on page 1 of this assignment, printLevel function calls would show the following:

printLevel(1): 6

printLevel(2): 4 8

printLevel(3): 2 7 9

printLevel(4): 1 3 10

Part 2) Write a main test program that allows the user to interactively test all these functions. The user must be able to insert, delete, search and print at any time similar to the way you wrote the main program for programming assignment 1. The demo of the program will be such that I will be testing to make sure everything works to my satisfaction.

When developing and testing this project, remember every change impacts may impact neighboring nodes, so youll want to test as many scenarios as you can predict.