Binary Trees & Recursion
CSC 251 Study Guide đŗ
đ ī¸Wed, Dec 3, 2014
đ4 min read â 698 words
CSC 251 Study Guide đŗ
đ ī¸Wed, Dec 3, 2014
đ4 min read â 698 words
trees
root
binary tree
leaf
descendant
ancestor
binary search tree
full binary tree
complete binary tree
balanced tree
preorder
inorder
postorder
FUN TIP I đ
a fast way to remember this is through the following, starting by writing r in the far left then fill it out with L or R, representing left or right, as follows:
r L R - preorder L r R - inorder L R r - postorder
FUN TIP II đin-order traversal is probably easiest to see, because it sorts the values from smallest to largest (literally)
recursive method is a method that calls itself
recursive solutions repetitively
basically works like this:
examples of recursion in real life
example 1 provided - emptyVase đļ\
void emptyVase(int flowersInVase) {
if (flowersInVase > 0) {
//takes one flower
emptyVase(flowersInVase-1);
} else {
// vase is empty, nothing to do
}
}
public class Recursion2 {
public void countItDown(int counter) {
if (counter == 0)
return;
else {
System.out.println("Count: " + counter);
counter--;
countItDown(counter);
System.out.println("" + counter);
return;
}
}
public static void main (String[] args) {
Recursion2 myRecursor = new Recursion2();
myRecursor.countItDown(5);
}
}
count(n)
if (n > 0)
print n
count (n-1)
else
print done
count: n --> n = 3
count: (n-1) --> n = 2
count: (n-1) --> n = 1
count: (n-1) --> n = 0
public class Recursive {
public static void message(int n) { //displays message n times
if (n > 0) {
System.out.println("This is a recursive method.");
message(n-1);
}
}
}
public static int fib(int n) { // returns nth number in Fibonacci sequence
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
public static int factorial(int n) { // returns factorial of non-negative argument
if (n == 0)
return 1;
else
return n * factorial(n-1);
}
public static int gcd(int x, int y) { // returns greater common denominator of two arguments
if (x % y == 0)
return y;
else
return gcd(y, x % y);
}