Looking for last quarter's course web site?
Click here for the CS 106B, Autumn 2015 course web site.
NOTE: This web site is out of date.
This is the course web site from a past quarter, Autumn 2015.
If you are a current student taking the course, this is not your class web site, and you should visit the current class web site instead at http://cs106b.stanford.edu/.
If you are already at cs106b.stanford.edu, the web page may not be updated yet for the new quarter.
Please be advised that courses change with each new quarter and instructor.
Any information on this out-of-date page may not apply to you this quarter.
(Suggested book reading: Programming Abstractions in C++, Chapter 16, section 16.1)
Today we'll learn about a way of organizing data in memory called a binary tree.
A binary tree shares some aspects of the linked list that you have just studied. Just like linked
list has two parts that work together: ListNode (holds a piece of data and a "next" pointer) and
LinkedList (holds a pointer to only the first node of the list, from which we can traverse and
access the whole list), binary trees have a TreeNode and BinaryTree that work together.
Definitions:
tree: hierarchical structure of linked nodes.
binary tree: a tree where each node has at most two children
Recursive definition: A tree is either:
empty (NULL), or
a root node that contains: (1) data, (2) a left subtree, (3) a right subtree
Trees are useful throughout computer science. For example, the folders (directories) on a computer form a tree structure--each folder can contain more folders. Note that folders form a tree structure but not necessarily a binary tree structure, because a folder may have more than two sub-folders contained within it. Other tree structures include a family genealogy, a corporate organizational chart, (in AI) a decision tree, (in compilers) a parse tree ("a = (b+c) * d;"), or cell phone word auto-completion.
Binary tree terminology:
node: an object containing a data value and left/right children
root node: topmost node of a tree (the parent of all the others)
subtree: the smaller tree of nodes on the left or right of the current node
tree height: number of nodes from the root to the furthest descendant of that node
tree level or depth [of a node]: number of nodes from the root to that node
In your file's comment header, list both partners' names; also cite all sources of help, including books, web pages, friends, section leaders, etc.
Do not consult any assignment solutions that are not your (pair's) own.
Do not attempt to disguise any code that is not your (pair's) own.
Do not give out your assignment solution to another student (outside of your pair).
Do not post your homework solution code online. (e.g. PasteBin, DropBox, web forums).
Please take steps to ensure that your (pair's) work is not easily copied by others.
Remember that we run similarity-detection software over all solutions,
including this quarter and past quarters, as well as any solutions we find on the web.
If you need help solving an assignment, we are happy to help you.
You can go to the LaIR,
or the course message forum,
or email your section leader,
or visit the instructor / head TA during office hours.
You can do it!