COMP 9024, Assignment 2, 11s2
John Plaice
Tue Aug 30 11:37:43 EST 2011
You are to take supplied files BTNode.java and LinkedBinaryTree.java and modify
them to produce files BTNodeThreaded.java and LinkedBinaryTreeThreaded.java. You
will then submit the files using the following command.
give cs9024 assn2 BTNodeThreaded.java LinkedBinaryTreeThreaded.java
The submission due date is Tuesday, 30 August, 23:59:59.
BTNodeThreaded
File BTNode.java, defining class BTNode, will be modified to define class BTNodeThreaded.
In this class, you will add:
private BTPosition next;
public BTPosition getNext() { ... }
public void setNext(BTPosition v) { ... }
Of course, you should fill in the ... as appropriate.
LinkedBinaryTreeThreaded
File LinkedBinaryTree.java, defining class LinkedBinaryTree, will be modified to define
class LinkedBinaryTreeThreaded.
First, add to the class the type declaration:
public enum TraversalOrder {PREORDER, INORDER, POSTORDER};
Then add a field that uses that type:
protected TraversalOrder order;
Then add the following methods:
public TraversalOrder getOrder() { ... }
public void setOrder(TraversalOrder) { ... }
1
Then, modify the constructor so that the field is initialized:
public LinkedBinaryTreeThreaded(TraversalOrder o) { ... }
Then, basing yourself on the definition of preorderPositions(), add definitions
inorderPositions() and postorderPositions().
Then, modify the definition of positions() so that it will call, depending on the value
of order, one of preorderPositions(), inorderPositions() or postorderPositions().
Then add a field that uses that type:
protected BTNodeThread start;
Now, add method
public void threadTree() { ... }
which will thread the tree using, depending on the value of order, a pre-order, in-order or
post-order traversal of the nodes in the tree, and will put the start of the thread in node
start.
Finally, add method
public Iterator iteratorThreaded() { ... }
which will emulate iterator(), but use the threaded information.
1 Addendum, 24 August 2011
1.1 Using subclasses
Up to the development of the threadTree() method, the assignment is quite straightfor-
ward. The best way to do this is to write
• BTNodeThreaded as a subclass of BTNode;
• LinkedBinaryTreeThreaded as a subclass of LinkedBinaryTree.
This way, you will not have to rewrite all of the methods. Now, if you look at the code
of LinkedBinaryTree, then you will notice that all of the nodes in the tree are cre-
ated by createNode(...), which creates a BTNode. You will have to write a new
createNode(...) to create a BTNodeThreaded.
1.2 inorderPositions()
It turns out that you do not have to write inorderPositions(). It is already implemented.
2
1.3 Threading the tree
This is the hard part of the assignment, as you need to figure out what needs to be done
for each of the traversal orders. For each order, you will need to write a primary method,
which calls a recursive secondary method. For example, for the in-order case, the primary
method would look like this:
public void inorderThreadTree() {
BTNodePair startEnd = inorderTraverse(root);
start = startEnd.getStart();
}
where BTNodePair is a class file that you will need to submit. The real algorithm is in
the method inorderTraverse(...), which you have to figure out. Similarly for the other
traversal orders.
The idea of your algorithm is to singly-link the nodes in the tree in the correct traversal
order. The head of this singly-linked list will be held in the field start, which will be the
root for pre-order traversal and the leftmost child for in-order and post-order traversal.
1.4 TraversalOrder
The enumeration TraversalOrder should be placed in its own file, TraversalOrder.java.
1.5 Testing your program
I have written a class that allows you to test your program. It is in file BuildLBTT.java.
1.6 Submitting your program
The submission should include four files, not two:
give cs9024 assn2 BTNodeThreaded.java LinkedBinaryTreeThreaded.java \
BTNodePair.java TraversalOrder.java
2 Addendum, 26 August 2011
2.1 Type of iteratorThreaded
The type of iteratorThreaded() was wrong. It should be:
public Iterable> iteratorThreaded() { ... }
3
2.2 Expected output on test program
8 4 2 1 3 6 5 7 12 10 9 11 14 13 15
8 4 2 1 3 6 5 7 12 10 9 11 14 13 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 3 2 5 7 6 4 9 11 10 13 15 14 12 8
1 3 2 5 7 6 4 9 11 10 13 15 14 12 8
2.3 Package of submission
All submitted Java files should begin with the line
package chapter7;
and should import the class6 types as needed.
2.4 Interface of BTNodePair
package chapter7;
public class BTNodePair {
public BTNodePair() { ... }
public BTNodePair(BTPosition s, BTPosition e) { ... }
public BTPosition getStart() { ... }
public void setStart(BTPosition v) { ... }
public BTPosition getEnd() { ... }
public void setEnd(BTPosition v) { ... }
}
3 Addendum, 30 August 2011
The type for start is wrong. It should be
protected BTPosition start;
4
