----------
PRE-DISCUSSION
----------

PRINT OUT PROJECT SPEC

----------
OUTLINE
----------

ANNOUNCEMENTS
TREES



----------
ANNOUNCEMENTS
----------

SPEC HAS BEEN UPDATED - GO OVER UPDATES

GAME GRAPH / TREE IS CONCEPTUAL - THERE ARE OTHER WAYS OF REPRESENTING A
TREE BESIDES BUILDING ONE.

MAIN GOAL - GET SOMETHING THAT WORKS

ALSO WANT TO MAKE IT EFFICIENT - IN TERMS OF MEMORY AND PROCESSING SPEED

TRY TO DO THESE AT THE SAME TIME, BUT FOCUS ON GETTING SOMETHING WORKING



----------
TREES
----------

ADVICE FOR LEARNING THIS MATERIAL -

SIT DOWN AND PRACTICE ACTUALLY RUNNING THROUGH THE ALGORITHM

ALGORITHMS OFTEN SEEM STRAIGHTFORWARD WHEN JUST DESCRIBED TO YOU, BUT DETAILS
CAN TRIP YOU UP ON A TEST, FOR EXAMPLE.

IF YOU HAVE TIME, I RECOMMEND PROGRAMMING IT (BUT I WILL ADMIT THAT TAKES
MORE TIME)






EVERYTHING WE HAVE SEEN, AND WILL SEE, IS A BINARY TREE

SEARCH TREES AND AVL TREES BOTH ADHERE TO THE ORDERING PROPERTY

AVL TREES, UNLIKE SEARCH TREES, ARE BALANCED, AS WE SAW IN THE LAB YESTERDAY



--- TRAVERSALS

ANY BINARY TREE (AND ANY TREE REALLY) CAN BE TRAVERSED IN THE SAME WAY

TWO MAJOR WAYS TO TRAVERSE (AND THIS IS TRUE OF GRAPHS, AS WE WILL SEE)

DEPTH FIRST AND BREADTH FIRST

THE PRE, IN, AND POST ORDER TRAVERSALS ARE ALL DEPTH FIRST



BOTTOM LINE - IN ONE WAY OR ANOTHER YOU NEED TO USE A STACK OR A QUEUE TO
TRAVERSE A TREE.

USING AN EXPLICIT STACK OR QUEUE CAN BE MORE EFFICIENT



DRAW SOME TREE WITH ARROWS INDICATING THE ORDER OF TRAVERSAL

ALSO DRAW OUT THE RESULT OF ALL THE DIFFERENT TRAVERSALS




--- BREADTH FIRST SEARCH -

USE A QUEUE




--- DEPTH FIRST SEARCH -

MY SOLUTION -
IS BASED ON THE ALG DESCRIBED IN THE BOOK.

PROCESS ALL OF THE DEPTH FIRST SEARCHES IN GENERALLY THE SAME WAY, USING
THE SAME CODE.

USE A STACK TO STORE NODES THAT WE WANT TO LOOK AT AGAIN

ALSO USE AN "OPERATOR" THAT OPTIONALLY HAS ITS OWN "VALUE STACK" TO DO
INTERESTING THINGS AS WE TRAVERSE.

CAN BE USED TO PRINT THE TRAVERSAL, EVAULATE ARITHMETIC EXPRESSIONS, EVALUATE
TREE INVARIANTS (SEARCH OR AVL INVARIANTS), ETC

INVARIANT - NEED TO KEEP A CONSISTENT NUMBER OF ELEMENTS ON THE VALUE STACK


--- GO OVER THE CODE