Class Notes (838,386)
Canada (510,872)
CS 234 (31)


6 Pages
Unlock Document

Computer Science
CS 234
Robert Sproule

CS 234 – Lecture 12, Binary Trees and Heaps June 13, 2013 Binary Trees: • Binary Trees are another representation of data that we can use, sometimes more effectively than, say, a Python list or a linked list Some important features of a tree are: • Root (A) • Left Child (B is the left child of A) • Right Child (E is the right child of B) • Siblings (D and E are siblings) • Interior Nodes (B is an interior Node) • Height (The number of levels – height 4) • Depth (A is depth 0, F is depth 2) • Ancestors (The ancestors of E are B and A) • Descendants (The des. of C are F and H) • Special Types of Binary Trees: o Full Binary Tree – every node has either ZERO or TWO children o Perfect Binary Tree – all leaves are at the SAME level o Complete Binary Tree – all levels besides the last are full, and the last level has all nodes as far to the left as possible NOTE: A perfect binary tree is both full and complete • Properties of Binary Trees: o A perfect binary tree of height h has exactly 2 – 1 nodes  Ex. A perfect tree of height 4 would have 15 nodes o A perfect binary tree of size n has a height of log 2n+1)  Ex. A perfect tree of size 31 would have height 5 h-1 h o A complete binary tree of height h has a size n such that 2 <= n <= 2 – 1 • Memory Model of a Tree A tree is stored in data in a manner similar to that of a linked list. We declare a node structure with 3+ fields, including a data field, as well as a field for both left and right subtrees. The left and right hold other nodes, or None if that child is empty. This forms the recursive tree structure. The data field holds whatever information you wish to store in your tree. The figure to the left shows the root node and both of its children in memory. The next level of the tree could have up to 4 nodes. • Tree Traversals o The traversal of a tree is iteration over the nodes of the tree, one at a time. Different types of iterations would be used for different purposes. We define these iterations into two main classes o Depth First Traversal:  Pre-Order Traversal – we analyze the root node first, then traverse the left subtree, then traverse the right subtree (the root becomes FIRST)  In-Order Traversal – we traverse the left subtree first, then the root node, then traverse the right subtree (in ORDER from left to right)  Post-Order Traversal – we traverse the left subtree first, then the right subtree, then the root node (the root becomes LAST) o Breadth First Traversal:  We visit the nodes from top to bottom, left to right  This is much harder to code than the depth first traversals; while depth first can
More Less

Related notes for CS 234

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.