Before starting any specific exercise, you may wish to download, extract, and open up the provided starter project for this lesson so that you'll have it ready when you need/want it.
Part A:
Be ready to demonstrate how the Binary Search Tree's Find algorithm works. You should be prepared to explain this verbally, using diagrams and pictures written on the whiteboard to clarify how the algorithm works.
Part b:
Also be ready to demonstrate how the Binary Search Tree's Add algorithm works.
Most likely the teacher will ask different pairs of people to explain each of the two parts, but you should be ready to do both parts if needed.
For this exercise you need to write up pseudocode for the Find_Loop method on the BinarySearchTree class. For this exercise you should have the Find method operate using a loop; a separate exercise will ask you to implement Find using a recursive approach.
This class is defined in the starter project for the POST Class Exercises, and is listed below for convenience. If you need more detail on any given method you should find the document/exercise in the PCEs which describes what the method in question should do.
For this exercise you need to write up pseudocode for each of the methods of the BinarySearchTree class that you'll be implementing during this week's PCEs using this document
Be ready to present your pseudocode to the class, and to walk the class through your "trace".
public class BinarySearchTree
{
// Protected so that the BST_Verifier subclass can get at it
// and verify that the tree looks right (for NUnit tests)
// Normally this should be private.
protected BSTNode top; // also (semi-)traditional to name this 'root', instead of 'top'
// You should make the BSTNode class a nested class
// Normally should be private; it's protected for the reasons explained above
protected class BSTNode
{
public BSTNode Left;
public BSTNode Right;
public int Data;
public BSTNode(int val)
{
Data = val;
}
}
public bool Find(int target)
{
if (top == null)
return true;
return false;
}
public void Add(int newValueToAdd)
{
}
}
This exercise is basically the same as one of the prior exercises, except that in this exercise you should implement the Find_Recursive method using a recursive approach.
The instructor is breaking up the overall goal of "write pseudocode for all the methods" into separate parts so that it will be easier to clearly identify which method everyone should be working on.
This exercise is basically the same as the prior exercise, except that this is for the Add_Loop method. Again, this method should use a loop, NOT recursion.
The instructor is breaking up the overall goal of "write pseudocode for all the methods" into separate parts so that it will be easier to clearly identify which method everyone should be working on.
This exercise is basically the same as one of the prior exercises, except that in this exercise you should implement the Add_Recursive method using a recursive approach.
The instructor is breaking up the overall goal of "write pseudocode for all the methods" into separate parts so that it will be easier to clearly identify which method everyone should be working on.
With a partner, start working on one of the PCEs for this week: Compare & Contrast Two Pow implementations
Be ready to explain your answers to the rest of the class; keep in mind that the important part of your explanation isn't the actual answer, but your reasoning and justification for the answer.
Fix 'comparing two pows' so that the numbers calculated are always a power of 2
"A “one-minute paper” may be defined as a very short, in-class writing activity (taking one-minute or less to complete) in response to an instructor-posed question, which prompts students to reflect on the day’s lesson and provides the instructor with useful feedback." (from http://www.oncourseworkshop.com/Awareness012.htm).
Once you're done with this lesson please head on over to the One-Minute Paper and fill it out: