All of the work in this project is my own! I have not left copies of my code in public folders on university computers. I have not given any of this project to others. I will not give any portion of this project to others taking this class. I realize that the penalty for turning in work that is not my own can range from an "F" in the class to dismissal from Trinity University.
Print Name __________________________ Time Required = ______.____ Hrs.
Signature __________________________ (pledged)
Binary Tree Class Lab
- Main Program
Individual/Team (1-2 Persons) Assignment
40 Points
1] Create program BinTree.java.
public class BinTree <T extends Comparable <T>>
2] The private data members must include equivalents to the following C declarations:
protected DLNode<T> root;
protected T tempInfo;
private static int DIAGNOSTIC_LEVEL = 10;
3] Create function
public BinTree()
which will create a new empty dynamic binary tree.
4] Create function
public boolean Empty()
which will return true if the binary tree is empty; otherwise return false.
5] Create function
public boolean SetLeft(T
newInfo, DLNode<T> Father)
which will return true if it is able to create a new node that contains newInfo
and link it to the left of the Father;
otherwise return false.
6] Create function
public boolean SetRight (T newInfo, DLNode<T> Father)
which will return true if it is able to create a new node that contains newInfo
and link it to the right of the Father;
otherwise return false.
7] Create function
public boolean Inplace (T newInfo)
which will return true if it is able
to create a new node and place it in order on the tree, in accordance with the
Comparable <T>; otherwise return false.
8] Create function
public void InorderTraversal (String Message)
which will (1) display the message,
(2) graphically display the Tree header information [Root], and (3) graphically
display all of the nodes in the Tree in order from low to high in accordance
with the Comparable <T>.
You may use and document the following:
public void DisplayHeader(String message, boolean DisplayTitles,
boolean DisplayTopLine, boolean DisplayBottomLine)
{
String rootStr, rearStr, ptrStr;
if (root == null)
{
ptrStr = new String(" null ");
rootStr = new String(" null ");
}
else
{
ptrStr = root.toString().toString().substring(7,root.toString().length());;
rootStr = root.toString().substring(7,root.toString().length());
}
if (message.length() > 0)
System.out.println(message);
if (DisplayTitles == true)
System.out.println(" root ");
if (DisplayTopLine == true)
System.out.println(" |---------------------------------------------------|-------------|");
System.out.printf("%10s | %49s | %10s |\n",ptrStr,"", rootStr);
if (DisplayBottomLine == true)
System.out.println(" |---------------------------------------------------|-------------|");
}
public void InorderTraversalHelper(DLNode<T> ptr)
{
if (ptr != null)
{
InorderTraversalHelper(ptr.left);
ptr.Display("", ptr, false, true, false);
InorderTraversalHelper(ptr.right);
}
}
public void InorderTraversal(String Message)
{
DisplayHeader(Message, true, true, true);
InorderTraversalHelper(root);
if (!Empty())
System.out.println(" |------------|----------------------------------------------------|------------|\n");
}
With these display functions, the following block of code:
if (DIAGNOSTIC_LEVEL <= 8)
{
System.out.println("\n--------------------------------------------------------------------------------");
System.out.println("--------------------------- DIAGNOSTIC_LEVEL = 8 -------------------------------");
System.out.println("------------------------------ Test Inplace -----------------------------------");
System.out.println("--------------------------------------------------------------------------------\n");
BinTree<Integer> Tree1 = new BinTree <Integer> ();
Tree1.Inplace(100);
Tree1.Inplace(50);
Tree1.Inplace(150);
Tree1.Inplace(25);
Tree1.Inplace(75);
Tree1.Inplace(125);
Tree1.Inplace(175);
Tree1.InorderTraversal("Contents Of Tree1");
}
Wiill produce the following output:
Contents Of Tree1
root
|---------------------------------------------------|-------------|
130c19b |
| 130c19b |
|---------------------------------------------------|-------------|
|------------|----------------------------------------------------|------------|
9cab16 | null |
25 | null |
|------------|----------------------------------------------------|------------|
1a46e30 | 9cab16 |
50 | 3e25a5 |
|------------|----------------------------------------------------|------------|
3e25a5 | null |
75 | null |
|------------|----------------------------------------------------|------------|
130c19b | 1a46e30 |
100 | 19821f |
|------------|----------------------------------------------------|------------|
addbf1 | null |
125 | null |
|------------|----------------------------------------------------|------------|
19821f | addbf1 |
150 | 42e816 |
|------------|----------------------------------------------------|------------|
42e816 | null |
175 | null |
|------------|----------------------------------------------------|------------|
9] Create function
public void TestBinaryTree ()
whose DIAGNOSTIC_LEVEL = 10 will do a java equivalent for the following block of C++ code. This block of code creates an array of 20 and fills it with values 1-20. It then randomly mixes up the numbers a bit. After the numbers are mixed up, it Inplaces these numbers into Tree and displays the Tree information in order.
# define MAX_LIST1 20
int
* NoArray,
Temp,
Counter;
NoArray = new int [MAX_LIST1 + 1];
for (Counter = 1; Counter <= MAX_LIST1; Counter ++)
NoArray [Counter] = Counter;
for (Counter = 1; Counter <= MAX_LIST1; Counter ++)
{
Loc1 = rand() % MAX_LIST1 + 1;
Loc2 = rand() % MAX_LIST1 + 1;
Temp = NoArray[Loc1];
NoArray[Loc1] = NoArray[Loc2];
NoArray[Loc2] = Temp;
}
for (Counter = 1; Counter <= MAX_LIST1; Counter ++)
Tree.Inplace(NoArray[Counter]);
Tree.InorderTraversal("Information In Tree");
10] Document the entire program using JavaDocs; Make sure that your name(s) is/are in the top documentation box.
11] What is a balanced tree?
____________________________________________________________________________________________
____________________________________________________________________________________________
12] What is a skew tree?
____________________________________________________________________________________________
____________________________________________________________________________________________
13] What is a complete tree?
____________________________________________________________________________________________
____________________________________________________________________________________________
1] Spot Check!
2] Print
BinaryTree.java and the javadocs.
3] Sign and complete the lab form.
Attach the printouts to this assignment sheet.
4] Mail me your solution in a message whose Subject is CSCI 1321 - BinTree 1
5] Make sure you have at least two additional
backup copies of all projects. Maybe store one on your Y drive and one on your
hard drive.
6] Those Labs labeled "Individual Assignment" are to
be done separately by each individual. Using a pen, each individual is to
print his/her name at the top of this document in the space provided and
sign it. Those Labs labeled "Team Assignment" may be done as a team or
individually. Using a pen, each individual on the team is to print print
his/her name at the top of this document in the space provided and sign it.
Submit only one copy of team assignments!