STUDENT TASKS
6_6. Complete the implementation of method recursiveFind().
{
if (tree == null)
return null;
else if(((Comparable)target).compareTo(root.getValue())==0)
return tree;
else if (((Comparable)tree.getValue()).compareTo(target)>0)
return recursiveFind(tree.getLeft(), target);
else
return recursiveFind(tree.getRight(), target);
}//recursiveFind
6_7. Test your implementation of recursiveFind() by creating a BST Object on the BlueJ workbench, building a small tree with String values, then calling testRecursiveFind().
Works great, just takes a long time to make the tree... might be smart to make some method to make the whole process more simple for the future if I plan to work with trees a little more.
6_8. Try sketching a run-time stack to follow the the call to testRecursiveFind(). You can observe the recursive calls by using the BlueJ to set a breakpoint in the code for recursiveFind().
Done, not sure about the breakpoint part though, haven't touched any of that stuff since the very first lesson of last year.
Done, not sure about the breakpoint part though, haven't touched any of that stuff since the very first lesson of last year.
6_9. What are the relative advantages and disadvantages of the iterative and recursive algorithms?
Recursive algorithms tend to reduce code length, while iterative solutions are more simple to code in my opinion. It seems to me also that recursive solutions may stack overflow easier than iterative solutions. I generally prefer iterative solutions because they come to me more naturally, and up until now I've never encountered a situation where I had to reduce my code length using recursion. I also feel that recursive solutions aren't exactly logical. If I were to make an analogy, I feel like iterative solutions solve a puzzle, whereas recursive solutions build a whole new puzzle and use that puzzle to solve the puzzle we have in the first place. It requires almost a creative approach to coding.
Recursive algorithms tend to reduce code length, while iterative solutions are more simple to code in my opinion. It seems to me also that recursive solutions may stack overflow easier than iterative solutions. I generally prefer iterative solutions because they come to me more naturally, and up until now I've never encountered a situation where I had to reduce my code length using recursion. I also feel that recursive solutions aren't exactly logical. If I were to make an analogy, I feel like iterative solutions solve a puzzle, whereas recursive solutions build a whole new puzzle and use that puzzle to solve the puzzle we have in the first place. It requires almost a creative approach to coding.
6_10. What modifications would need to be made to class BST in order to call recursiveFind(), without recourse to a special calling method like testRecursiveFind()?
I'm confused of the question. From what I understand the answer is none, recursiveFind() works fine on its own, and testRecursiveFind() simply tests the algorithm with different parameters. If that's the question, then one simply has to change the parameters on recursiveFind() to that of the fields in the BST as testRecursiveFind() does.
6_11. The postOrder traversal produced a sequence which was the reverse order from the order of entry. Will this always be the case? Try some experiments to test the idea.
Yes it'll always be the case.
6_12. The inOrder traversal suggests a new method of sorting. Let's call this method the binarySearchTreeSort. The efficiency of this sort is O(nlogn) which puts it in the family of more efficient sorts along with Merge Sort, and Quick Sort.
Create a new class named binarySearchTreeSortDemo. Use the class to demonstrate the binarySearchTree sort on an array of 20 random integers with values in the range 1..100.
create the array
print the array
create a binary search tree from the array (ints need to be wrapped into Integer)
do an inOrder traversal of the BST to return values to the array in ascending order
print the sorted array
public class binarySearchTreeSortDemo
{
private int[] list;
public binarySearchTreeSortDemo()
{
list = new int[20];
for (int i=0; i<20; i++)
{
list[i] = ((int)Math.random()*100);
}
}
public void sort()
{
BST tree = new BST();
for(int i=0; i<20; i++) {
tree.add(list[i]); }
tree.testTreeTraversal();
}
}
6.13 & 6.14 I'm really unsure of how to make the recursive method for this. And nobody seems to have any pointers on it in their blogs so I'm extremely lost. I'm just going to try and go on and work without this problem.
6.15 I've tested this before in one of the quizzes. It's pretty obvious too that Inorder and infix and postOrder and postfix are the same, quite logical.
6.16 I see and understand how the call in between and the nature of run-time stacks causes the desired effect. I can easily solve recursive problems and such, it's just the creation of recursive methods which drives me insane. I've been working on the recursive javabat by the way like you said.
6.17 Working on it. But I wish to also get some queues and heaps done, so i'll get back to it this week.
I'm confused of the question. From what I understand the answer is none, recursiveFind() works fine on its own, and testRecursiveFind() simply tests the algorithm with different parameters. If that's the question, then one simply has to change the parameters on recursiveFind() to that of the fields in the BST as testRecursiveFind() does.
6_11. The postOrder traversal produced a sequence which was the reverse order from the order of entry. Will this always be the case? Try some experiments to test the idea.
Yes it'll always be the case.
6_12. The inOrder traversal suggests a new method of sorting. Let's call this method the binarySearchTreeSort. The efficiency of this sort is O(nlogn) which puts it in the family of more efficient sorts along with Merge Sort, and Quick Sort.
Create a new class named binarySearchTreeSortDemo. Use the class to demonstrate the binarySearchTree sort on an array of 20 random integers with values in the range 1..100.
create the array
print the array
create a binary search tree from the array (ints need to be wrapped into Integer)
do an inOrder traversal of the BST to return values to the array in ascending order
print the sorted array
public class binarySearchTreeSortDemo
{
private int[] list;
public binarySearchTreeSortDemo()
{
list = new int[20];
for (int i=0; i<20; i++)
{
list[i] = ((int)Math.random()*100);
}
}
public void sort()
{
BST tree = new BST();
for(int i=0; i<20; i++) {
tree.add(list[i]); }
tree.testTreeTraversal();
}
}
6.13 & 6.14 I'm really unsure of how to make the recursive method for this. And nobody seems to have any pointers on it in their blogs so I'm extremely lost. I'm just going to try and go on and work without this problem.
6.15 I've tested this before in one of the quizzes. It's pretty obvious too that Inorder and infix and postOrder and postfix are the same, quite logical.
6.16 I see and understand how the call in between and the nature of run-time stacks causes the desired effect. I can easily solve recursive problems and such, it's just the creation of recursive methods which drives me insane. I've been working on the recursive javabat by the way like you said.
6.17 Working on it. But I wish to also get some queues and heaps done, so i'll get back to it this week.
